[C++.STL] 4장: 컨테이너(container) 클래스

4.1 개요

 

표준 라이브러리는 약 10가지 종류의 컨테이너를 제공한다. 이 장에서는 이들 컨테이너의 종류와 각각의 성질에 대해 알아보고, 실제 문제를 해결하는데 있어 어떤 컨테이너를 선택해야 할지에 관해 언급하고자 한다. 이후의 절에서는 각 컨테이너에 대해서 보다 자세히 다루기로 한다.

다음 표는 표준 라이브러리가 제공하는 10가지 형태의 컨테이너를 나열하고, 각 컨테이너의 주요 특징들을 덧붙여 놓았다.
 

이름	특징
vector	임의접근이 가능하며, 뒤에서의 삽입이 빠름
list	위치에 상관없이 삽입과 삭제가 빠름
deque	임의접근이 가능하며, 앞과 뒤에서의 삽입이 빠름
set	원소들을 순서대로 관리하며, 소속검사와 삽입,삭제가 빠름
multiset	중복을 허용하는 set
map	키를 통해 값을 접근하며, 삽입과 삭제가 빠름
multimap	중복키를 허용하는 map
stack	top에서만 삽입과 삭제가 가능
queue	삽입은 뒤쪽에서, 삭제는 앞쪽에서
priority_queue	가장 큰값의 접근과 삭제가 빠름

   

 

4.2 컨테이너 선택하기

다음 질문들은 특정 문제를 풀고자 할 때 어떤 종류의 컨테이너를 선택하는 것이 좋은가에 관한 몇가지 선택 기준을 제시하고 있다.

콜렉션내의 값들을 어떤 방식으로 접근하는가?

임의접근이 필요하다면, vector와 deque를 사용하라. 순차접근만으로 충분하다면, 다른 컨테이너를 써도 무방하다.

콜렉션내의 값들에 순서를 매길 것인가?

값들이 나열되는 방식에는 여러가지가 있다. 컨테이너가 유지되는 동안 계속 순서가 유지되어야 한다면, set을 선택해야 한다. set에 삽입을 하면 자동적으로 순서에 맞게 놓여진다. 반면에, 순서가 어느 한시점에서만 중요시된다면, list나 vector에 값들을 삽입하고, 적절한 때에 해당 컨테이너를 정렬을 하는 것이 더 수월하다. 만약에 데이터구조 내에서 유지되는 값들의 순서가 삽입하는 순서에 관계가 있다면, stack이나 queue또는 list가 최상의 선택이 될 것이다.

실행중에 데이터 구조의 크기가 광범위하게 변하는가?

그렇다면, list나 set를 선택하는 것이 가장 좋다. vector나 deque은 콜렉션으로부터 원소들을 제거한 뒤에도 커다란 버퍼를 계속 유지하고 있다. 만약에, 콜렉션의 크기가 상대적으로 고정되어 있다면, vector나 deque가 같은 수의 원소를 지니고 있는 list나 set보다는 적은 메모리를 사용한다.

콜렉션의 크기를 추정할 수 있는가?

vector는 원하는 크기의 메모리 블럭을 미리 할당받을 수 있다(reserve() 멤버함수를 사용). 이는 다른 컨테이너에서는 제공되지 않은 기능이다.

어떤 값이 콜렉션내에 포함되어 있는지를 자주 확인하는가?

만약에 그렇다면, set이나 map을 선택하는 것이 좋겠다. set이나 map에서는 어떤 값이 컨테이너에 속해 있는지를 검사하는 것이 매우 빠르지만, 다른 종류의 콜렉션에서는 이를 검사하기 위해서 컨테이너에 저장된 모든 원소들을 일일이 비교해야 한다.

콜렉션에 대해 인덱싱이 가능한가? 다시말해, 콜렉션을 키와 값의 쌍으로 생각할 수 있는가?

키들이 0과 어떤 상한선 사이의 정수값이라면, vector와 deque를 선택해야 한다. 반면에, 키값들이 어떤 순서가 있는 데이터형이라면(문자나 문자열 또는 사용자 정의 타입과 같은) map을 사용한다.

값들간에 서로 연관성이 있는가?

표준 라이브러리가 제공하는 컨테이너에 속한 모든 값들이 다른 값과 같은지를 비교할 수 있어야 한다. 하지만, 모든 컨테이너가 less-than 연산자를 제공할 필요는 없다. 그러나, less-than 연산자를 사용해서는 순서가 유지될 수 없는 값들은 set이나 map에 저장하면 안된다.

콜렉션으로부터 가장 큰 값을 찾아서 제거하는 연산이 자주 일어나는가?

그렇다면, priority_queue가 최선의 컨테이너이다.

데이터 구조의 어느 위치로 값들이 삽입되고 제거되는가?

중간쯤에서 값들이 삽입되고 제거된다면, list가 최선의 선택이다. 값들이 앞쪽에만 삽입된다면, deque나 list가 더 좋겠고, 끝에서만 삽입과 삭제가 이루어진다면, stack이나 queue가 좋을 것이다.

두개 이상의 수열을 하나로 합치는 일이 자주 일어나는 연산인가?

그렇다면, set이나 list가 좋은 선택이 될 것이다. 이 둘중에 어느 것을 선택할 지는 순서가 유지되는가의 여부에 따라 결정하면 된다. 두개의 set을 합치는 것은 매우 효율적인 연산이다. 콜렉션의 순서가 유지되지 않고, list가 제공하는 효율적인 splice() 멤버함수를 사용하면, list를 선택하는 것이 좋겠다. 왜냐하면, 이 연산은 다른 컨테이너에서는 제공하지 않는 연산이기 때문이다.

대부분의 경우에 주어진 문제에 대해서 여러가지 컨테이너가 사용될 수 있는데, 그럴때는 실제 수행시간을 비교해서 어느 것이 나은가를 결정하는 것도 한 방법이 될 것이다.

 

 

 

4.3 메모리 관리 이슈들

표준 라이브러리의 컨테이너(container)는 템플릿으로 설계되었기 때문에, 다양한 타입의 원소들을 관리할 수 있다. 이들 타입에는 정수형이나 문자형과 같은 기초적인 데이터 타입이나 포인터, 또는 사용자 정의(user-defined) 타입들이 있다. 컨테이너는 레퍼런스(reference)를 담을 수 없다. 일반적으로 컨테이너의 메모리 관리는 프로그래머와는 무관하게 표준 컨테이너 클래스가 알아서 자동으로 관리한다.

값들은 복사 생성자(copy constructor)를 사용하여 컨테이너에 배치된다. 대부분의 컨테이너 클래스의 경우, 자신이 관리하고 있는 원소들의 타입은 기본 생성자(default constructor)를 정의하고 있어야 한다. copy()와 같이 컨테이너로의 복사를 수행하는 generic 알고리듬들은 대입 연산자(assignment operator)를 사용한다.

복사 생성자나 대입 연산자(=, assignment operator)를 사용하면, 컨테이너 A 전체가 새로운 컨테이너 B로 복사되는 경우가 발생하는데, 이 경우 컨테이너 A내의 모든 원소(객체)들은 각 원소들에 정의되어 있는 복사 생성자나 대입 연산자를 사용하여 컨테이너 B로 복사가 된다. 그 결과가 'deep copy'가 될지, 'shallow copy'가 될지는 대입 연산자를 프로그래머가 어떻게 정의했는지에 달려 있다. 대부분의 컨테이너 클래스가 데이터 구조를 위해 내부적으로 사용하는 메모리는 자동적이고 효율적으로 할당되고 반환된다.

컨테이너의 원소 타입에 대해 소멸자(destructor)가 정의되어 있다면, 컨테이너로부터 값들을 삭제할 때, 이 소멸자가 호출된다. 컨테이너 전체가 소멸되는 경우에는, 남아있는 원소들에 대해서 각각 소멸자를 호출한다.

포인터 값을 담고 있는 컨테이너에 관해 몇가지 언급하기로 하자. 이러한 콜렉션이 그리 드문 것은 아니다. 예를 들어, 클래스나 하위클래스의 인스턴스를 나타내는 값들을 저장할 때는 포인터의 콜렉션이 유일한 방법이다. 이러한 콜렉션은 11.3절의 예에서 살펴볼 수 있다.

이러한 경우에 컨테이너는 포인터 값 자체만 관리하면 된다. 포인터가 참조하는 값에 대한 메모리 관리는 프로그래머가 책임져야 할 부분이다. 즉, 컨테이너가 해당 메모리에 대한 포인터를 간직하고 있는 동안에는 그 메모리를 반환해서는 안되며, 일단 포인터가 컨테이너에서 삭제되면 그 포인터가 가리키고 있던 메모리를 올바르게 반환하는 작업들은 프로그래머 스스로가 담당해야 하는 것이다.

컨테이너에 포인터를 저장하는 문제에 관해서는 다음 절에서 별도로 다루기로 한다.

 

 

 

4.4 컨테이너에 포인터 저장하기(문제점과 해결책)

STL 컨테이너는 포인터 저장용으로 설계된 것이 아니라, 객체를 담을 목적으로 설계된 자료 구조이다. 만일 여러분이 작성하고 있는 프로그램에서 STL을 사용하고 있고, STL 컨테이너에 포인터를 저장할 필요가 있는 사람들에게는 이 말이 상당히 아쉽게 들릴 것이다. 그래서, 되도록이면 컨테이너에 포인터를 저장하지 않는 것이 좋으나, 어쩔 수 없이 포인터를 저장해야만 한다면(실제로 이런 경우가 흔히 발생한다), 이 절에서 설명할 내용을 잘 기억하고 있어야 한다. 뉴스 그룹이나 기타 여러 사람들이 말하는 것과는 달리, STL 컨테이너에 객체 대신에 포인터를 저장한다고 해서 크게 문제가 될 것은 없다. 하지만, 실제로 컨테이너에 포인터를 저장하는 경우에 메모리 누수(memory leak)와 같은 여러가지 골치아픈 문제들을 일으킬 소지가 있는 것은 사실이므로, 되도록이면 피하는 것이 좋다. 하지만, 다음과 같은 예외적인 상황에서는 컨테이너에 포인터를 저장할 수 있다.

• 객체를 프로그램 이곳 저곳에 중복해서 만들어 놓기에는 객체의 크기가 너무 큰 경우나, 이미 메모리 힙(heap)에 생성되어 있는 크키가 큰 객체를 컨테이너에 추가하고자 하는 경우. 즉, 크기가 큰 객체의 복사는 부담스럽기 때문에 이를 피하려는 경우다.
• 하나의 객체를 다른 여러 컨테이너에 저장하려는 경우. 본인이 생각하기에는 이것이 가장 흔한 경우가 아닐까 한다.
• base object로부터 상속된 여러 다양한 객체들을 한 컨테이너에 저장하려는 경우. 물론, CAD 시스템에서 이러한 경우가 흔히 있는데, Smalltalk와 달리 C++에서는 진정한 heterogeneous 컨테이너를 요구한다는 것은 좀 무리라는 것을 염두할 필요가 있다. 그렇다고 불가능한 것은 아니다. (예를 들어, '도형'이라는 기초 클래스(base class)로 부터 상속된 '삼각형', '사각형', '원', '타원'이라는 여러 하위 클래스(subclass)의 객체들을 한 컨테이너에 담고자 하는 경우)

이러한 예외적인 상황에서 컨테이너에 포인터를 저장하기로 결정하였다면, 다음에 열거한 사항들을 유의하기 바란다.

1. 지역 변수(local variable)를 가리키는 포인터를 저장하지 말 것. 이것은 굳이 컨테이너에 포인터를 저장할 때 뿐만 아니라, C나 C++ 프로그래머라면 반드시 유의해야할 아주 기본적인 사항이다.
2. 포인터가 가리키는 객체들에 대한 소멸자(destructor)는 당신이 책임져야 할 부분이다. 당신이 의도한 바에 따라 당신만의 소멸자를 정의해 주어야 한다는 뜻이다.
3. 일부 STL 컨테이너에서는 컨테이너에 담긴 원소들에 대해 '<' 연산자를 이용하여 비교 연산을 수행하는데, 만약 이러한 컨테이너에 포인터를 담는다면, 포인터간의 대소 비교는 아무런 의미가 없으므로, 이를 반드시 고려하고 있어야 한다. 이 경우가 'smart pointer'가 아주 긴요하게 쓰일 수 있는 경우다.
4. set이나 map과 같이 STL 컨테이너를 생성할 때, 비교 함수(comparator)를 템플릿 인자로 요구하는 컨테이너에 포인터를 저장하고자 할 때는 반드시 그에 따르는 적절한 비교 함수를 만들어서 넘겨주어야 한다. 아래 예제를 참고하라.

4.4.1 4번 유의 사항에 대한 예제

일단 다음 코드를 한번 찬찬히 살펴보기 바란다. 특히 빨간 부분으로 표시된 'compare'에 주목하라.

#include <iostream>
#include <list>
#include <set>
#include <algorithm>

struct compare {
   bool operator()(const int* i1, const int* i2) const
   { 
      return *i1 < *i2;
   }
};

void print(int* i) { cout << " " << *i; }

int main()
{
   list<int*> list1;

   // list1을 정수 0,1,4,9,16 각각에 대한 포인터로 초기화
   for(int i = 0; i < 5; ++i)
      list1.push_back(new int(i * i));

   // list1의 내용을 출력
   cout << "List of int*: (";
   for_each(list1.begin(), list1.end(), print);
   cout << ")" << endl;

   // list1에 있던 정수 포인터들을 set1으로 옮긴다. set1을 선언할 때, 포인터가
   // 아닌, 포인터가 가리키는 정수간의 비교가 이루어지도록 사용자가 작성한
   // 비교 함수(comparator)를 사용해야 한다. 
   set<int*, compare> set1;
   copy(list1.begin(), list1.end(), 
      insert_iterator<set<int*, compare> >(set1, set1.begin()));

   // set1의 내용을 출력
   cout << "Set of int* : [";
   for_each(set1.begin(), set1.end(), print);
   cout << "]" << endl;

   return 0;
}

▶ 실행결과
List of int*: ( 0 1 4 9 16)
Set of int* : [ 0 1 4 9 16]

일단 설명의 간편함을 위해서, 객체의 포인터 대신에 int의 포인터를 담은 list 컨테이너를 예로 들어 설명했다.

 앞에서 지적했던 유의사항 4번을 명심하라. set, multiset, map과 같은 컨테이너에 포인터를 저장하고자 할 때는,

포인터가 가리키는 객체들간에 비교가 이루어지도록 비교 함수(comparator)를 프로그래머가 직접 제공해줘야 한다.

이렇게 하지 않으면 아무 의미 없는 포인터간의 비교 연산이 일어나게 된다.

4.4.2 2번 유의 사항에 대한 예제

컨테이너에 포인터를 담으려고 할 때는, 각각의 포인터가 가리키는 메모리 영역을 반환하는 코드를 반드시 추가해야 한다. 만약에 이렇게 하지 않으면, stack에 위치한 컨테이너 객체가 소멸될 때, 포인터가 저장된 메모리 영역만 반환되므로, 메모리 누수(memory leak)가 발생하게 된다. 즉, 컨테이너는 포인터가 저장된 메모리 영역을 복사하고 삭제할 뿐이며, 포인터가 가리키는 객체가 차지하는 메모리 영역에 대해서는 책임지지 않는다. 다음은 이러한 역할을 위해 템플릿으로 구현된 삭제 전용 함수이다.

   template <class ForwardIterator>
   void sequence_delete(ForwardIterator first, ForwardIterator last)
   {
       while (first != last)
           delete *first++;
   }

   template <class ForwardIterator>
   void map_delete(ForwardIterator first, ForwardIterator last)
   {
       while (first != last)
           delete (*first++).second;
   }

따라서, 위 4.4.1절에서 예로 든 코드는 메모리 누수 문제를 안고 있는 코드이다.

왜냐하면, set 컨테이너에 담긴 int*가 가리키는 메모리 영역을 반환하지 않았기 때문이다.

따라서, sequence_delete를 이용한 다음 코드를 끝에 추가해야 완벽한 프로그램이 된다.

   ...
   sequence_delete(set1.begin(), set1.end());
   sequence_delete(list1.begin(), list1.end());
   ...

4.4.3 2번 유의 사항에 대한 추가 예제

#include <iostream>
#include <vector>
#include <algorithm>

class object {
    char *str;
public:
    static int count;
    object() { str = 0; count++; }
    object(const object& o) {
        cout << "-- ctor called, ";
        str = new char[10]; strcpy(str, o.str); count++;
        cout << count << " object(s) remains." << endl;
    }
    object(const char *s) {
        cout << "-- ctor called, ";
        str = new char[10]; strcpy(str, s); count++;
        cout << count << " object(s) remains." << endl;
    }
    ~object() {
        cout << "-- dtor called, ";
        delete[] str; count--;
        cout << count << " object(s) remains." << endl;
    }

    friend ostream& operator<<(ostream& os, object o) { return os << o.str; }
    friend ostream& operator<<(ostream& os, object *o) { return os << o->str; }
};

int object::count = 0;

template <class ForwardIterator>
void sequence_delete(ForwardIterator first, ForwardIterator last)
{
    while (first != last)
        delete *first++;
}

void print(object *o) { cout << o << endl; }

int main()
{
    vector<object*> v;

    v.push_back(new object("obj1")); 
    v.push_back(new object("obj2")); 

    cout << "Print elements..." << endl;
    for_each(v.begin(), v.end(), print);

    cout << "Delete elements..." << endl;
    sequence_delete(v.begin(), v.end());

    return 0;
}

▶ 실행결과
-- ctor called, 1 object(s) remain(s).
-- ctor called, 2 object(s) remain(s).
Print elements...
obj1
obj2
Delete elements...
-- dtor called, 1 object(s) remain(s).
-- dtor called, 0 object(s) remain(s).

정적 클래스 멤버인 count는 object 객체의 갯수를 검사하기 위해서 사용되었다.

4.4.4 포인터 싸개(pointer wrapper)

#include <iostream>
#include <list>
#include <set>
#include <deque>
#include <algorithm>

// 다음에 정의한 class X의 객체에 대한 포인터를
// 여러 종류의 STL 컨테이너에 저장하려고 함.
class X {
    int i_;
public:
    X(int i) : i_(i) {  }
    X(const X& x) : i_(x.i_) { }
    ~X() { }

    X& operator=(const X& x) { i_ = x.i_; }
    int operator()() const { return i_; }
};

bool operator==(const X& x1, const X& x2) { return x1() == x2(); }
bool operator<(const X& x1, const X& x2) { return x1() < x2(); }

// STL 컨테이너에 저장할 wrapper 클래스
class XPtrWrapper {
    X* x_;
public:
    XPtrWrapper(X* x = 0) : x_(x) { }
    XPtrWrapper(const XPtrWrapper& xw) : x_(xw.x_) { }
    ~XPtrWrapper() { }

    XPtrWrapper& operator=(const XPtrWrapper& xw) { x_ = xw.x_; }
    const X* operator()() const { return x_; }  // for const XPtrWrapper
    X* operator()() { return x_; }              // for non-const XPtrWrapper
};

bool operator==(const XPtrWrapper& xw1, const XPtrWrapper& xw2)
{
    return (xw1() && xw2()) ? *xw1() == *xw2() : false;
}

bool operator<(const XPtrWrapper& xw1, const XPtrWrapper& xw2)
{
    return (xw1() && xw2()) ? *xw1() < *xw2() : false;
}

void print(const XPtrWrapper& xw) { cout << " " << (*xw())(); }

int main()
{
    // XPtrWrapper 5개를 배열에 저장(각각의 wrapper는 0,1,4,9,16를 가리킴)
    XPtrWrapper bucket[5];
    for(int i = 0; i < 5; i++)
        bucket[i] = XPtrWrapper(new X(i * i));
    random_shuffle(bucket, bucket + 5);

    // list로 XPtrWrapper들을 복사
    list<XPtrWrapper> list1;
    copy(bucket, bucket + 5, 
        back_insert_iterator<list<XPtrWrapper> >(list1)
    );

    // 출력
    cout << "List of XPtrWrapper: (";
    for_each(list1.begin(), list1.end(), print);
    cout << " )" << endl;

    // set으로 XPtrWrapper들을 복사
    // 앞에서도 말했지만, set을 선언할 때는 비교함수(comparator)를 반드시 지정
    set<XPtrWrapper, greater<XPtrWrapper> > set1;
    copy(list1.begin(), list1.end(), 
        insert_iterator<set<XPtrWrapper, greater<XPtrWrapper> > > 
            (set1, set1.begin())
    );

    // 출력
    cout << "Set of XPtrWrapper : [";
    for_each(set1.begin(), set1.end(), print);
    cout << " ]" << endl;

    // deque로 XPtrWrapper들을 복사
    deque<XPtrWrapper> deque1;
    copy(list1.begin(), list1.end(), 
        back_insert_iterator<deque<XPtrWrapper> > (deque1)
    );

    // 출력
    cout << "Deque of XPtrWrapper : (";
    for_each(deque1.begin(), deque1.end(), print);
    cout << " )" << endl;

    return 0;
}

▶ 실행결과
List of XPtrWrapper: ( 4 0 16 1 9 )
Set of XPtrWrapper : [ 16 9 4 1 0 ]
Deque of XPtrWrapper : ( 4 0 16 1 9 )

 

 

4.5 STL에 없는 컨테이너 타입들

전통적으로 많이 사용되고 있는 컨테이너 타입들중 표준 라이브러리에는 들어 있지 않은 것들이 꽤 있다. 그 이유는 대부분의 경우, 이미 제공된 컨테이너들을 적절하게 이용하면 보다 아주 광범위한 용도로 다양하게 사용될 수 있기 때문이다.

우선 tree 콜렉션이 없다. 그러나, set 타입은 내부적으로 이진 검색트리의 형태를 사용하여 구현되어 있다. tree를 이용하여 해결되는 많은 문제들은 set 데이터형으로 적절히 대체할 수 있다.

set 데이터 타입은 명시적으로 순서적이고, 순서를 매길수 없는 값들의 콜렉션(예를 들면, 복소수의 콜렉션)에 대해서는 set 연산(합집합,교집합)의 수행을 위한 어떤 대책도 마련되어 있지 않다. 그러한 경우에는 list를 대신 사용할 수 있는데, 이렇게 하려면, generic 알고리듬을 사용할 수 없기 때문에, 특별한 set 연산 함수를 작성해야할 필요가 생긴다.

다차원 배열도 없다. 그러나, vector를 원소로 하는 vector를 이용하면 된다.

그래프가 없다. 그렇지만, graph에 대한 표현은 맵을 원소로 하는 맵으로 만들어 낼 수 있다. 이런 타입의 구조는 9.3.2절의 예제 프로그램에서 설명한다.

sparse 배열도 없다. 이 문제에 대한 해결책은 9.3.2절에서 다룰 graph 표현 방식이 될 수 있겠다.

해쉬 테이블도 없다. 해쉬 테이블은 접근과 삭제 연산을 첨자 연산으로 바꿈으로써, amortized 상수 시간내에 접근,삽입,삭제가 가능하도록 한다. 그러나, 해쉬 테이블은 list나 set을 원소로 하는 vector나 deque로 만들어낼 수 있다. 이와 비슷한 예를 7.3절에서 radix 정렬 문제를 다룰 때 살펴보기로 하겠다.(이 예제는 값을 인덱스로 바꾸는 해쉬 함수는 가지고 있지 않다.)

간단히 말해서, 생각할 수 있는 모든 컨테이너 타입을 다 제공하지는 못하지만, 표준 라이브러리가 제공하는 컨테이너들을 응용하면 많은 문제들에서 필요로 하는 컨테이너들을 대부분 표현할 수 있고, 더 나아가 표준 라이브러리에서 제공하는 컨테니이들을 가지고, 새로운 컨테이너를 작성할 수도 있을 것이다.