Move Fast

개념

• 정의 (위키백과)

표준 템플릿 라이브러리(STL: Standard Template Library)는 C++을 위한 라이브러리로서 C++ 표준 라이브러리의 많은 부분에 영향을 끼쳤다. 이것은 알고리즘, 컨테이너, 함수자 그리고 반복자라고 불리는 네가지의 구성 요소를 제공한다.

STL은 컨테이너와 연관 배열 같은 C++을 위한 일반 클래스들의 미리 만들어진 집합을 제공하는데, 이것들은 어떤 빌트인 타입과도 그리고 어떤 사용자 정의 타입과도 같이 사용될 수 있다. STL 알고리즘들은 컨테이너들에 독립적인데, 이것은 라이브러리의 복잡성을 눈에 띄게 줄여주었다.

STL은 결과를 템플릿의 사용을 통해 달성한다. 이 접근법은 전통적인 런타임 다형성에 비해 훨씬 효과적인 컴파일 타임 다형성을 제공한다. 현대의 C++ 컴파일러들은 STL의 많은 사용에 의해 야기되는 어떤 추상화 패널티도 최소화하도록 튜닝되었다.

STL은 제네릭 알고리즘과 C++을 위한 데이터 구조체들의 첫 번째 라이브러리로서 만들어졌다. 이것은 다음의 네가지를 기초로 한다. 제네릭 프로그래밍, 효율성을 잃지 않은 추상화, 폰 노이만 구조 그리고 밸류 시멘틱스(value semantics)가 그것이다.

• 구성요소

  • 컨테이너(container): 데이터를 저장하는 객체의 집합으로, 연속 컨테이너(sequence container)와 연관 컨테이너(associative container)로 분류됨.

  • 반복자(iterator): 컨테이너에 저장된 객체를 참조하는 포인터.

  • 알고리즘(algorithm): 정렬, 삭제, 검색 등에 대한 함수를 제공

  • 함수 객체(function object): operator()를 오버로드하는 클래스의 인스턴스로, 함수처럼 동작하는 객체. C++에서는 사칙 연산과 관련해서 몇 가지 함수 객체를 제공함. 예를 들면, plus<자료형>()과 times<자료형>() 이 있음. STL의 알고리즘의 인자로 함수 객체를 넘길 수 있는데, 이는 C 언어에서 함수 포인터를 사용했을 때보다 훨씬 빠르게 동작함. 그 이유는 함수 포인터는 실행될 때까지 확인될 수 없기 때문에 인라인(inline)으로 만들어질 수 없으나, 함수 객체는 컴파일 시에 결정되기 때문에 컴파일러는 operator() 호출을 인라인으로 만들어 성능이 증가하기 때문임.

  • 어댑터(container adaptor): STL 구성 요소를 새로운 구성 요소로 보이게 하는 기능으로, 다른 컨테이너들을 사용하면서 특정한 인터페이스와 함께하는 컨테이너

  • 할당기(allocator): 컨테이너의 메모리 할당 정책을 담당

연속 컨테이너 (Sequence Container)

• 표준 연속 컨테이너들은 vector, deque, 그리고 list를 포함.

• vector<자료형>

  • STL에서 가장 많이 사용되는 컨테이너 라이브러리

  • C 배열과 같은 동적 배열로서 객체를 삽입하거나 제거할 때 자동으로 자신의 크기를 조정하는 능력을 갖는다.

  • vector의 end에 요소를 삽입하는 것은 상환 상수 시간(amortized constant time)을 필요로 한다.

  • 마지막 요소를 제거하는 것은 단지 상수 시간을 필요로 하는데, 크기 조정이 일어나지 않기 때문이다.

  • 처음 또는 중간에 삽입하거나 삭제하는 것은 뒤의 원소들을 뒤나 앞으로 옮겨야하므로 선형 시간이 든다.

  • bool 타입을 위한 특수화가 존재하는데 이것은 불린 값을 비트에 저장하기 위해 공간을 최적화한다.

  • 메모리 상에서 연속된 위치에 데이터를 저장하므로, memcpy()나 memset() 등의 함수를 이용하여 직접적인 데이터 수정 가능.

  • vector에서 제공하는 자주 쓰이는 멤버 함수로는 push_back(), pop_back(), front(), back() 이 있으며, 함수명에서 알 수 있듯이 뒤쪽에서만 데이터 삽입, 삭제가 가능함. 중간에 데이터를 수정하고 싶다면 다른 라이브러리를 사용해야 함.

  • 배열과의 차이점: 크기가 동적으로 변하며, 중간에 데이터 삽입 및 삭제가 가능.

  • 배열과의 공통점: 구현이 쉽고, 랜덤 접근(random access)이 가능.

  • 미리 크기를 알 수 있는 데이터 저장에 가장 적합하고, 크기가 가변적인 경우라도 뒤쪽에서만 데이터 삽입, 삭제가 빈번하게 발생할 경우 유용하게 사용됨. 그 외에도 랜덤 접근이 자주 발생하고 빠른 속도를 요구할 때 이용됨. 실제로 앞에서 삽입, 삭제가 많이 일어날 경우 다른 컨테이너 사용이 권장됨.

  • vector는 capacity() 함수를 통해 메모리 재할당 없이 최대 늘릴 수 있는 크기를 제공하며, 이는 size() 함수(=원소의 개수)와는 다른 용도임. 즉, 처음 할당 시 지정한 공간보다 넉넉하게 메모리를 잡기 때문에 미리 크기를 알 경우 메모리 재할당에 따른 추가 연산을 막을 수 있음.

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

int main() {
    cout << "Vector" << endl;
    vector<int> v;
    
    for (int i = 9; i > 0; i--) {
        v.push_back(i);
    }
    
    cout << v.front() << endl; // 9
    cout << v.back() << endl; // 1
    cout << v.size() << endl; // 9
    
    for (vector<int>::iterator iter = v.begin(); iter != v.end(); iter++) {
        cout << *iter << ", ";
    }
    cout << endl;
    
    // or
    for (auto it = v.begin(); it != v.end(); it++) {
        cout << *it << ", ";
    }
    cout << endl;
    
    v.pop_back();
    cout << v.back() << endl; // 2
    cout << v.empty() << endl; // 0 (= false)
    
    // 초기화되지 않은 경우 0으로 채워지지만, 이미 값이 있는 경우 크기만 줄인다.
    v.resize(3, 0);
    cout << v.size() << endl; // 3
    // 9, 8, 7
    for (auto it = v.begin(); it != v.end(); it++) {
        cout << *it << ", ";
    }
    cout << endl << "Vector2" << endl;
    
    vector<int> v2;
    v2.resize(5, 0);
    cout << v2.size() << endl; // 5
    for (auto it = v2.begin(); it != v2.end(); it++) {
        cout << *it << ", "; // 0
    }
    cout << endl;
    
    return 0;
}

• deque<자료형>

  • 앞, 뒤 모두에서 데이터 삽입 및 삭제가 가능.

  • 다른 기능들이 vector보다 성능이 떨어지기 때문에 자주 사용되지 않음.

  • vector와의 공통점은 메모리 상에 연속된 위치에 데이터가 저장되며, 중간 삽입 및 삭제가 용이하지 않다는 것. 즉, 멤버 함수가 제공되지 않음.

  • 대표적인 멤버 함수로는 push_front(), push_back(), pop_front(), pop_back(), front(), back() 이 있음.

• list<자료형>

  • 자료구조의 이중 연결 리스트를 템플릿으로 구현해 놓은 것으로, 중간에 데이터 삽입 및 삭제가 가장 빠름.

  • 메모리 상에서 데이터들이 흩어져서 저장되어 있으므로, vector나 deque처럼 연속된 메모리에 저장되는 컨테이너에 비해 읽는 속도가 굉장히 느림. 캐싱(caching) 작업을 할 때 인접한 메모리들도 함께 가져오기 때문에 list의 경우 캐싱으로 얻는 이점이 다른 컨테이너보다 적음. 또한, list는 각 엔트리마다 이전, 다음 엔트리를 가리키는 포인터를 저장해야 하므로 크기도 vector보다 커서 실제 메모리(물리 메모리) 상에 인접한 곳에 있어도 요소를 적게 가져오게 됨. 따라서 순회가 빈번한 경우 list 는 사용하지 않는 것이 좋음.

  • 느린 검색과 접근(선형 시간)을 갖지만, 한 번 위치가 찾아지면 빠른 삽입과 삭제가 가능(상수 시간).

  • 대표적인 멤버 함수로는 push_front(), push_back(), pop_front(), pop_back(), front(), back()가 있음.

  • 중간에 데이터를 삽입하는 함수로는 insert()가 있고, 삭제하는 함수로는 erase()가 있는데 매개변수에 따라 종류가 3가지로 나뉨.

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

int main () {
    list<int> mylist;
    list<int>::iterator it;

    // set some initial values:
    for (int i = 1; i < 6; ++i) mylist.push_back(i);       // 1 2 3 4 5

    it = mylist.begin();
    ++it;             // it points now to number 2              ^

    mylist.insert(it,10);                                  // 1 10 2 3 4 5

    // "it" still points to number 2                               ^
    mylist.insert(it, 2, 20);                              // 1 10 20 20 2 3 4 5

    --it;             // it points now to the second 20                ^

    vector<int> v(2, 30);
    mylist.insert(it, v.begin(), v.end());                 // 1 10 20 30 30 20 2 3 4 5
                                                           //                ^
    
    cout << "mylist contains:";
    for (it = mylist.begin(); it != mylist.end(); ++it)
        cout << ' ' << *it;
    cout << '\n';

    return 0;
}

/*
mylist contains: 1 10 20 30 30 20 2 3 4 5
 */

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

int main ()
{
    list<int> mylist;
    list<int>::iterator it1, it2;

    // set some values:
    for (int i=1; i<10; ++i) mylist.push_back(i * 10);

                                   // 10 20 30 40 50 60 70 80 90
    it1 = it2 = mylist.begin();    // ^^
    advance(it2, 6);               // ^                  ^
    ++it1;                         //     ^              ^

    it1 = mylist.erase(it1);       // 10 30 40 50 60 70 80 90
                                   //     ^           ^

    it2 = mylist.erase(it2);       // 10 30 40 50 60 80 90
                                   //     ^           ^

    ++it1;                         //        ^        ^
    --it2;                         //        ^     ^

    mylist.erase(it1, it2);        // 10 30 60 80 90
                                   //        ^

    cout << "mylist contains:";
    for (it1=mylist.begin(); it1!=mylist.end(); ++it1)
        cout << ' ' << *it1;
    cout << '\n';

    return 0;
}

/*
mylist contains: 10 30 60 80 90
 */

연관 컨테이너 (Associative Container)

• 키(Key)와 값(Value)의 짝(pair)으로 이루어진 자료구조(아닌 것도 있으나 자주 사용되지 않음)를 구현한 컨테이너.

• 저장된 자료의 순서와 상관없이 특정 기준에 맞게 저장(주로 키 값의 정렬 순서대로 저장).

• 간단한 연관 컨테이너로 pair와 tuple이 있음.

• pair<자료형, 자료형>

  • 데이터 요소의 2-튜플 또는 객체들로(고정된 순서에 따라 변수명.first 그리고 변수명.second로 접근 가능) 이루어짐.

  • STL 내부적으로 많이 사용되며, 함수의 리턴 값이 2개가 필요할 경우 사용됨.

  • map 또는 hash_map 에서 할당된 객체들의 배열은 기본 값으로 pair 타입을 가지며, 배치 및 복사 그리고 비교할 수 있음.

  • 비교 시 모든 first 요소들이 유니크 키로서 동작하고 second 요소는 키에 매핑되는 값 혹은 객체로 동작함.

  • 다른 컨테이너에 자료형으로 pair를 쓰는 경우 make_pair<자료형, 자료형>(값, 값) 함수로 pair 객체를 만들어서 컨테이너에 저장함.

  • C++11 부터 emplace_back() 이라는 함수를 제공하여 객체를 받는 대신, 객체의 생성자의 매개변수를 받아 vector 내부에서 직접 객체를 생성하므로 임시 객체를 생성하고 파괴 및 복사하는 추가 연산이 필요 없음.

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

int main() {
    vector<pair<int, double> > v;
    v.push_back(make_pair(3, 5.0)); // same as "v.emplace_back(3, 5.0);"

    pair<int, double> p;
    p.first = 10;
    p.second = 15.5;
    v.push_back(p);
    
    cout << p.first << ", " << p.second << endl;
    
    return 0;
}

• tuple<자료형, 자료형, ..., 자료형>

  • 3개 이상의 값을 반환하거나 저장할 때 사용되는 컨테이너.

  • pair와 유사하게 make_tuple<자료형, 자료형, ..., 자료형>(값, 값, ..., 값) 함수로 객체를 생성할 수 있음.

  • 그러나 값을 꺼내올 경우 get<인덱스>(변수명) 를 사용하여야 함. (멤버 함수 아님.)

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

int main() {
    tuple<int, double, bool> T(10, 15.5, true);
    
    // or
    T = make_tuple<int, double, bool>(10, 15.5, true);
    
    cout << get<0>(T) << endl; // 10
    cout << get<1>(T) << endl; // 15.5
    cout << get<2>(T) << endl; // 1 (=true)
    
    return 0;
}

• 표준 연관 컨테이너들은 set, multiset, map, multimap, unordered_set, unordered_map, unordered_multiset 그리고 unordered_multimap를 포함하며, 모두 정렬된 구조.

• 정렬되지 않는 경우 명칭이 "unordered_컨테이너명"가 됨.

• 보통 키를 기준으로 정렬하기 때문에 중복된 키 값을 입력할 수 없으나, mutli-가 붙은 컨테이너들은 중복된 키를 가질 수 있음.

• map<Key 자료형, Value 자료형>

  • 하나의 데이터 아이템(키)에서 다른 것(값)으로 매핑을 허용.

  • 키의 타입은 반드시 비교 연산 < 또는 명시된 커스텀 비교자를 통해 구현되어야 함. (map<자료형, 자료형, 비교자> 로 선언)

  • 이러한 비교 연산 또는 비교자 함수는 반드시 strict weak ordering을 보장해야 하며, 아니면 행위가 정의되지 않음.

  • 일반적으로 자가 균형 이진 탐색 트리(Red-Black Tree)를 사용해서 구현됨.

  • 자주 사용되는 멤버 함수로는 insert(), erase(), find(), count() 등이 있음.

  • 정렬된 상태로 많은 데이터를 저장하고, 빠른 검색이 필요하며, 삽입 및 삭제 연산이 빈번하게 일어나지 않는 경우에 굉장히 효율적으로 사용됨.

  • multimap 같은 키(Key)로 여러 개의 값(Value) 입력 가능. #include <map>

  • unordered_map C++11에서 해시 테이블로 구현된 것으로, 정렬되지 않으나, 검색 속도가 빠름. #include <unordered_map>

  • unordered_multimap 같은 키(Key)로 여러 개의 값(Value) 입력 가능하며, 정렬되지 않은 상태로 저장. #include <unordered_multimap>

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

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

    // How to insert
    m.insert(make_pair<int, double>(5, 10.1));
    m.insert(pair<int, double>(3, 15.5));
    m.insert({7, 8.123}); // using initializer_list
    m.emplace(1, 5.5); // C++11
    m[123] = 0.3145723;


    // How to read
    cout << m[3] << endl; // 15.5

    for (auto it = m.begin(); it != m.end(); it++) {
        cout << "(" << it->first << ", " << it->second << ")" << endl;
    }

    // How to delete
    map<int, double>::iterator it = m.find(3);
    m.erase(it);    // erasing by iterator
    m.erase(1);     // erasing by key
    it = m.find(7);
    m.erase(it, m.end()); // erasing by range

    cout << "After deleting ..." << endl;
    for (auto it = m.begin(); it != m.end(); it++) {
        cout << "(" << it->first << ", " << it->second << ")" << endl;
    }

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
15.5
(1, 5.5)
(3, 15.5)
(5, 10.1)
(7, 8.123)
(123, 0.314572)
After deleting ...
(5, 10.1)
 */

• set<Key 자료형>

  • 키(Key)만으로 이루어진 이진트리 자료구조로, map과 마찬가지로 자가 균형 이진 탐색 트리(Red-Black Tree)로 구현됨.

  • 수학의 집합(set)을 표현한 자료구조이기 때문에, 집합 연산(union, intersection, difference, symmetric difference) 그리고 포함 테스트를 제공.

  • 키의 타입은 반드시 비교 연산 < 또는 명시된 커스텀 비교자 함수를 통해서 구현되어야 함.

  • 이러한 비교 연산 또는 비교자 함수는 반드시 strict weak ordering을 보장해야 하며, 아니면 행위가 정의되지 않음.

  • map과 마찬가지로 자주 사용되는 멤버 함수로는 insert(), erase(), find() 등이 있음.

  • 정렬된 상태로 많은 데이터를 저장하고 빠른 검색 속도를 필요로 하는 경우 (특정 값의 유무를 파악해야 할 때 등) 효율적으로 사용됨.

  • mutliset 중복 요소들을 허용. #include <set>

  • unordered_set C++11에서 해시 테이블로 구현됨. 정렬되지 않은 대신 검색 속도가 빠름. #include <unordered_set>

  • unordered_mutliset 중복 요소 허용 및 정렬되지 않으나 빠른 검색 속도 제공. #include <unordered_set>

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

int main() {
    set<int> s{9, 7, 5, 1, 3}; // 1, 3, 5, 7, 9
    s.insert(4); // 1, 3, 4, 5, 7, 9
    s.insert(4); // no new element inserted.

    for (auto it = s.begin(); it != s.end(); it++)
        cout << (*it) << ", ";
    cout << endl;

    auto found = s.find(5);
    if (found != s.end())
        cout << "Found:" << *found << endl;

    cout << endl << "After inserting 123:" << endl;
    s.insert(found, 123);
    for (auto it = s.begin(); it != s.end(); it++)
        cout << (*it) << ", ";
    cout << endl;

    cout << endl << "After inserting an array:" << endl;
    int arr[] = {20, 21, 23, 25};
    s.insert(arr, arr + 4);
    for (auto it = s.begin(); it != s.end(); it++)
        cout << (*it) << ", ";
    cout << endl;

    cout << endl << "After erasing:" << endl;
    found = s.find(4);
    s.erase(found);             // erasing by iterator
    s.erase(9);                // erasing by key
    found = s.find(23);
    s.erase(found, s.end());    // erasing by range
    for (auto it = s.begin(); it != s.end(); it++)
        cout << (*it) << ", ";
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
1, 3, 4, 5, 7, 9,
Found:5

After inserting 123:
1, 3, 4, 5, 7, 9, 123,

After inserting an array:
1, 3, 4, 5, 7, 9, 20, 21, 23, 25, 123,

After erasing:
1, 3, 5, 7, 20, 21,
 */

반복자(Itrerator)

• 컨테이너 내 객체를 참조하는 포인터로, 컨테이너명<자료형>::iterator 변수명 = ... 으로 선언하여 사용함.

• ++나 --, 그리고 -> 또는 *과 같은 포인터 연산이 대부분 그대로 사용됨.

• 우항에는 일반적으로 컨테이너명.begin(); 이 들어가는데, begin()과 end()는 0번 인덱스와 마지막 인덱스 + 1의 위치를 참조하고 있음.

• 반대로 순회하길 원할 경우 rbegin()과 rend()를 활용하면 됨.

• 반복자의 종류로는 Input, Output, Forward, Bidirectional, Random Access가 있음.

  • Input과 Output은 입/출력을 담당하는 최소한의 기능만을 가진 반복자.

  • Forward와 Bidirectional은 순회하는 방향에 따라 지어진 이름으로, 각각 순방향과 양방향을 의미함. 즉, bidirectional 반복자는 양방향으로 이동하면서 데이터를 참조할 수 있음.

  • Random Access는 말 그대로 무작위로 데이터에 접근할 수 있는 반복자.

  • 포함 범위: Input/Output < Forward < Bidirectional < Random Access

• 각 컨테이너의 반복자를 반환하는 멤버 함수로 begin(), end(), rbegin(), rend(), cbegin(), cend(), crbegin(), crend()가 있음.

  • begin()과 end()는 순방향으로 데이터를 조회하기 위한 함수.

  • rbegin()과 rend()는 반대로 순회(역방향)하기 위해 각각 마지막 원소와 첫 원소 - 1 의 위치를 참조함.

  • cbegin()과 cend()는 auto 키워드를 사용할 경우 상수 타입(const)의 반복자를 받지 못하는 문제를 개선하기 위해 C++11부터 도입된 것으로 상수 반복자를 반환함.

  • crbegin()과 crend()는 역방향 상수 반복자를 반환.

• auto 키워드 사용 시 상수 반복자를 반환하는 멤버 함수를 사용해야 함.

  • auto it = v.cbegin();