8 분 소요

시퀀스 컨테이너

요소들을 순차 저장합니다.

항목 내용
vector 타입이 동일한 요소를 연속적인 메모리 공간에 관리합니다.
배열과 유사하며, 요소 삽입/삭제에 비효율적이고, 랜덤 접근을 지원합니다.
list 타입이 동일한 요소를 연결된 리스트로 관리합니다.
요소 삽입/삭제에 최적화되어 있으며, 양방향 순차 접근 지원하고, 랜덤 접근은 불가능합니다.
queue 타입이 동일한 요소를 선입선출 방식으로 관리합니다.
front()시 선입된 요소 반환합니다.
내부적으론 deque으로 구현됩니다.
stack 타입이 동일한 요소를 후입선출 방식으로 관리합니다.
deque 양방향에서 입출력이 가능한 queue입니다. 앞과 뒤에서 요소를 넣거나 뺄 수 있습니다.
양쪽 입력/삭제가 list와 효율이 같으며 랜덤 접근은 vector와 효율이 같습니다.
중간 입출력은 vector와 같이 비효율적입니다.
priority_queue 우선 순위에 따라 정렬된 queue입니다.
top()시 가장 큰 요소 반환하며 내부적으론 vector로 구현됩니다.
array (C++11~) 기존 C스타일의 배열처럼 연속된 메모리를 사용하는 컨테이너 입니다. C스타일 배열처럼 컴파일 타임에 크기가 결정되어 스택에 할당되므로, 힙에 할당되는 vector 보다 성능이 좋습니다.
forward_list (C++11~) 단방향 리스트여서 양방향 리스트인 list보다 요소 관리 공간을 작게 차지하며, push_front()로 요소의 앞쪽 방향으로 리스트를 구성합니다.

연관 컨테이너

요소의 대소 비교가 필요하며, Key로 정렬하여 관리합니다. 따라서 Key로 사용되는 타입은 bool operator <(const T& other); 가 구현되어 있어야 합니다.

항목 내용 Key 조건
map Key - Value 쌍으로 관리하며, pair를 요소로 사용합니다.(pair 참고)
이진 트리 탐색으로 요소를 탐색(O(logN))하며 요소 삽입시 <에 의해 정렬됩니다. 삽입되는 Key는 유일하며, 첨자 연산이 지원됩니다.		 < 구현
multimap map과 동일합니다.
중복 Key를 허용하며, 첨자 연산은 지원하지 않습니다.		 < 구현
set Key만 요소로 사용합니다.
이진 트리 탐색으로 요소 탐색(O(logN))하며, 요소 삽입시 <에 의해 정렬됩니다. 삽입되는 Key는 유일합니다.		 < 구현
multiset set과 동일합니다.
중복 Key허용합니다.		 < 구현
unordered_map, unordered_multimap, unordered_set, unordered_multiset (C++11~) 정렬되지 않은 컨테이너로서, 해시값(Digest)을 사용하는 해시 컨테이너 입니다. == 구현
hash()

(C++11~) const_iterator 지원

기존의 컨테이너에서 const_iterator를 지원했습니다만, 다른 함수에서 지원하지 않았기에 사용성이 좀 떨어졌습니다.

예를들어 vector의 insert()함수는 다음처럼 iterator를 전달받습니다.

1

iterator insert(iterator position, const value_type& x);

따라서, 다음처럼 find()한 const_iterator를 insert()함수에 전달할 수 없습니다.

1
2
3
4
5
6

std::vector<int> v;
v.push_back(1);
v.push_back(2);

std::vector<int>::const_iterator const_itr = std::find(v.begin(), v.end(), 1); // v를 수정하지 않으므로 const_iterator로 받습니다.
v.insert(const_itr, 0); // (X) 컴파일 오류. const_itr 앞에 0을 삽입하려고 했지만 iterator를 전달해야 합니다.

그래서 어쩔수 없이 그냥 iterator를 사용할 수 밖에 없었습니다.

1
2
3
4
5
6

std::vector<int> v;
v.push_back(1);
v.push_back(2);

std::vector<int>::iterator itr = std::find(v.begin(), v.end(), 1); // (△) 비권장. v를 수정하지 않아 const_iterator로 받고 싶지만, insert 함수에서 사용하기 위해 iterator로 받습니다.
v.insert(itr, 0); // (△) 비권장. insert() 함수가 const_iterator가 아닌 iterator를 사용하므로, 어쩔수 없이 iterator를 전달합니다.

C++11 부터는 const_iterator 지원이 강화되어 cbegin(), cend(), crbegin(), crend()가 추가되었고, insert(), erase()등의 멤버 함수에서 사용할 수 있습니다.

따라서 상기 코드를 다음과 같이 cbegin(), cend()과 insert()를 이용하여 구현할 수 있습니다.

1
2
3
4
5
6
7
8

std::vector<int> v;
v.push_back(1);
v.push_back(2);

std::vector<int>::const_iterator const_itr = std::find(v.cbegin(), v.cend(), 1); // v를 수정하지 않으므로 const_iterator로 받습니다.
v.insert(const_itr, 0); // const_itr 앞에 0을 삽입합니다.

EXPECT_TRUE(v[0] == 0 && v[1] == 1 && v[2] == 2);

(C++11~) 컨테이너의 initializer_list 초기화

기존에는 컨테이너에 요소들을 추가할때 일일이 추가해야 했습니다.(컨테이너 요소 삽입/삭제 참고)

1
2
3
4

std::vector<int> v;
v.push_back(1); // 이전에는 push_back으로 데이터를 삽입했습니다.
v.push_back(2);
v.push_back(3);

C++11 부터는 컨테이너의 initializer_list 초기화가 추가되어 초기값 입력이 간편해 졌습니다.

1

std::vector<int> v{1, 2, 3}; // C++11. 중괄호 초기화로 초기값을 넣을 수 있습니다.

단, 기존 생성자와 initializer_list 생성자와의 충돌에서 말씀드린 것처럼 initializer_list를 사용한 버전이 비교적 우선적으로 선택되기 때문에 중괄호 초기화시 기존 버전 초기화를 사용할때는 ()버전을 사용해야 합니다.

1
2
3
4
5

std::vector<int> v1(2); // 요소 갯수가 2개인 vector 생성
EXPECT_TRUE(v1.size() == 2 && v1[0] == 0 && v1[1] == 0);

std::vector<int> v2{2}; // 요소값이 2인 vector 생성
EXPECT_TRUE(v2.size() == 1 && v2[0] == 2);

(C++11~) emplace(), emplace_back(), emplace_front(), emplace_hint() 삽입

기존에는 컨테이너 바깥에서 개체를 생성해서 push_back()등으로 컨테이너에 전달했는데요, 이때 컨테이너는 삽입된 개체의 복제본을 관리합니다.(컨테이너의 원본 관리 참고)

C++11 부터는 emplace() 계열 함수들이 추가되어 요소 삽입시 완벽한 전달을 이용하여 컨테이너 내에서 요소 개체를 직접 생성할 수 있으며, 불필요한 복제본을 생성하지 않습니다.

요소 개체를 컨테이너 밖에서 생성하던, 컨테이너 안에서 생성하던 생성하는건 똑같지만, 바깥에서 생성된 것은 관리를 위해 복제본을 만들어야 하기 때문에 복사 부하가 있습니다.

다음 예에서

  • push_back(a)는 기존에 생성한 a개체를 복사 생성하여 vector에서 관리합니다. 즉 2회 생성합니다.

  • push_back(A{1, 2})는 임시 개체인 A{1, 2}를 생성하고, 이를 이동 생성하여 vector에서 관리합니다. 즉 1회 생성 / 1회 이동합니다.

  • emplace_back(1, 2)는 1 과 2를 가지고 A개체를 생성해서 vector에서 관리합니다. 즉 1회 생성합니다.

따라서, emplace_back()이 불필요한 복제본을 만들지 않으니 push_back() 보다는 emplace_back()을 사용하는게 효율적입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class A {
    int m_X;
    int m_Y;
public:
    A(int x, int y) {std::cout << "A::Value Constructor" << std::endl;}
    A(const A& other) {std::cout << "A::Copy Constructor" << std::endl;}
    A(A&& other) noexcept {std::cout << "A::Move Constructor" << std::endl;}

    A& operator =(const A& other) = delete;
    A& operator =(A&& other) noexcept = delete;
};

std::vector<A> v;
v.reserve(10); // push_back이나 emplace_back 중 재할당이 없게끔 공간을 널널하게 만듭니다.

A a{1, 2}; 
v.push_back(a); // (△) 비권장. 복제본을 생성하면서 좌측값이므로 복사 생성 1회.
v.push_back(A{1, 2}); // (△) 비권장. 복제본을 생성하면서 임시개체인 우측값이므로 이동 생성 1회.
v.push_back({1, 2}); // (△) 비권장. 중괄호 복사 초기화로 v.push_back(A{1, 2}); 과 동일

v.emplace_back(1, 2); // (O) A개체 생성을 위한 데이터를 전달합니다. 개체 생성 1회
// v.emplace_back({1, 2}); // (X) 컴파일 오류. A는 {1, 2} 를 전달받는 생성자가 없습니다.

또한, initializer_list 보다 emplace_back()을 사용하는게 효과적입니다.

다음 예를 보면, initializer_list는 값 생성자 2회, 복사 생성자 2회를 호출하지만, emplace_back()은 값 생성자 2회만 호출합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class A {
    int m_X;
    int m_Y;
public:
    A(int x, int y) {std::cout << "A::Value Constructor" << std::endl;}
    A(const A& other) {std::cout << "A::Copy Constructor" << std::endl;}
    A(A&& other) noexcept {std::cout << "A::Move Constructor" << std::endl;}

    A& operator =(const A& other) = delete;
    A& operator =(A&& other) noexcept = delete;
};

// 값 생성자 2회 
// initializer_list 요소로 만들기 위해 이동 생성자 2회 -> 컴파일러 최적화에 의해 생략됨
// 복사 생성자 2회 - vector에서 복제본 관리
std::vector<A> v1{A{1, 2}, A{3, 4}}; 
                                        
std::vector<A> v2;
v2.reserve(2);
v2.emplace_back(1, 2); // 값 생성자 1회
v2.emplace_back(3, 4); // 값 생성자 1회

(C++14~) 연관 컨테이너의 이종 탐색

기존에는 map과 set등의 연관 컨테이너에서 Key와 동일한 타입으로만 탐색이 가능했습니다.

다음 예에서는 Lee의 데이터를 탐색하고 싶어 Data{"Lee", 10}와 같이 Key와 동일한 Data 타입 개체를 만들어 find()함수를 호출합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Data {
public:
    std::string m_Name;
    int m_Val;
    bool operator <(const Data& other) const {
        if (m_Val < other.m_Val) return true;
        if (other.m_Val < m_Val) return false;

        return m_Name < other.m_Name;
    }
};

std::set<Data> dataSet{
    Data{"Lee", 10},
    Data{"Park", 20}
};
auto result{
    dataSet.find(
        Data{"Lee", 10} // (△) 비권장. 같은 타입만 탐색이 가능하므로 "Lee"를 탐색하고 싶어도 Data 개체를 동일하게 만들어 탐색해야 합니다.
    )
}; 
EXPECT_TRUE((*result).m_Name == "Lee" && (*result).m_Val == 10);

이때 탐색할 "Lee"만 알고 있고, 10은 모르고 있다면, 그냥 요소들을 다 뒤져서 값비교를 해야 합니다. 연관 컨테이너의 장점을 살리지 못하니, 이럴게 사용할 바엔 차라리 vector가 낫죠.

C++14 부터는 연관 컨테이너의 이종 탐색을 지원하여 Key와 다른 타입이더라도 탐색이 가능합니다.

  1. 이종 타입에 대해 비교할 수 있게 정적 비교 함수를 제공합니다.
  2. 컨테이너 선언시 find() 에서 Key 타입외에 다른 것을 사용하려면 less<>를 사용합니다.
  3. find() 함수에 탐색하고 싶은 이종 타입의 개체를 전달합니다.

다음 예에서는 Data 개체를 생성하지 않고 "Lee"로 검색합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Data {
public:
    std::string m_Name;
    int m_Val;
    bool operator <(const Data& other) const {
        if (m_Val < other.m_Val) return true;
        if (other.m_Val < m_Val) return false;

        return m_Name < other.m_Name;
    }
};
// 이종 타입에 대해 비교할 수 있게 정적 비교 함수를 제공합니다.
bool operator <(const Data& left, const char* right) {
    return left.m_Name < right;
}
bool operator <(const char* left, const Data& right) {
    return left < right.m_Name;
}

// find()에서 키 타입외에 다른 것을 사용하려면 std::less<>를 사용합니다.
std::set<Data, std::less<>> dataSet{
    Data{"Lee", 10},
    Data{"Park", 20}
};
auto result{
    dataSet.find(
        "Lee" // find() 함수에 탐색하고 싶은 이종 타입의 개체를 전달합니다.
    )
}; 

EXPECT_TRUE((*result).m_Name == "Lee" && (*result).m_Val == 10);

(C++20~) 컨테이너 멤버 함수의 constexpr 개선

컨테이너 멤버 함수의 constexpr 지원이 개선되어 대부분의 멤버 함수들이 constexpr 함수로 변경되었습니다.

(C++20~) vector와 string의 constexpr 개선

vector와 string이 constexpr 컨테이너로 변경되었습니다.

또한 대부분의 알고리즘에서 constexpr 지원이 개선되었기 때문에 다음과 같이 컴파일 타임에 vector와 string를 정렬하여 사용할 수 있습니다.

1
2
3
4
5
6
7
8
9

constexpr int maxVal { 
    [] {
        std::vector<int> v{3, 2, 1};
        std::sort(v.begin(), v.end()); // 컴파일 타임에 정렬됩니다.
        
        return v.back(); // 가장 뒤의 값을 리턴합니다.
    }()
};
static_assert(maxVal == 3); // 컴파일 타임 상수입니다.

(C++20~) erase(), erase_if()

각 컨테이너의 erase()는 이터레이터를 전달받아 요소를 삭제하고, 알고리즘의 remove()는 값을 전달받아 삭제하지 않을 요소를 앞으로 옮깁니다. 따라서 값으로 요소를 삭제하려면 다음과 같이 이 둘을 결합해서 사용해야 했습니다.(컨테이너 멤버 함수 erase()와 알고리즘 remove() 함수 참고)

1
2
3
4

std::vector<int> v{1, 1, 2, 1, 1, 3};
std::vector<int>::iterator result{std::remove(v.begin(), v.end(), 1)}; // 삭제하지 않을 요소를 컨테이너의 앞으로 옮기고 erase할 위치를 리턴합니다.
v.erase(result, v.end()); // 요소를 실제로 삭제합니다.
EXPECT_TRUE(v.size() == 2 && v[0] == 2 && v[1] == 3);

C++20 부터는 erase(), erase_if()가 추가되어 값으로 요소를 삭제할 수 있습니다.

1
2
3

std::vector<int> v{1, 1, 2, 1, 1, 3};
std::erase(v, 1); // 값이 1인 요소를 삭제합니다.
EXPECT_TRUE(v.size() == 2 && v[0] == 2 && v[1] == 3);

(C++20~) contains()

기존에는 연관 컨테이너에서 주어진 Key가 있는지 검사하려면 find()를 사용했는데요,

1
2
3
4

std::set<int> s{1, 2, 3}; // C++17 부터는 템플릿 인수 추론을 하므로 std::set s{1, 2, 3}; 도 됩니다.
if (s.find(2) != s.end()) {
    // s에 2가 있을때의 코드
}

C++20 부터는 contains()가 추가되어 연관 컨테이너에서 주어진 Key가 있는지 검사할 수 있습니다.

1
2
3
4

std::set s{1, 2, 3};
if (s.contains(2)) {
    // s에 2가 있을때의 코드   
}

태그:

카테고리:

업데이트:

댓글남기기