STL 컨테이너(deque, list, set, map) 설명

컨테이너는 STL의 구성 요소 중 하나이며, 데이터를 저장하는 객체들이다.

 

컨테이너의 구성 요소

• Sequence Containers  (vector, deque, list, slist)
• Associative Containers  (set, multiset, map, multimap, unordered_set, unordered_map, bitset)
• container adapters  (stack, queue, priority_queue)

---

 

Sequence Containers (순차 컨테이너, 정렬되지 않은 연결리스트/배열)

 

1. 임의의 위치에 삽입, 삭제가 가능하다.

2. 데이터를 순차적으로 저장한다.

3. 일반적인 자료구조와 동일한 형태이다.

4. 자료를 입력한 순서대로 저장하기 때문에 저장, 검색, 알고리즘에 불리하다

        => 많지 않은 자료, 검색 속도 중요하지 않을 때 사용

 

deque

#include <deque>

 

1. 동적 배열이다.

2. vector와 다르게 시작 & 끝에서 삽입과 삭제를 수행한다.

              push_front, push_back

 

#include <deque>
#include <iostream>

using namespace std;
int main()
{
	std::deque<int> deq;
    
	for (int i = 0; i < 10; ++i)
	{
		deq.push_back(i);
		deq.push_front(i);
	}
    
	for (auto& itr : deq)
		cout << itr << "  ";
    /* *출력
    9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9
    */
	cout << "\n";

}

 

list

#include <list>

 

 

1. 노도 기반 컨테이너, 이중 연결 리스트 (양방향 -> 임의 접근 반복자는 불가능하며, 양방향 반복자(++, --)를 이용해서 탐색 가능)

2. 배열과 달리 요소들이 서로 근접한 메모리에 연속적으로 저장되지 않음

3. 검색과 접근이 느리지만 일단 검색이 되면 빠른 삽입과 제거 시간을 가진다.

 

장점.

1. 중간 삽입/삭제 가능하며, 크기 변경도 가능하다

2. 적은 양의 자료에 유리하며 순차 접근이 가능하다

 

단점.

1. 많은 양의 자료에 불리하다

2. 랜덤 엑세스 불가하며 검색속도가 느리다

---

 

Associative Containers (연관 컨테이너,  정렬된 컨테이너)

 

1. 일정 규칙에 따라 자료를 조직화하여 저장한다.

2. 자료를 정렬/해시 등 이용해 저장하기 때문에 검색에 유리하다

     => 많은 양의 자료, 빠른 검색

map

#include <map>

 

1. 이진탐색트리 기반이며, Key를 기준으로 자동으로 정렬된다.

2. key - value pair로 구성되며, Key와 Value은 서로 대응된다.

3. Key는 중복되지 않는다.

4. Key와 Value를 pair로 삽입하거나 [key] = value 형식으로 삽입해야 한다.

 

장점.

1. 많은 양의 자료에 유리

2. 검색 속도 빠르다

3. key / value 따로 저장되며 자동 정렬된다.

 

단점.

1. 적은 양엔 오버헤드로 인해 오히려 손해

 

#include <iostream>
#include <map>

using namespace std;

void main()
{
    std::map<char, int> userMap;
    userMap['a'] = 10;					// userMap['a'] = 10; o / userMap['a'](10); x
    userMap['b'] = 20;					// b = key  / 20 = value
    userMap.insert(make_pair('c', 50));
    
    cout << userMap['a'] << endl;		// 출력 : 10
    userMap.insert(make_pair('a', 100)); // 'a' key는 이미 있기에 무시된다.
    cout << userMap['a'] << endl;		// 출력 : 10
    
    cout << userMap.size() << endl;		// 출력 : 3
    
    for (auto& itr : userMap)
	{ // first -> Key,  second -> Value
    	cout << "Key = " <<  itr.first << "   " << "Value = " << itr.second << "\n";
    }
    /* *출력
    Key = a   Value = 10
    Key = b   Value = 20
    Key = c   Value = 50
    */
    cout << "\n";
}

 

Set

#include <set>

 

1. 이진탐색트리 기반이며, 자동 정렬되고, key만 저장한다.

2. insert함수로 삽입

3. 원소가 중복되지 않는다.

        삽입하려는 아이템이 이미 set안에 있어 중복이 된다면 삽입되지 않고 무시한다.

 

장점.

1. 많은 양의 자료에 유리하며, 검색 속도가 빠르다.

2. key만 저장한다 (즉, key = value)

 

단점.

1. 적은 양엔 오버헤드로 인해 오히려 손해이다.

 

#include <set>
#include <iostream>

using namespace std;
int main()
{
	std::set<string> strSet;

	strSet.insert("Hello");
	strSet.insert("World");
	strSet.insert("Hello");	// 이미 중복된 원소가 있어서 삽입 안되고 무시된다. 

	cout << strSet.size() << "\n";		// 출력  2

	for (auto& itr : strSet)
        cout << itr << "   ";
       // 출력 Hello World
	cout << "\n";
}