[C++] Vector, Deque, List는 언제 사용해야할까?

Vector

벡터의 선언

• vector <자료형> 변수명(m, n)과 같이 초기화하며 m만큼 벡터를 생성 후 숫자 n로 초기화한다.
• vector <자료형> 변수명[] = {, }과 같이 2차원 벡터를 선언한다. 이때 열의 크기는 고정이고 행의 크기는 변할 수 있다.
• vector <vector <자료형>> 변수명과 같이 2차원 벡터를 선언할 수 있고 이 경우는 열과 행 모두 크기가 변할 수 있다.

---

벡터의 원소에 접근

• v.begin() : 벡터 시작점의 주소 값을 반환한다.
• v.end() : 벡터 벡터의 마지막 원소의 주소값을 반환한다.
• v.at(i) : 벡터의 i번째 요소에 접근한다. 이때 범위를 검사한다.
• v [i] : 벡터의 i번째 요소에 접근하며 이때 범위는 검사하지 않는다.
• v.front() : 벡터의 첫 번째 값을 리턴한다.
• v.back() : 벡터의 마지막 값을 리턴한다.

---

벡터 원소 삽입/삭제

• v.push_back() : 새로운 메모리에 모든 값을 복사한 후 마지막에 새로운 요소를 추가한다.
• v.pop_back() : 벡터의 마지막 원소를 제거한다.
• v.insert(삽입할 위치의 주소 값, 값) : 삽입할 위치의 주소에 값을 삽입한다. 이 때도 push_back()과 같이 복사생성자를 호출한다.
• v.emplace_back() : push_back()과 같은 역할을 하지만 복사생성자를 호출하지 않는다.
• v.emplace(삽입할 위치의 주소 값, 값) : insert()와 같은 역할을 하지만 복사생성자를 호출하지 않고 벡터 내부에서 값을 생성한다.
• v.erase(index) : index의 요소를 제거한다.
• v.erase(시작위치, 끝위치) : 시작위치부터 끝위치까지의 요소들을 제거한다.
• v.clear() : 벡터의 모든 요소를 지우고 벡터의 크기를 0으로 만든다.

---

벡터의 저장 공간 할당 방식

 벡터는 배열처럼 원소들을 연속적으로 저장한다. 따라서 중간의 원소를 삭제하려면 해당 원소 뒤의 모든 원소들을 앞으로 한 칸씩 당겨야 하므로 시간이 더 든다. 하지만, 연속적으로 저장하기에 개별 원소에 대한 접근은 빠르다. 또 배열의 끝에서 일어나는 삽입/삭제도 가장 빠르다.

 

 vector의 크기는 size와 capacity 두 개가 있는데, size는 벡터가 생성된 크기이며 capacity는 벡터의 최대 할당 크기이다.

push연산을 통해 벡터의 size가 capacity를 초과하면 reallocate가 발생하여 모든 값들을 새로운 메모리에 복사하는 과정이 일어난다. 이 과정에서 속도 저하가 일어나며 capacity를 설정해 주는 함수들을 이용하여 reallocate를 막을 수 있다.

clear()로 벡터의 값들을 지우면 벡터의 요소들은 없어지지만 capacity는 여전히 남아있다. 따라서 swap을 이용하여 capacity 또한 제거해줘야 한다.

 

vector<int> v = {1, 2, 3, 4};
v.clear();
vector<int>().swap(v);

위와 같이 사용하면 아무것도 없는 벡터공간과 swap이 일어나 capacity를 없앨 수 있다.

• v.empty() : 벡터가 빈 공간이면 true를 아니라면 flase를 리턴한다.
• v.size() : 벡터의 size를 리턴한다.
• v.capacity() : 메모리 heap에 할당된 벡터의 최대크기를 반환한다.
• v.shrink_to_fit() : capacity의 크기를 벡터의 실제 크기로 맞춘다.

---

Deque

 vector의 경우 size가 capacity를 초과하는 경우 reallocate가 발생한다는 단점이 있었다. 하지만 deque에서는 여러 개의 메모리 블록을 할당하고 이들을 하나의 블록처럼 사용한다. 이를 chunk라고 부르며, 이는 내부적으로 관리된다. 따라서 메모리가 부족하면 새로운 메모리 블록을 할당하여 vector의 단점을 보완하였다.

• vector와 같은 방식으로 초기화한다.
• dq.assign(a, b) : b를 a개만큼 할당한다.
• dq.push_front(value) : deque의 제일 앞에 value를 삽입한다.
• dq.pop_front() : deque의 제일 앞의 원소를 제거한다.

나머지 메서드들은 vector와 비슷하게 작동한다.

---

Deque의 저장 공간 할당 방식

덱은 배열의 시작과 끝에서 원소의 삽입/삭제가 빠르다. 또 벡터와 달리 chunk 단위로 쪼개어 비연속적으로 원소를 저장한다. 따라서 저장할 원소가 많은 경우 벡터에 비해 메모리를 더 조금씩 할당하기에 확장 비용이 절감된다. 그러나 비연속적으로 저장하기 때문에 벡터에서 가능했던 원소들 간의 포인터 연산이 불가능하다.

---

List

이중 연결 리스트이다. 원소의 index로 접근하는 방식인 at이나 []가 아닌 iterator를 통해서 ++, --연산을 통해 원소를 접근한다. 자주 사용하는 메서드들을 보자.

• lt.assign(a, b) : b로 초기화된 a개의 list를 생성한다.
• lt.insert(iter, k) : iter가 가리키는 위치에 원소 k를 삽입한다.
• lt.erase(iter) : iter가 가리키는 원소를 삭제한다.
• lt.remove(k) : k와 같은 원소를 모두 삭제한다.
• lt.remove_if(Predicate) : 조건자에 해당하는 원소를 모두 제거한다.
• lt.srot() : iterator로 범위를 지정하여 오름차순으로 정렬한다. 비교자 함수를 정의하여 세 번째 인자로 사용할 수 있다. 이 경우 연산자 재정의를 통해 이루어진다.

struct _RANKING_INFO_ {
int  score;
char strUserName[32];
              bool operator<  ( const _RANKING_INFO_& rhs ) const
              {
                   return score < rhs.score;
               }
};

bool RankComp( const _RANKING_INFO_& lhs, const _RANKING_INFO_& rhs )
{
  return lhs.score < rhs.score;   //오름차순 정렬
};

---

List의 특징과 장단점

List는 이중 연결 리스트를 그대로 구현한 컨테이너이다. 따라서 컨테이너의 어느 위치에서든 삽입과 삭제가 빠르다. 하지만 원소에 index로 접근이 불가능하고, 순회가 느리다는 단점이 있다.