잘 쓰이는 STL 간단 정리

vector

 

벡터는 배열과 비슷하다

하지만 동적으로 크기를 늘리고 줄이는 점이 다르다.

 

vector<int> vc;

이래 선언하면 하나의 벡터에 아이템을 추가할 수 있고

 

vector<int> vc[10];

이래 선언하면 벡터 배열이 순차적으로 구현되며

각각의 배열 요소마다 아이템을 추가할 수 있다.

 

크기 변경 가능

순차 접근 가능

랜덤 접근 가능(인덱스를 이용하여)

 

다만 배열이기 때문에 중간에 삽입하거나 삭제를 한다면?

삽입하게 되면 그 요소 다음 원소부터 싹다 밀어서 저장해야하고

삭제하게 되면 그 요소 다음 원소부터 싹다 당겨서 저장해야하기 때문에

삽입, 삭제가 빈번하면 효율적이지 못하다.

 

 

 

list

 

리스트는 이중 연결리스트로써 구현이 된다.

이중 연결리스트라 하면은 배열처럼 순서 있게 구현되는 것이 아니라

서로를 가리키는 주소, 즉 포인터를 가지고서 연결이 되게 된다.

 

크기 변경 가능

중간 삽입, 삭제 용이

순차 접근 가능(포인터를 따라서)

 

다만 랜덤접근은 불가능하다.

주소값으로 연결되어 있기 때문에 곧바로 접근은 불가능하고

그냥 선형탐색을 해서 찾아야 한다.

 

그래도 삽입, 삭제가 빈번하다면 원소를 밀거나 당길 필요가 없기 때문에 효율적이다.

 

 

 

map

 

맵은 키 그리고 매핑된 값의 결합 형태를 가지는 요소를 저장하는 컨테이너이다.

즉 맵은 (키, 값) 일케 묶여서 보관이 된다.

 

맵은 일반적으로 키값을 기준으로 해서 내부에서 정렬이 된다.

이진 탐색트리라고 보면 된다.

 

이진 탐색트리로 구성되어 있다는 것은

어떤 원소를 찾는데 있어서 시간복잡도가 logn 이기 때문에

아주 빠르게 특정 원소를 찾을 수 있다.

 

원소가 8개라고 가정 하면 맵은 키값을 기준으로

          a

      b       c

  d    e   f    g

 

이래 구성 되어 있다.

원소 g를 찾는다고 했을 때

a와 비교

c와 비교

g와 비교 하면 찾는다.

 

즉 비교하는 높이가 3이면 종료되게 된다.

log2 8 = 3