내장 라이브러리가 있는 자료 구조

C++은 프로그램에 필요한 자료구조와 알고리즘을 STL(Standard Template Library)로서 제공합니다.

 

이 글에서는 C++ STL에 내장된 자료구조가 어떤 것들이 있는지 간단하게 언급하고 넘어가려고 합니다.

 

기본적인 자료구조 자체에 대한 설명은 하지 않습니다.

 

 

1. 정적 배열 (array)

 

#include <array>
using namespace std;
 
int main()
{
    int a[100]; // 정적 배열
    array <int, 100> b; // 함수로 전달할 때 포인터 형 변환이 되지 않는 정적 배열
}

---

2. 동적 배열 (vector)

 

#include <vector>
using namespace std;
 
int main()
{
    vector <int> vec; // 동적 배열
}

---

3. bool형 정적 배열 (bitset)

 

#include <bitset>
using namespace std;
 
int main()
{
    bitset <100> bs; // bool형 정적 배열
}

bool형 배열에 추후 설명할 비트연산을 할 수 있는 자료구조 입니다.

---

4. 스택 (stack)

 

#include <stack>
using namespace std;
 
int main()
{
    stack <int> stk; // 스택
}

보통 스택이 필요한 경우는 스택의 기능을 다 가지고 있고 인덱스 접근도 가능한 vector을 사용하게 됩니다.

---

5. 큐 (queue)

 

#include <queue>
using namespace std;
 
int main()
{
    queue <int> q; // 큐
}

---

6. 덱 (deque)

 

#include <deque>
using namespace std;
 
int main()
{
    deque <int> dq; // 덱
}

---

7. 이중 연결 리스트 (list)

 

#include <list>
using namespace std;
 
int main()
{
    list <int> ls; // 이중 연결 리스트
}

---

8. 균형 이진 탐색 트리 (set, map, multiset, multimap)

 

#include <set>
#include <map>
using namespace std;
 
int main()
{
    set <int> st; // key only BBST
    multiset <int> ms; // 중복 가능 key only BBST
    map <int, int> mp; // key-value BBST
    multimap <int, int> mm; // 중복 가능 key-value BBST
}

 

---

9. 힙 (priority_queue)

 

#include <queue>
using namespace std;
 
int main()
{
    priority_queue <int> pq; // 힙
}

 

---

10. 해시 테이블 (unordered_set, unordered_map, unordered_multiset, unordered_multimap)

 

#include <unordered_set>
#include <unordered_map>
using namespace std;
 
int main()
{
    unordered_set <int> us; // key only Hash Table
    unordered_multiset <int> ums; // 중복 가능 key only Hash Table
    unordered_map <int, int> um; // key-value Hash Table
    unordered_multimap <int, int> umm; // 중복 가능 key-value Hash Table
}

 

일반적으로 같은 작업을 할 수 있는 균형 이진 탐색 트리에 비해 평균적인 속도가 빠르지만, 최악의 경우는 더 느리기 때문에 PS에서는 잘 쓰이지 않습니다.