Computer Science & Engineering

STL priority_queue

    이번 글에는 STL의 <queue> 헤더파일에 존재하는 내부 함수 우선순위 큐를 직접 구현해보았다. priority_queue를 C++ STL 홈페이지(https://www.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue)에서 찾아볼 경우 다음과 같이 나온다.

초록색 글씨를 보면 선언할 때 변수의 type(class도 가능)을 받고 두 번째 인자로 우선순위 큐를 구성하는 컨테이너, 즉 배열을 선언할 수 있다. 기본값으론 vector를 사용한다. 마지막 인자로 힙을 구성하는 비교 함수 연산자가 있는 class를 포함한다. 기본값인 less는 최대힙을 만들 때 사용한다. 최소힙으로 사용하고 싶을 경우 greater를 사용한다. 다음과 같이 최대힙, 최소힙을 선언할 수 있다.

#include <queue>

priority_queue<int, vector<int>, less<int>> pq; //최대힙
priority_queue<int, vector<int>, greater<int>> pq; //최소힙

우선순위 큐 동작 방식

 우선순위 큐는 힙을 이용한다. FIRST IN FIRST OUT인 queue와 다르게 우선순위가 높은 인자가 우선적으로 나온다. 힙의 push와 pop은 다음과 같이 동작한다. 예시는 5, 6, 3, 7, 10, 4가 순서대로 push될 경우 최대힙이 만들어지는 과정이다.

힙은 언제나 완전 이진트리이다. 동작방식은 다음과 같다.

삽입

• 삽입하려는 값을 트리의 맨 마지막에 넣는다.
• 부모노드와 비교하며 삽입하려는 값이 더 큰 경우 부모노드와 값을 바꾼다.
• 삽입하려는 값보다 큰 값이 나오지 않을 때까지 반복한다.
• 만약 root노드보다 삽입하려는 값이 큰 경우 root노드에 저장한다.

삭제

• 트리의 맨 아래의 맨 오른쪽에 있는 원소인 pivot을 root노드로 위치시킨다.
• 왼쪽 자식 노드와 오른쪽 자식 노드 중 큰 값과 비교한다.
• 자식 노드가 더 큰 경우 자식노드와 값을 바꾼다.
• pivot 값보다 작은 값을 만날 때까지 반복한다.
• 만약 leaf노드까지 도달한 경우 pivot 값을 leaf노드에 저장한다.

우선순위 큐는 위의 과정으로 동작한다. 여기서 비교하는 함수는 선언의 마지막 인자에 있는 class를 이용하여 비교연산을 한다. 

priority_queue 코드 설명

class의 구조와 멤버 변수는 다음과 같다.

template <class T, class CONT = std::vector<T>, class CMP = less<typename CONT::value_type>>
class mypriority_queue {
private:
    CONT container;
    int num;
    CMP compare;
}

    맨 첫 번째 줄을 보면 글 맨 위에 있는 사진에서 확인할 수 있듯이 template를 동일하게 선언하였다. 타입, 컨테이터, 비교클래스.

    멤버변수는 template로 선언한 container가 컨테이너, num은  원소의 수를 나타내고 compare는 비교를 실행할 인스턴스이다. 비교 클래스를 받기 때문에 클래스 안에 있는 비교함수나 연산자를 이용하기 위해선 그 class를 타입으로 가지는 인스턴스가 존재해야하기 때문에 선언하였다. 예를 들어 CMP안에 ()연산자가 정의된 경우 compare(a, b)와 같이 사용하여 비교연산을 수행할 수 있다.

사이트에 나와있는 멤버 함수는 다음과 같다.

이 중에 구현한 함수는 생성자를 포함해 empty, size, top, push, pop을 구현하였다. 다른 함수들은 많이 사용되지 않기 때문에 생략하였다.

소스 코드

아래 링크에서 확인할 수 있다.

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

이번에는 여러가지 알고리즘을 사용할 때 꼭 필요한 queue를 구현해보았다. STL의 queue에서 제공하는 priority_queue는 따로 minheap, maxheap으로 따로 구현하도록 하겠다. 우선 구현한 코드는 아래 링크에서 확인할 수 있다.

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

queue란?

    queue(큐)는 stack과 같은 기본적인 자료구조로 가장 마지막으로 들어간 원소가 가장 먼저 나오는 LIFO(Last In First Out)인 stack과 다르게 가장 먼저 들어간 원소가 가장 먼저 나오는 FIFO(First In First Out)이다. queue를 그림으로 표현하면 다음과 같다.

그림과 같이 한쪽은 나올 수 만 있는 출구가 있고 다른 한 쪽은 들어갈 수만 있는 입구가 있다. queue안에서 순서는 바뀌지 않는다. 따라서 들어간 순서와 나오는 순서가 똑같다. 큐에 원소를 넣는 것을 'push'라고 하고 원소를 빼는 것을 'pop'이라고 한다. 위 그림은 1부터 6까지 push한 상태에서 1번 pop을 하고 7을 push하려고 하는 상태이다.

구현

     큐의 구현은 여러가지로 할 수 있다. 배열로 구현하는 것은 간단하지만  pop을 여러번 하는 경우 배열의 크기는 일정하기 때문에 배열의 앞 부분은 비어있는 상태가 될 수 있다. 또 배열의 크기보다 push를 많이 하는 경우 새로 할당해줘야하는 등의 오버헤드가 있기 때문에 그러한 번거로움을 줄일 수 있는 연결리스트로 구현하였다. 연결 리스트를 이용하여 구현하였기 때문에 이전 글 만들었던 list와 비슷한 부분이 많았다. 우선 각 노드를 나타내는 구조체는 아래와 같다.

struct node {
    T data; //값이 들어가는 변수
    node* next; //다음 노드를 가리키는 포인터

    node(T input) { //생성자
        data = input; //input을 준 경우 input으로 data를 설정
        next = NULL; //다음 노드는 NULL포인터로 설정
    }
    
    node() { //생성자
        data = 0; //input이 없는 경우 0으로 초기화
        next = NULL; //다음 노드는 NULL포인터로 설정
    }
};

STL queue에서 제공하는 대부분의 함수를 구현하였다. iterator가 없기 때문에 굉장히 간단했다. 구현한 메소드로는 empty, size, front, back, push, pop, swap이 있다.

실행 결과

1. push, pop 실행 결과

int main() {
    myqueue<int> q1;
    for(int i = 1; i <= 10; i++) //q1에 1부터 10까지 넣음
        q1.push(i);
    
    while(!q1.empty()) { //q1 출력
        cout << q1.front() << ' ';
        q1.pop();
    }
}

2. front, back 실행 결과

int main() {
    myqueue<int> q1;
    for(int i = 1; i <= 10; i++) //q1에 1부터 10까지 넣음
        q1.push(i);
    
    cout << "front : " << q1.front() << "\nback : " << q1.back() << endl; //front, back 출력

    while(!q1.empty()) { //q1 출력
        cout << q1.front() << ' ';
        q1.pop();
    }
}

3. swap 실행 결과

int main() {
    myqueue<int> q1, q2;
    for(int i = 1; i <= 10; i++) //q1에 1부터 10까지 넣음
        q1.push(i);
    
    for(int i = 101; i <= 110; i++) //q2에 101부터 110까지 넣음
        q2.push(i);

    q1.swap(q2); //q1과 q2 swap

    while(!q1.empty()) { //q1 출력
        cout << q1.front() << ' ';
        q1.pop();
    }
    
    cout << endl;

    while(!q2.empty()) { //q2 출력
        cout << q2.front() << ' ';
        q2.pop();
    }
    
}

이렇게 간단한 자료구조 queue를 구현해보았다. 우선순위 큐는 따로 minheap과 maxheap으로 구현하도록 하겠다.

이번에는 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++에 대한 이해가 더 발전한 것 같다.