Certi Pro 취득을 위해 꼭 알아야 할 STL Container : Sequence

이전 글 : Certi Pro 취득을 위해 꼭 알아야 할 iterator

 

Pro 시험에 STL 사용이 가능해지면서, STL에 구현된 자료구조를 사용하는 방법과 자료구조의 장단점을 익히는 것이 중요해졌다. 어떤 상황에 어떤 자료구조를 쓰는 것이 유리한지, 그 자료구조를 어떻게 활용하는지를 중점을 두고 공부해야 한다.

 

Pro에서 자주 사용되는 자료구조는 다음과 같다.

1) Sequence : vector, list

2) Associative : set, map

3) Unordered Associative : unordered_set, unordered_map

4) Adaptors : priority_queue, (stack)

 

물론 이 외에도 queue, deque, multi_set, multi_map 등 다양한 자료구조가 있지만, 프로 시험에서 자주 쓰이지는 않는다.

stack 같은 경우에도 계산 기능을 구현하는 문제에서 대표적으로 사용되지만, 시험에서는 그냥 배열 형태를 사용하는 경우가 많다.

 

이번 포스팅에서는 Sequence Container를 살펴보자.

 

① vector

vector는 dynamic array 형태의 자료구조이고, random access가 가능하다.

[배열 형태의 자료구조를 쓰고 싶지만 크기를 고정해 두고 사용할 수 없을 때] 주로 사용한다.

vector는 프로 시험에서 꽤 자주 사용되는 자료구조이지만, capacity를 늘리는 것이 꽤 비싼 연산이기 때문에 최적화가 중요한 시험에서는 적합하지 않다. 프로 시험에서는 항상 변수의 범위와 함수 호출 횟수를 알려주기 때문에, 배열을 사용할 수 있는 경우라면 vector 대신 고정된 크기의 배열 자료구조를 사용하는 것을 추천한다.

 

vector는 위와 같이 사용 중인 크기 size와 할당받은 크기 capacity로 이루어져 있다. capacity를 다 사용했는데 새로운 원소가 삽입되면, 동적으로 새로운 배열을 할당한다.

 

vector의 공간 및 연산의 시간복잡도는 다음과 같다.

	Complexity
space	O(n)
search	O(n)
insert	O(n)
delete	O(n)
push_back	O(1)
pop_back	O(1)
migration	O(n)

 

[vector 주요 문법]

iterator v.begin(), v.end() // 벡터의 시작 원소, 마지막 원소의 다음 iterator
iterator v.rbegin(), vrend() // 벡터의 마지막 원소, 시작 원소의 앞 iterator

T v[int idx] // random access 가능

bool v.empty() // vector가 비어있나 check
void v.clear() // vector 초기화

size_t v.size()
size_t v.capacity()

T v.front(), v.back()

void v.push_back()
void v.pop_back()

iterator v.insert(iterator pos, T x)
iterator v.insert(iterator pos, int count, T value)
iterator v.insert(iterator pos, iterator first, iterator last)
// 처음 입력된 element의 iterator 반환

iterator v.erase(iterator pos)
iterator v.erase(iterator first, iterator last)
// 마지막 지워진 element의 다음 iterator 반환

 

[vector 사용 예제]

vector<int> v; // 선언

for(int i = 1; i <=5; i++) v.push_back(i); // 뒤에 삽입

// 순회하는 방법, 결과는 모두 1 2 3 4 5
for (int i = 0; i < v.size(); i++) cout << v[i] << ' ';
for (auto x : v) cout << x << ' ';
for (auto it = v.begin(); it != v.end(), ++it) cout << *it << ' ';

for (auto it = v.rbegin(); it != v.rend(), ++it) cout << *it << ' ';
// 5 4 3 2 1

v.insert(v.begin(), 6); // 6 1 2 3 4 5
v.insert(v.end(), 7); // 6 1 2 3 4 5 7
v.insert(v.begin() + 3, 8); // 6 1 2 8 3 4 5 7

v.erase(v.begin() + 1); // 6 2 8 3 4 5 7
v.erase(v.end() - 1); // 6 2 8 3 4 5
v.pop_back(); // 6 2 8 3 4

v[2] = 0; // 6 2 0 3 4
v.empty(); // 0 (false)
v.size(); // 5

sort(v.begin(), v.end()); // 0 2 3 4 6

 

 

② deque

deque는 프로 시험에서 자주 사용되지 않기 때문에 간단하게 vector와의 차이점만 짚고 넘어가자.

vector와 달리 deque는 front에 원소를 삽입하고 삭제하는 것이 O(1)에 가능하다.

다른 문법은 vector와 비슷하지만, push_front와 pop_front를 추가적으로 사용할 수 있다는 차이가 있다.

일반적인 연산은 vector보다 느리므로, front에 데이터 insert / erase가 필요한 경우에 사용한다.

 

deque의 공간 및 연산의 시간복잡도는 다음과 같다.

	Complexity
space	O(n)
search	O(n)
insert	O(n)
delete	O(n)
push_back push_front	O(1)
pop_back pop_front	O(1)
migration	O(Block 수)

 

 

③ list

cpp에서 list는 이중 연결 리스트(doubly linked list)이며 bidirectional iterator를 가지고 있다.

list의 가장 큰 장점은 원소를 삽입하고 삭제하는 데 걸리는 시간이 O(1)이라는 점이다.

원소의 삭제와 삽입이 빈번하다면, list 사용을 의심해 보면 좋다.

 

list의 공간 및 연산의 시간복잡도는 다음과 같다.

	Complexity
space	O(n)
search	O(n)
insert	O(1)
delete	O(1)

 

[list 주요 문법]

list<T> li // 선언
iterator li.begin(), li.end()
reverse iterator li.rbegin, li.end()

void li.clear()
bool li.empty()
size_t li.size()

T li.front(), li.back()

void li.push_back(T x)
void li.pop_back()
void li.push_front(T x)
void li.pop_front()

iterator li.insert(iterator pos, T x)
iterator li.insert(iterator pos, int count, T x)
iterator li.insert(iterator pos, iterator first, iterator last)
// 처음 입력된 element의 iterator 반환

void li.splice(iterator pos, list<T> li2)
// li의 pos에 li2 전체 이동
void li.splice(iterator pos, list<T> li2, iterator it)
// li의 pos에 li2의 it 이동
void li.splice(iterator pos, list<T> li2, iterator first, iterator last)
// li의 pos에 li2의 [first, last) 구간 이동

void li.sort() // operator< 기준으로 정렬
void li.sort(function compare) // compare 기준으로 정렬 : O(nlogn)

전반적으로 vector와 문법이 유사하고, 추가적으로는 splice method를 익혀두면 좋은데, 세 번째 splice의 경우 시간복잡도가 O(n)이기 때문에 주의해서 사용해야 한다. 또한 list에서 insert 메서드의 반환값이 원소가 삽입된 곳을 가리키는 iterator라는 것을 기억해 두자.

 

[list 사용 예제]

list<int> li1, li2;

for (int i = 1; i <= 5; i++) li.push_back(i); // 1 2 3 4 5

li.insert(li.end(), 6); // 1 2 3 4 5 6
li.insert(next(li.begin(), 3), 7); // 1 2 3 7 4 5 6

li.pop_front(); // 2 3 7 4 5 6
li.erase(li.begin()); // 3 7 4 5 6 
li.erase(--li.end()); // 3 7 4 5

li.sort(); // 3 4 5 7
li.sort(greater<int>{}); // 7 5 4 3

li.splice(li.end(), li, li.begin()) // 4 5 7 3
li2.splice(li2.begin(), li); // li = empty, li2 = 4 5 7 3

li.splice(li.begin(), li2, li2.begin(), next(li2.begin(), 2)) // li = 4 5, li2 = 7 3

struct Data {
	int id;
    int value;
};

list<Data>li;
list<Data>::iterator it[6]; // li를 가르킬 iterator를 담을 배열

for (int i = 1; i <= 5; i++) it[i] = li.insert(li.begin(), {i, 0});
// insert하며 iterator 기록

/* 정방향 순회 */
for (auto d : li) d.id, d.value;
for (auto it = li.begin()); it != li.end(); ++it) it->id, it->value;

/* 역방향 순회 */
for (auto it = li.rbegin()); it != li.rend(); ++it) it->id, it->value;

it[5]->value = 3; // (1, 0), (2, 0), (3, 0), (4, 0), (5, 3)
it[3]->value = 4; // (1, 0), (2, 0), (3, 4), (4, 0), (5, 3)

li.erase(it[1]); // (2, 0), (3, 0), (4, 0), (5, 3)
li.splice(li.begin(), li, it[5]) // (5, 3), (2, 0), (3, 0), (4, 0)

위의 예시에서 list<Data>::iterator 문법과 insert하며 iterator를 기록해 두는 테크닉은 자주 사용되므로 꼭 연습해 두자.

 

다음 글 : Certi Pro 취득을 위해 꼭 알아야 할 STL Container : Associative