이번 시간에는 STL의 Container에 대해서 알아보겠습니다.

STL Container 특징

1. Container basic

  • 시퀀스 컨테이너 : 요소가 삽입된 순서대로 놓여있는 컨테이너

    • list, vector, deque, forward_list, array

  • 연관 컨테이너

    • 삽입 순서와 상관없이 규칙을 가지고 요소를 보관
    • set, muti-set, map, multi-map, unordered_set, unordered-multiset, unordered_map, unordered_multimap

  • Adapter container

    • stack, queue, priority_queue

2. 공통 특징

  • 값을 보관함
  • 멤버 함수 뿐 아니라 member type 제공
  • 반복자 제공
  • 제거와 리턴을 동시에 하지 않음 ( .back()과 .pop_back() )

3. Policy base design

  • 메모리 할당 방식을 제공(Allocator)
#include <iostream>
using namespace std;

template<typename T,
         typename Allocator = allocator<T> > class vector
{
    //....
    Allocator ax;
public:
    void push_back(const T& a)
    {
        // 메모리 할당이 필요하다.
        // new, malloc, 공유 메모리, pool,
        T* p = ax.allocate(1);

        ax.deallocate(p, 1);

    }
};

int main()
{
    vector<int, MyAlloc> v;

    v.push_back(10);
}
  • 단위 전략 디자인 제공
#include <iostream>
#include <string>
using namespace std;

#include <cctype>

struct ci_char_traits : public std::char_traits<char>
{
    static char to_upper(char ch)
    {
        return std::toupper((unsigned char) ch);
    }
    static bool eq(char c1, char c2) {
         return to_upper(c1) == to_upper(c2);
     }
    static bool lt(char c1, char c2) {
         return to_upper(c1) <  to_upper(c2);
    }
    static int compare(const char* s1, const char* s2, size_t n) {
        while ( n-- != 0 ) {
            if ( to_upper(*s1) < to_upper(*s2) ) return -1;
            if ( to_upper(*s1) > to_upper(*s2) ) return 1;
            ++s1; ++s2;
        }
        return 0;
    }
    static const char* find(const char* s, int n, char a) {
        auto const ua (to_upper(a));
        while ( n-- != 0 )
        {
            if (to_upper(*s) == ua)
                return s;
            s++;
        }
        return nullptr;
    }
};

using ci_string = std::basic_string<char, ci_char_traits>;

int main()
{
    ci_string s1 = "abcd";
    ci_string s2 = "ABCD";

    if ( s1 == s2 )
        cout << "same" << endl;
    else
        cout << "not same" << endl;
}

Sequence(선형) Contianer

1. 선형 컨테이너들은 인터페이스가 동일하지만, vector는 push_front를 제공하지 않는 등 제공 유/무 여부가 다름

#include <iostream>
#include <list>
#include <vector>
#include <deque>
#include <forward_list>
#include <array>
using namespace std;

int main()
{
    list<int> s;
    //deque<int> s;
    //vector<int> s;

    s.push_front(10);
    s.push_back(20);

    cout << s[0] << endl;
}

2. Vector

  • 생성/삽입/접근
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    // vector 생성
    vector<int> v1;
    vector<int> v2(10);
    vector<int> v3(10, 3);
    vector<int> v4(v3);

    vector<int> v5 = {1,2,3,4};
    vector<int> v6{1,2,3,4};

    vector<int> v7(10,0); // 10 개를 0으로 초기화
    vector<int> v8{10,0}; // 2개를 10, 0 으로 초기화

    //----------------------
    vector<int> v;
    //v.push_front(10); // error.
    v.push_back(10);
    v.push_back(20);
    //v.insert( 위치,  30);

    v.insert( begin(v)+1,  30); // 10 30 20

    // 요소 꺼내기
    int n = v.front();
    int n1 = v[0];

    int x[5] = { 1,2,3,4,5};

    v.assign( x, x+5);

    //sort( begin(v), end(v));

    v[100] = 10;   // 예외 없이 runtime error
    //v.at(100) = 10; // 예외 발생

    for ( int i = 0; i < v.size(); i++)
        v[i] = 10; // ok
        v.at(i) = 10; // !!
}
  • size와 capacity(메모리사용량)
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> v(10,0);

    v.resize(7);    // ?

    cout << v.size()     << endl; // 7
    cout << v.capacity() << endl; // 10

    v.push_back(0);
    cout << v.size()     << endl; // 8
    cout << v.capacity() << endl; // 10

    v.pop_back();
    cout << v.size()     << endl; // 7
    cout << v.capacity() << endl; // 10

    v.shrink_to_fit();
    cout << v.size()     << endl; // 7
    cout << v.capacity() << endl; // 7

    v.push_back(0);

    cout << v.size()     << endl; // 8
    cout << v.capacity() << endl; // 컴파일러마다 다름
}

3. std::array

  • vector는 heap을 사용하지만, std::array는 일반 배열처럼 stack 사용

  • 동적으로 크기 변경 불가

4. 객체 삽입시 최적화 관련

#include <iostream>
#include <vector>
using namespace std;

class Point
{
    int x, y;
public:
    Point(int a, int b) : x(a), y(b){ cout << "Point()" << endl; }

    ~Point() { cout << "~Point()" << endl;}

    Point(const Point& ) { cout << "Point(const Point&)" << endl;}
};

int main()
{
    vector<Point> v;

    // 1.
    //Point p1(10, 20);
    //v.push_back(p1 );

    // 2. 임시객체로 넣기
    //v.push_back( Point(10,20));

    // 3. 객체 자체를 vector가 만들게 한다.
    // 객체를 전달하지 말고, 생성자 인자를 전달한다.
    //v.emplace_back( 10, 20 ); // emplace_front()
                                // insert ==> emplace


    Point p1(10, 20); // 객체 생성
    // p1 사용...

    //v.push_back(p1 );
    v.push_back( move(p1) );

    // p1은 이제 필요 없다.

    cout << "-----------" << endl;
}

Adapter container의 원리

1. stack을 만드는 2가지 방법

  • stack을 처음 부터 새롭게 구현
  • list의 인터페이스를 변경해서 stack처럼 동작하도록 처리
#include <iostream>
using namespace std;

// list 가 제공된다.
#include <list>
/*
// 그런데 stack 이 필요하다.
template<typename T, typename C = deque<T> > class stack
{
    C st;
public:
    inline void push(const T& a) { st.push_back(a);}
    inline void pop()            { st.pop_back();}
    inline T&   top()            { return st.back();}
    inline bool empty()          { return st.empty();}
};
*/
#include <vector>
#include <deque>
#include <stack>

int main()
{
//    stack<int, list<int, MyAlloc<int>> > s3;

    stack<int> s2;
    stack<int, vector<int>> s1;
    stack<int, list<int>> s;

    s.push(10);
    s.push(20);

    cout << s.top() << endl; // 20
    s.pop();

    cout << s.top() << endl; // 10
}
  • STL의 우선순위 큐, deque 등도 비슷한 방법으로 구현됨

Associative container

1. set

  • STL에서 tree를 쓰는 대부분의 컨테이너는 red black tree 사용
#include <iostream>
#include <set>
#include <functional>
using namespace std;

int main()
{
    //set<int> s;
    set<int, greater<int> > s;

    //s.push_front(10); // error
    s.insert(30);
    s.insert(40);   // < 연산으로 비교, >
    s.insert(20);
    s.insert(10);
    s.insert(45);
    s.insert(25);

    // 알고리즘의 find를 쓸 경우 선형 검색 -> 비권장, 성능 나쁨
    //auto p2 = find( begin(s), end(s), 10);
    //cout << *p2 << endl;

    auto p2 = s.find(10); // 이진 검색.
    cout << *p2 << endl;

    auto p = begin(s);

    //*p = 10;
    while( p != end(s))
    {
        cout << *p << endl;
        ++p;
    }
}
  • 중복 삽입시
#include <iostream>
#include <set>
using namespace std;

int main()
{
    //set<int> s;

    multiset<int> s;

    s.insert(30);
    s.insert(40);
    s.insert(20);
    s.insert(10);
    s.insert(45);
    s.insert(25);

    // set : pair
    // multiset : iterator
    auto ret = s.insert(20);

    //pair<set<int>::iterator, bool> ret = s.insert(20);

//    if ( ret.second == false )
//        cout << "fail" << endl;

    for( auto n : s)
        cout << n << endl;
}

2. map

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main()
{
    map<string, string> m;

    // 1. pair 만들어서 insert
    pair<string, string> p1("월요일","mon");
    m.insert( p1 );

    // 2. make_pair
    m.insert( make_pair("화요일","tue"));

    // 3. [] 연산
    m[ "수요일"] = "wed";

    cout << m[ "월요일"] << endl; // "mon"
    cout << m[ "토요일"] << endl; // 첨자로 접근시 없으면 : make_pair("토요일", "") 항목추가

    auto ret = m.find("일요일");
    if ( ret == m.end())
        cout << "fail" << endl;
}

3. unordered 컨테이너들

  • 내부적으로 hash table 사용
  • 표준에서 제공하는 hash function
#include <iostream>
#include <string>
#include <functional>
using namespace std;

int main()
{
    hash<int> hi;
    hash<double> hd;
    hash<string> hs;

    cout << hi(50) << endl;
    cout << hd(3.4) << endl;
    cout << hs("hello") << endl;
}