[모던C++입문] 4.1 표준 템플릿 라이브러리

라이브러리

4.1 표준 템플릿 라이브러리

• 표준 템플릿 라이브러리(Standard Template Library, STL)는 기본 라이브러리
• Alex Stepanov,David Musser가 만든 STL대부분은 C++표준 라이브러리의 일부가 됨
• Matt Austern 은 STL의 핵심 개발자
• Josuttis는 라이브러리 튜토리얼을 작성

도입 예제

• 컨테이너는 개체를 포함하는 클래스
• 대표적을 vector와 list 클래스가 있다.

std::vector<double> vec;
std::list<double>   lst;

double vec_sum = std::accumulate(begin(vec), end(vec), 0.0);
double lst_sum = std::accumulate(begin(lst), end(lst), 0.0);

반복자

반복자의 종류

• InputIterator : (한번만) 참조된 항목을 읽는 반복자 [입력 반복자]
• OutputIterator : (한번만) 참조된 항목을 쓰는 반복자 [출력 반복자]
• ForwardIterator : opertator++를 제공 [순방향 반복자]
• BidirectionalIterator : operator++과 operator--를 제공 [양방향 반복자]
• RandomAccessIterator : operator[]를 제공 [임의 접근 반복자]

반복자로 작업하기

using namespace std;

std::list<int> lst = {3, 5, 9, 7};      //C++11
//C++03
for(list<int>::iterator it = lst.begin(); it != lst.end(); ++it)
{
    int i = *it;
    cout << i << endl;
}

//모던C++
for(auto it = begin(lst), e = end(lst); it != e; ++it)
{
    int i = *it;
    cout << i << endl;
}

for(const auto it = begin(lst), e = end(lst); it != e; ++it)    //오류
//begin()과 end()는 상수 리스트일때만 const_iterator를 반환

const std::list<int>& lstr = lst;
for(auto it = begin(lstr), e = end(lstr); it != e; ++it)        //가능

for(auto it = begin(const_cast<const std::list<int>&>(lst)),
e = end(const_cast<const std::list<int>&>(lst); it != e; ++it)  //가능

//but C++14에선 cbegin과 cend를 도입하였다
for(auto it = cbegin(lst); it != cend(lst); ++it)

//다음의 경우 auto는 전체를 순환하는 역참조된 반복자
for(auto i : lst)
    cout << i << endl;

//i를 복사하는 오버헤드를 피할수 있다
for(auto& i : lst)
    cout << i << endl;

//lst가 상수(const) 리스트 인경우
for(const auto& i : lst)
    cout << i << endl;

동작

• iterator 라이브러리는 advance와 distance 함수를 제공
• advance(it, n) 동작은 반복자 it를 n번 증가
• it+n은 it를 변경하지 않으며 RandomAccessIterator에서만 동작
• distance(it1, it2) 동작은 두 반복자 사이의 거리를 반환

컨테이너

벡터

• std::vector는 c배열과 유사하게 데이터를 연속적으로 저장
• c배열은 스택에 저장되지만 vector는 힙에 상주한다
• 벡터는 첨자 연산자를 제공, 배열 스타일의 알고리즘을 사용
• capacity를 통해 사용 가능한 공간을 알수 있다.
• 벡터의 이미 예약된 공간을 채우는 경우 속도가 빠르다.
• 많은 메모리를 할당하고 모든 데이터를 복사하는 경우 속도가 느리다.
• resize(n)은 벡터의 크기를 n으로 맞춘다.
• resize로 크기를 조정해도 메모리를 해제하지 않음
• C++11에 추가된 shrink_to_fit 함수를 통해 용량을 실제 벡터 크기로 줄임

vector<int> v = {3, 4, 7, 9};
auto it = find(v.begin(), v.end(), 4);
cout << "After " << *it << " comes " << *(it+1) << endl;
auto it2 = v.insert(it+1, 5);   //2번째 위치에 값 5를 삽입
v.erase(v.begin());             //1번째 위치에 있는 항목을 지움(3)
cout << "size = " << v.size() << ", capacity = " << v.capacity() << endl;
v.shrink_to_fit();              //여분 항목 삭제
v.push_back(7);
for(auto i : v)
    cout << i << ", ";
cout << endl;

vector<matrix> v;
v.push_back(matrix(3.7));       //3*7 행렬을 바깥에서 만들어 추가한다
v.emplace_back(7.9);            //7*9 행렬을 안에서 만들어 추가한다
//emplace_back을 사용하면 복사, 이동 작업과 일부 메모리 할당/해제를 절약 가능

• 컴파일시 벡터의 크기를 알고 있고, 크기가 변하지 않으면 array를 사용하자
• 스택에 상주하므로 보다 효율적이다.(move및 swap같은 얕은 복사 작업은 제외)

양쪽으로 사용할 수 있는 큐

• deque(double-ended queue 의 약어)는 여러 각도에서 접근 가능
  • FIFO(First in First out) 큐
  • LIFO(Last in First out) 큐
  • 앞쪽에서 빠른 삽입을 하는 vector의 일반화
• deque 항목은 절대로 재배치 되지 않는다.
• 복사 또는 이동 비용을 절약하고 복사 이동이 불가능한 타입도 저장 가능

리스트

• list 컨테이너는 링크르 리스트
• n번쨰 항목에 직접 접근할 수 없음
• vector와 deque에 비해 같은 장점은 중간의 삽입 삭제 비용이 좀더 저렴하다

셋과 멀티셋

• set 컨테이너의 목적은 집합에 속하는 값 정보를 저장
• set항목은 내부적으로 트리로 정렬되어 O(n)의 시간복잡도로 접근 가능
• find와 count로 검사 가능
• set은 중복된 값을 저장하지 않는다.
• 중복된 값을 넣고 싶다면 multiset을 사용하자

맵과 멀티맵

• map은 연관 컨테이너로 값이 키(key)와 연관된다.
• 키는 순서가 있는 모든 타입을 가질수 있음
• 순서는 operator< 를 통해 정렬된다.
• map의 value_type은 pair<keytype, valuetype> 이다.
• 키가 여러값을 연관되게 하려면 multimap을 사용
• 중복된 값을 lower_bound와 upper_bound를 통해 반복문을 수행할 수 있다.

해시 테이블

• 해시테이블은 단일 항목에 접근하는데 O(1) 시간복잡도는 가짐
• hash라는 이름대신 unordered를 사용 (unordered_map<key, value>)

알고리즘

• 헤더 파일

시퀀스를 수정하지 않는 연산

//RandomAccessIterator가 필요
vector<int> seq = { 3, 4, 7, 9, 2, 5, 7, 8 };
auto it = find(seq.begin(), seq.end(), 7);      //첫번째 7
auto end = find(it + 1, seq.end(), 7);          //두번째 7
for(auto past = end+1; it != past; it++)
    cout << *it << " ";
cout << endl;

//ForwardIterator가 필요
list<int> seq2 = { 3, 4, 7, 9, 2, 5, 7, 8 };
auto it = find(seq2.begin(0, seq2.end(), 7), it2 = it;  //첫번째 7
it2++;
auto end = find(it2, seq.end(), 7);         //두번째 7
end++;
for(; it != end; ++it)
    cout << *it << " ";
cout << endl;

//find_if는 특정 조건에 해당하는 첫번째 항목을 검색한다
//단일값 비교 대신 bool값을 반환하는 함수인 술어(predicate)를 계산
bool check(int i) { return i > 4 && i < 7; }
int main()
{
    list<int> seq = {3,4,7,9,2,5,7,8};
    auto it = find_if(begin(seq), end(seq), check);
    cout << *it << endl;
}

시퀀스를 수정하는 연산

//copy함수는 호출전에 충분한 공간을 확보해야함
vector<int> seq = {3,4,7,9,2,5,7,8};
v.resize(seq.size());      
copy(seq.begin(), seq.end(), v.begin());

//unique함수는 중복된 항목을 제거한다
//unique함수는 시퀀스가 정렬되어있어야 한다는 전제조건이 필요하다
sort(seq.begin(), seq.end());
auto it = unique(seq.begin(), seq.end());
seq.resize(distance(seq.begin(), it));

정렬 연산

• sort 함수는 기본적으로 < 연산자를 사용하지만 람다 표현식등으로 사용자 정의 함수 사용 가능

vector<int> seq = {3,4,7,9,2,5,7,8,3,4,3,9};
sort(seq.begin(), seq.end(), [](int x, int y) { return x > y; });

수치연산

• STL의 수치연산은 헤더에 있다
• iota는 모든항목에 지정한 값을 기준으로 1씩 증가하는 값을 연속적으로 채운 시퀀스를 생성
• accumulate는 시퀀스의 합을 계산 사용자 정의 함수 가능
• inner_product는 내적을 수행
• partial_sum은 부분의 합을 계산
• adjacent_difference는 앞 항목과의 차이를 계산

    std::vector<float> v = { 3.1, 4.2, 7, 9.3, 2, 5, 7, 8, 3, 4 }, w(10), x(10), y(10);
    iota(w.begin(), w.end(), 12.1);                         //12.1, 13.1, 14.1, ..., 21.1
    partial_sum(v.begin(), v.end(), x.begin());             //3.1, 7.3, 14.3, 23.6, ..., 52.5
    adjacent_difference(v.begin(), v.end(), y.begin());     //3.1, 1.1, 2.8, 2.3, ..., 1.0

    float alpha = inner_product(w.begin(), w.end(), v.begin(), 0.0);
    float sum_w = accumulate(w.begin(), w.end(), 0.0f),
        prodect_w = accumulate(w.begin(), w.end(), 1.0f, [](float x, float y) { return x * y; });

복잡도

• O(1) : swap, iter_swap
• O(logN) : lower_bound, upper_bound, squal_range, binary_search, push_heap, pop_heap
• O(N logN) : inplace_merge, stable_partition, 모든 정렬 알고리즘
• O(N^2) : find_end, find_first_of, serarch, search_n
• O(n) : 모든 알고리즘

반복자를 넘어서

• 안좋은 케이스
  • 끝을 가리키는 반복자가 먼저온다
  • 다른 컨테이너의 반복자이다.
  • 반복자가 더 큰 반복단계를 만들어 끝을 가리키는 반복자를 방문하지 못함