Computer Science & Engineering

이번에는 C++에서 제공하는 Standart Template Library의 <list>를 구현해보았다. list는 linked list(연결리스트)를 구현한 것이며 특징으로는 iterator를 제공하고 양방향 연결리스트라는 것이다. cplusplus.com에 검색하면 나오는 list의 모든 메소드들을 구현하지는 못하였고 많이 쓰이는 메소드 몇 가지만 구현하였다. 소스코드는 아래의 링크에서 확인할 수 있다.

https://github.com/Seo-sang/Cpp-_Standard_Template_Library/blob/master/mylist.cpp

연결리스트는 컴퓨터 전공생이면 1학년부터 C언어에서 포인터를 배우며 누구나 구현해보았을 것이다. 양방향 연결리스트도 이전노드와 연결해주는 것만 포함하면 전혀 다를 것이 없이 쉽게 구현할 수 있다. 따라서 이 구현에서 새로웠던 점은 iterator구현이다. list의 iterator 구현을 위한 특징이 하나 있다. 아래는 mylist의 멤버 변수이다.

멤버변수

public:
    node* head; //시작 노드
    node* tail; //마지막 노드
    node* fin; //end 노드
    int num; //노드 수

head와 tail은 첫 번째 노드와 마지막 노드를 가리킨다. iterator에서는 end가 존재한다. end는 연결리스트의 노드가 아니며 마지막만을 나타내는 기능을 제공한다. 즉 데이터가 들어있지 않다. 따라서 list에 아무것도 들어있지 않았어도 end를 가리키는 fin노드는 존재하여 유지시켰다.

iterator

class myiterator {
        node* current;
    public:
        myiterator(node* node = 0) : current(node) {};

        myiterator& operator++() {
            current = current->next;
            return *this;
        }
        
        myiterator& operator--() {
            current = current->prev;
            return *this;
        }

        node* operator&() {
            return current;
        }

        T& operator*() {
            return current->data;
        }

        bool operator !=(const myiterator& cmp) {
            return (current != cmp.current);
        }

        bool operator ==(const myiterator& cmp) {
            return (current == cmp.current);
        }
    };

iterator는 vector를 구현했을 때와 비슷하다. 연산자는 ++, --, *, !=, ==를 구현하였고 &연산자는 iterator로부터 포인터 값을 얻기 위해 내가 따로 만들었다. 물론 사용자도 사용할 수 있다. ++와 --는 각각 다음 노드, 이전 노드로 이동하는 연산자이다. iterator를 이용한 연결리스트를 순회할 때 굉장히 유용하게 사용할 수 있다. * 연산자는 현재 노드의 데이터 값을 얻어오는 연산자이다. ==와 !=는 각각 두 iterator변수가 같은 노드를 가리키는지 다른 노드를 가리키는지를 판단하는 연산자이다.

methods

구현한 메소드를 나열해보면

size, empty, front, back, push_back, pop_back, push_front, pop_front, insert, erase, begin, end로 총 12가지이다. 메소드는 모두 cplusplus.com에서 list를 검색했을 때 나오는 메소드와 똑같이 동작한다. 아래에서 실제 실행 결과로 보여주겠다. 코드가 길어 소스코드는 위의 링크에서 확인할 수 있다.

실행결과

이 코드는 아래와 같이 동작한다.

    1. 1부터 10까지 push_back을 한 다음 출력

    2. 3번 pop_back()을 한 다음 출력

    3. 100부터 3번 push_front한 다음 출력

    4. 6번 pop_front한 다음 출력

실행 결과는 다음과 같이 올바르게 나오는 것을 알 수 있다. iterator를 이용하여 모든 노드의 데이터를 출력하는 것도 올바르게 동작하는 것을 확인할 수 있다.

이번에는 insert와 erase를 사용해보겠다.

이 코드는 다음과 같이 동작한다.

    1. 1부터 10까지 push_back하고 출력

    2. begin부터 2번 다음 노드로 이동 후 100 insert 하고 출력

    3. 그 다음 3번 다음 노드로 이동 후 erase하고 출력

결과는 다음과 같다.

실행 결과 begin부터 2번 이동한 3번 위치에서 insert를 수행할 경우 3번 위치에 100을 삽입하고 3부터는 뒤로 밀리는 것을 알 수 있다. 그 다음 3번 위치부터 3번 이동한 6번 노드에서 erase연산을 수행하여 6번 노드가 사라진 최종 결과가 정확히 나왔음을 확인할 수 있다.

이렇게 C++ STL의 list의 일부를 직접 구현해보았다. 연결리스트를 직접 구현할 경우 예상치 못한 널포인터로 segmentation fault가 발생하는 것을 자주 접할 수 있다. 글쓴이 역시 list를 구현하며 몇 번의 segmentation fault를 보았다. 하지만 포인터 관리만 잘해주면 오류를 쉽게 찾고 고칠 수 있기 때문에 이렇게 직접 구현해보며 실수를 깨달을 수 있었다.

stack은 가장 기본적인 자료구조이다. 이 글에서는 C++의 template를 이용해 어떤 type의 변수던지 사용할 수 있는 STL의 stack을 그대로 구현해보겠다. 구현 방법은 이전 글인 vector만들기와 상당히 유사했다. 코드는 다음과 같다.

#include <iostream>
#include <stdlib.h>
#include <cstring>

using namespace std;

template <typename T>
class mystack {
private:
    int num;
    int len;
    T* tmp;
    T* arr;
public:
    mystack() { //생성자
        mystack::num = 0;
        mystack::arr = (T*)malloc(sizeof(T) * 10); //초기 stack 배열 크기 10으로 설정
        memset(arr, 0, sizeof(arr)); //배열 초기화
        len = 10; //초기 크기 10
        tmp = NULL;
    }

    ~mystack() { //소멸자
        if(arr) free(arr); //메모리 반환
    }

    T top() { //가장 위에 있는 원소 리턴
        return arr[num-1];
    }

    int size() { //stack에 있는 원소의 수 리턴
        return num;
    }

    bool empty() { //stack이 차있는 경우 false 빈 경우 true 리턴
        if(num) return false;
        else return true;
    }

    void pop() { //가장 위에 있는 원소 제거
        if(num == 0) return; //stack이 빈 경우 어떤 일도 일어나지 않음
        arr[num--] = 0; //가장 위에 있느 원소 0으로 설정하고 num 감수
        if(num < len/2) { //만약 배열의 절반도 안차있는 경우
            len /= 2; //배열 크기 절반으로 감소
            tmp = arr; //임시 배열 설정
            arr = (T*)malloc(sizeof(T) * len); //배열 절반 크기로 새로 생성
            for(int i = 0; i < num; i++) arr[i] = tmp[i]; //stack에 있는 원소 복사
            free(tmp); //임시 배열 메모리 반환
        }
    }

    void push(T input) { //원소 stack 맨 위에 추가
        if(num == len - 1) { //stack 배열이 모두 찬 경우
            len *= 2; //배열 크기 두배로 늘림
            tmp = arr; //임시 배열 설정
            arr = (T*)malloc(sizeof(T) * len); //배열 크기 두 배로 생성
            for(int i = 0; i < num; i++) arr[i] = tmp[i]; //stack에 있는 원소 복사
            free(tmp); //임시 배열 메모리 반환
        }
        arr[num++] = input; //원소 맨 위에 추가
    }
};

위의 코드를 이용하여 직접 stack을 실행시켜 보았다.

1부터 4096전까지 2씩  곱하며 stack에 넣었다. 이후 stack의 크기를 출력하였고 그 다음 7개의 원소 top을 출력하고 pop하였다. 그 결과 stack

의 크기를 또 한번 출력하였다. 결과는 다음과 같다.

다음과 같이 12개의 원소가 잘 들어갔고 7개의 원소가 잘 pop된 것을 알 수 있다. template를 사용하였기 때문에 int형 변수 말고도 mystack을 사용할 때 <>안에 다른 자료형을 사용할 수 있다. ADT인 class나 struct도 사용할 수 있기 때문에 굉장히 편리하게 사용할 수 있다. 다른 STL 구현 코드들도 아래 링크에서 확인할 수 있다.

https://github.com/Seo-sang/C-_Standard_Template_Library

이번에는 C++에서 가장 많이 사용하는 vector를 구현해보았다. 완벽하게 똑같이 만들고싶은 욕심이 있었지만 한계가 있었다. 우선 소스코드는 아래 링크에 있다.

https://github.com/Seo-sang/C-_Standard_Template_Library

1. 벡터 동작 방식

    벡터는 크기가 부족할 경우 크기를 두 배씩 늘리는 동적배열이다. 따라서 초기 배열의 크기를 10으로 잡았다. 처음 myvector를 선언할 경우 배열의 크기는 10으로 설정된다. push_back을 했을 때 공간이 부족한 경우 길이 2배짜리 배열을 만든 후 원래 배열의 내용을 옮겨 담는다. 반대로 pop_back도 마찬가지이다. 현재 배열을 사용하는 공간이 이전 배열의 1/2보다 작은 경우 배열의 크기를 1/2로 줄이고 내용을 복사한다.

2. iterator

    벡터뿐 아니라 다른 STL에서도 iterator 기능은 굉장히 많이 사용한다. 그렇기 때문에 이 기능은 뺄 수 없었다. iterator가할 수 있는 연산은 ++, --, *, !=, == 총 5가지를 구현하였다. iterator를 구현하며 클래스 자체를 리턴할 수 있음을 알 수 있었다. 현재 가리키는 포인터를 하나 두어 상대적인 연산을 하도록 만들었다. iterator class의 코드는 다음과 같다.

class myiterator {
        T* current;
    public:
        myiterator(T* node = 0) : current(node) {};

        myiterator& operator++() {
            current++;
            return *this;
        }
        
        myiterator& operator--() {
            current--;
            return *this;
        }

        T& operator*() {
            return *current;
        }

        bool operator !=(const myiterator& cmp) {
            return (current != cmp.current);
        }

        bool operator ==(const myiterator& cmp) {
            return (current == cmp.current);
        }
    };

클래스의 멤버 변수는 하나가 있다 current라는 변수로 벡터 배열의 원소를 가리키는 포인터이다. iterator는 항상 begin부터 시작하거나 end부터 시작한다. 그렇기 때문에 begin, end 코드를 보면 다음과 같다.

    myiterator begin() {
        return myiterator(head);
    }

    myiterator end() {
        return myiterator(tail);
    }

생성자를 이용하여 head와 tail을 현재 포인터로 하는 생성자를 만들었다. begin()을 호출할 경우 iterator는 가장 첫 번째 원소를 가리킨다. end()를 호출할 경우 iterator는 가장 마지막원소 다음을 가리킨다. 벡터에서 end에는 원소가 존재하지 않고 마지막을 나타낸다. 그렇기 때문에 나도 크기가 10인 경우 9개의 원소만 넣고 10번째는 항상 빈 상태로 유지하였다.

3. 메소드

    우리가 가장 많이 사용하는 push_back, pop_back을 포함하여 front, back, size, empty, clear, resize, at을 구현하였고 iterator연산에 빠질 수 없는 begin, end도 구현하였다. 코드의 길이가 꽤 길기 때문에 소스코드는 github링크를 통해 확인하기 바란다. 가장 중요한 부분이 push_back과 pop_back에서의 길이를 2배로 늘리거나 1/2로 줄이는 일이었다. 처음에 memcpy를 이용해봤으나 생각한대로 동작하지 않아 for문을 이용해 일일히 복사하는 수 밖에 없었다. resize도 마찬가지로 크기 n을 인자로 받았을 경우 10부터 2배씩 늘려 n을 포함할 수 있는 크기로 배열의 크기를 재설정하였다.

    사용만하던 벡터를 직접 구현하면서 벡터에 대한 이해가 더 깊어진 것 같고 특히 iterator를 직접 구현해보고 연산자를 구현해보면서 C++에 대한 이해가 더 발전한 것 같다.