C++ 에서의 자료구조 Array 대신 Vector를 쓰는 이유

 

C++에서는array도 제공하지만 vector도 제공한다.

왜 우리는 vector를 쓰는가?

 

우선 array는 컴파일할 때 크기가 결정된다. 즉, 미리 알고 선언해야한다는 말이다.

크기가 고정되어있으므로 원소의 데이터는 바꿀 수 있어도 원소를 추가하거나 삭제하는 일은 불가능하다.

또한 컴파일할 때 크기가 결정되므로 무조건 스택 메모리를 사용한다.

 

솔직히 거의 모든 응용프로그램에서는 데이터가 동적이며 크기도 고정되어 있지 않은 게 현실이다.

때문에 데이터의 크기를 미리 알고 있는 것은 어렵다

**다만 메모리가 많다면 미리 선언하는 것도 나쁘지는 않다고 본다.

 

하지만 효율적인 활용을 위해선, 위 상황을 제외하면

가변 크기의 데이터 컨테이너가 있었으면 좋겠다고 생각한다.

 

바로 그것이 vector이다.

 

//1. 크기가 0인 벡터
std::vector<int> vec;

//2. 크기가 5이면서 초기값이 설정된 벡터
std::vector<int> vec = {1,2,3,4,5}

//3 크기가 10인 벡터
std::vector<int> vec(10);

//4. 크기가 10이고 -1로 초기화된 벡터
std::vector<int> vec(10,-1);

 

우선 위는 벡터의 선언 방법이다.

원소 개수를 지정하지 않더라도 선언이 된다. 

**다만 크기를 지정할 수 없는 경우 컴파일러 구현 방법에 따라 용량(capacity)를 가지는 벡터를 생성한다.

 

용량과 실제 벡터의 크기는 엄연히 다르다.

 

그렇다면 원소 추가는 어떨까?

push_back()과 insert()가 이용된다.

push_back(value);
//if size<capacity // 할당된 공간이 있을 경우
// 마지막 원소 뒤에 value 추가
// 벡터 크기를 1 증가
// return


//if vector is already full // 용량이 꽉찼을 때
// 2*size 크기의 메모리를 새로 할당한다.
// 새로 할당한 메모리로 기존 원소를 모두 복사시켜서 이동한다.
// 데이터 포인터를 새로 할당한 메모리 주소로 지정
// 마지막 원소 다음에 value 추가 벡터 크기 1 증가.

 

우선 원소를 추가할 때 용량(capacity)이 초과하는 상황이 발생한다면..?

뭐 용량을 키워서 다시 추가해야지...

 

당연히 위에 써놓은 push_back과 insert는 실제 구현은 아니고 그냥 의사코드 비슷하게 짠 것이다.

동작은 비슷하게 진행된다.

 

어차피 2*31은 21억과 맞먹는 수치기 떄문에.. 벡터 용량은 생각보다 금방 늘어난다.

 

또한 push_back()은 맨 뒤에 원소를 추가하는 것이라 시간 복잡도는 O(1)이라고 본다.

insert()함수는 임의의 위치에 원소를 추가하기 때문에

그 위치에 있는 것부터 끝까지 1칸씩 다 밀어야 하기 때문에

O(N)의 시간 복잡도를 가지고 있다.

 

또한 push_front()같은 것은 지원하지 않기 때문에

insert(vec,begin(), 0) 맨 처음을 가리키는 iterator를 이용하여 추가시킨다.

 

---

 

원소를 추가시키는 방법이 비효율적이라고 생각되기도 한다.

이들 함수가 추가할 value라는 원소의 값을 미리 할당한 다음 그 후에 함수에 다시 집어넣어서 vector로 복사하거나 이동하니까..

 

굳이 value라는 변수를 만들어야하나..?

처음부터 벡터에 넣으려는 위치에서 해당 값을 가진 원소를 만들면 안되냐???

 

그래서 벡터는 emplace()와 emplace_back()을 지원한다.
성능 향상을 위해선 insert, push_back보다 위 함수를 사용한다.

 

즉, 위 함수들은 새 원소의 위치에서 객체가 바로 생성되어 함수에 객체를 전달하는 것이 아니라

생성자에 필요한 매개변수를 전달한다.

emplace() 함수는 전달된 생성자 인자를 사용해서 객체를 생성하고 삽입하는 것이다.

 

emplace종류의 함수는 원소가 생성된 위치의 iterator를 반환한다.

// vector::emplace
#include <iostream>
#include <vector>

int main ()
{
  std::vector<int> myvector = {10,20,30};

  auto it = myvector.emplace ( myvector.begin()+1, 100 );
  myvector.emplace ( it, 200 );
  myvector.emplace ( myvector.end(), 300 );

  std::cout << "myvector contains:";
  for (auto& x: myvector)
    std::cout << ' ' << x;
  std::cout << '\n';

  return 0;
}

//////////////////////////
myvector contains: 10 200 100 20 30 300

 

---

 

물론 이제 삭제 함수도 있다.

pop_back()과 erase() 함수다.

 

pop_back은 역시 생긴대로 맨 뒤의 원소를 제거하고 벡터 크기를 1 주이는 방식이다.

erase는 2가지 형태로 오버로딩 되어있다.

1. iterator를 받아서 해당 위치의 원소를 제거

2. iterator를 2개 받아서 해당 first, last [first, last] 까지 제거한다.

**first 위치에 해당하는 원소는 제거하며 last의 앞까지의 원소만 제거한다.

 

앞과 비슷한 원리니 패스

 

---

 

기타 함수로는

clear() - 벡터에 있는 모든 원소 제거

reserve(capacity) - 벡터에 용량 지정 -> capacity가 현재 용량보다 클 때 가능 (같거나 작으면 동작x)

shrink_to_fit() -  남은 용량 해제 벡터크기 = 벡터용량

**(오버헤드가 발생하지 않으려면 벡터의 크기가 변하지 않아야함)

 

 

벡터는 유용하다.

하지만 만능은 아니다.

 

쉽게 말하자면 모든 원소에 접근이 가능한 스택이라고 보면될까나..

효율적으로 작동하려면 삽입과 삭제가 스택처럼 맨 뒤에서만 일어나야한다..?

 

대부분 순차적인 삽입 삭제가 일어나 pop_back(), push_back()으로만 쓰일 경우는

벡터는 효율적이라고 알려져있다.

하지만

임의의 원소의 삽입 삭제가 일어나는 응용프로그램에서는 지양하는 것이 좋다.

 

 

++

[문제풀이(Problem Solving)/C++ 문제풀이에 유용한 것들] - vector에서 iterator 활용, 벡터 역순