C++에서 vector 제대로 알기 (feat. array, stack, deque)

벡터

메모리 heap에 동적 할당되는 자료의 길이를 변경할 수 있는 배열입니다.
쉽게 말해 자동으로 메모리가 할당되는 배열입니다. 

• 일반 배열과 동일하게 연속적인 메모리 공간에 저장합니다. (개별 원소에 대한 접근 속도가 빠름)
• iterator 뿐 아니라 index 로도 접근이 가능합니다.
• 컨테이너 끝에서 삽입 / 제거하는 속도가 빠릅니다.
• 중간의 값을 삽입하거나 삭제할 수도 있지만 배열 기반이므로 빈번하게 일어난다면 비효율적입니다.
• 동적으로 확장 및 축소가 가능한 Dynamic Array로 구현되어 있습니다.

vector 생성자와 연산자

• vector<int> v
  - 비어있는 vector v 를 생성합니다.
• vector<int> v(5)
  - 기본 값(0)으로 초기화 된 5개의 원소를 가지는 vector v를 생성합니다.
• vector<int> v(5, 2)
  - 2로 초기화된 5개의 원소를 가지는 vector v를 생성합니다.
• vector<int> v2(v1)
  - v2는 v1 vector를 복사해서 생성됩니다.

vector 멤버 함수

• v.assign(5, 2)
  - 2의 값으로 5개의 원소 할당합니다.
• v.at(idx)
  - idx번째 원소를 참조 합니다.
  - v[idx] 보다 속도는 느리지만, 범위를 결정하므로 안전합니다.
• v[idx]
  - idx 번째 원소를 참조합니다.
  - 범위를 점검하지 않으므로 속도가 v.at(idx)보다 빠릅니다.
• v.clear()
  - 모든 원소를 제거합니다.
  - 원소만 제거하고 메모리는 남아있습니다.
  - size만 줄어들고 capacity는 그대로 남아있습니다.
• v.push_back(7)
  - 마지막 원소 뒤에 원소 7을 삽입합니다.
• v.pop_back()
  - 마지막 원소를 제거합니다.
• v.begin()
  - 첫 번째 원소를 가리킵니다. (iterator 사용)
• v.end()
  - 마지막 "다음"을 가리킵니다. (iterator 사용)
• v.rbegin()
  - reverse begin()
  - 거꾸로 해서 첫 번째 원소를 가리킵니다. (iterator 사용)
• v.rend()
  - reverse end()
  - 거꾸로 해서 마지막 "다음"을 가리킵니다. (iterator 사용)
• v.reserve(n)
  - n개의 원소를 저장할 위치를 예약합니다. (미리 동적할당)
• v.resize(n)
  - 크기를 n으로 변경합니다.
  - 더 커졌을 경우 default 값 0으로 초기화 합니다.
• v.resize(n, 3)
  - 크기를 n으로 변경합니다.
  - 더 커졌을 경우 인자의 값을 3으로 초기화 합니다.
• v.size()
  - 원소의 갯수를 리턴합니다.
• v.capacity()
  - 할당된 공간의 크기를 리턴합니다.
  - 공간 할당의 기준은 점점 커지면서 capacity를 할당하게 됩니다.
• v2.swap(v1)
  - v1과 v2의 원소와 capacity를 바꿔줍니다.
  - v1의 capacity를 없앨 때 (할당한 메모리를 프로그램 끝내기전에 없애고 싶을 때) 사용
  - v2를 capacity가 0인 임시 객체로 만들어서 스왑 해줍니다.
• v.insert(2, 3, 4)
  - 2번째 위치에 3개의 4값을 삽입합니다.
• v.insert(2, 3)
  - 2번째 위치에 3값을 삽입합니다.
  - 삽입한 곳의 iterator를 반환합니다.
• v.erase(iter) or v.erase(start, end)
  - iter가 가리키는 원소를 제거합니다.
  - size만 줄어들고 capacity는 그대로 남습니다.
  - erase는 파라미터 하나를 받을 때와 두개를 받을 때 다릅니다.
• v.empty()
  - vector가 비었으면 리턴 true
  - 비어있다의 기준은 size가 0 이라는 것이므로 capacity와는 무관합니다.

 

백터의 size vs capacity

원소의 갯수를 리턴하는 v.size() 와 다르게 v.capacity()는 할당된 공간의 크기를 리턴합니다.

(String 클래스로 vector를 만들었을 때)
원소 갯수 1 -> capacity 1
원소 갯수 2 -> capacity 2
원소 갯수 3 -> capacity 4
원소 갯수 4 -> capacity 4
원소 갯수 5 -> capacity 8
원소 갯수 6 -> capacity 8
원소 갯수 7 -> capacity 16
...

• 메모리가 꽉 차면 기존 메모리의 x2 로 증가합니다.
• 이런 메모리 방식은 push_back이 일어날 때마다 동적 할당을 하면 비효율적이므로,
  미리 정해둔 만큼 동적할당을 한번에 하는 것입니다.
  
  

원소 개수가 증가하면서 메모리 증가해서 따로 할당하게 되면 기존 위치에 메모리를
이어서 할당하지 않고 새롭게 메모리를 할당해 원소들을 전부 복사하는 형태입니다.

 

벡터의 iterator

#include <bits/stdc++.h>
using namespace std;

int main(){
    vector<int> v;
    for(int i=0 ; i<10 ; i++){
        v.push_back(i);
    }

    for(auto it = v.begin() ; it != v.end() ; it++){
        it(*it % 2 == 0){
            if(*it % 2 == 0){
                *it = 2;
            }
        }
    }

    return 0;
}

begin(), end()는 vector 안의 원소를 참조하여 사용하고 iterator 값을 반환하기 때문에
해당 원소 값을 사용하려면 포인터와 같이 *를 붙여주어야 합니다.

 

벡터의 접근 방법 3가지

#include <bits/stdc++.h>
using namespace std;

int main(){
    vector<int> v;
    for(int i=0 ; i<10 ; i++){
        v.push_back(i);
    }

    cout << v.at(1) << " ";
    cout << v[1] << " ";
    cout << v.front() << " ";
    cout << v.back() << " "

    return 0;
}

1. at은 범위를 검사하기 때문에 범위 밖 인덱스가 들어오면 out of range 에러가 발생합니다.
2. [idx]는 범위 검사를 하지 않으므로 범위 밖 인덱스가 들어와도 에러가 발생하지 않습니다. (주의 필요)
3. front, back은 맨 앞과 뒤의 요소를 참조합니다.

 

벡터의 삽입 / 삭제 방법 

#include <bits/stdc++.h>
using namespace std;

int main(){
    vector<int> v = {1, 2, 3, 4, 5};
    
    v.push_back(6);                // [1, 2, 3, 4, 5, 6]
    v.emplace_back(7);         // [1, 2, 3, 4, 5, 6, 7]
    v.insert(2, 10);                    // [1, 2, 10, 3, 4, 5, 6, 7]
    v.pop_back();                    // [1, 2, 10, 3, 4, 5, 6]
    v.emplace(3, 9);               // [1, 2, 10, 9, 3, 4, 5, 6]
    v.erase(2);                        // [1, 2, 9, 3, 4, 5, 6]
    v.clear();                           // [ ]
}

push_back vs emplace_back

push_back은 메모리 할당을 하지 않고 데이터를 삽입하기만 합니다. (O(1))

객체를 삽입하기 위해 똑같은 임시 객체를 하나 더 만들어 거기 복사한 후 벡터에 삽입합니다.
삽입이 끝나면 임시 객체를 파괴합니다.
잠시 쓰고 버릴 객체를 굳이 할당해줌으로써 불필요한 연산이 생깁니다.

emplace_back은 벡터에 메모리를 할당하는 동시에 값을 삽입하는 것이 가능합니다.

가변인자 템플릿을 사용해 삽입하려는 자료형에 따라 함수 내 삽입을 위한 객체를 자체 생성합니다.
즉, 똑같은 임시 객체를 만들 필요가 없습니다. 파괴해야 할 객체 자체가 생기지 않습니다.
잠시 쓰고 버릴 객체를 할당할 필요가 없다는 뜻이므로 push_back에 비해 효율적입니다.
특히 다중 parameter를 사용할 때 유용합니다.
다만 에러가 발생하는 경우가 많은 함수인만큼 사용할 때 충분한 이해가 필요합니다. 

emplace_back 활용 예시

vector<vector<int>> v;
v.push_back(2)               // 불가능
v.emplace_back(2)        // 가능

2차원 백터를 생성하고 행의 길이는 정할 수 있지만
열의 길이는 데이터 상황에 따라 변하여 할당해주기 어려울 때 emplace_back 를 사용하면
2차원 벡터의 행만 할당하고 각 행의 사이즈는 0인 상태로 할당됩니다.

 

emplace_back이 push_back의 상당 부분 대체할 수 있지만
다른 사람들과 함께 하는 프로젝트라면 호환성을 위해 push_back을 사용하는게 좋습니다.
emplace_back 함수는 개인 프로젝트나 코딩 테스트 알고리즘 문제풀이로 사용하는 것을 권장합니다.

insert와 erase

insert의 경우 모든 값을 새로운 메모리에 복사한 후 해당 자리에 값을 넣습니다. (O(n))

insert와 erase 모두 해당 위치에 원소를 넣을 때 다른 원소 데이터를 하나하나 이동시킵니다.
이 방식은 vector의 크기를 재할당하는 문제를 야기할 수 있기 때문에
삽입,삭제가 빈번하다면 list나 deque를 사용하는게 더 좋습니다.

clear

clear 함수를 실행하면 벡터 요소들만 사라지고 할당된 크기는 그대로 남습니다.

이는 공간 비효율로 이어질 수 있기 때문에 swap() 함수를 사용해서 완벽하게 공간을 해제해주어야 합니다.
하지만 이 경우 한 개의 함수 안에서 재활용되는 경우에만 사용해야 합니다.
함수가 바로 종료되는 경우 어차피 힙에서 메모리 해제가 자동으로 이루어져 굳이 하지 않아도 됩니다.

 

벡터의 메모리 확장

#include <bits/stdc++.h>
using namespace std;

int main(){
    vector<int> v = {1, 2};

    if(v.empty()) {
        cout << "빈 배열" << endl;
    } else {
        cout << "안에 원소가 있습니다 << endl;
    }
    
    v.max_size();        // 벡터에 들어갈 수 있는 최대 값 리턴
    v.size();                 // 벡터의 현재 사이즈 : 2
    v.capacity();         // 벡터에 할당해준 사이즈 : 사용자가 할당해준 사이즈마다 다름
    v.reserve(6);        // 벡터 크기 변경 ( = v.resize(6))
    v.capacity();         // 6
    v.resize(2);           // 늘어난 버퍼를 줄이고 싶을 경우 사용
    v.shrink_to_fit();
    v.capacity();         // 2

    return 0;
}

vector의 capacity 이상으로 원소가 채워진다면 capacity가 재할당됩니다. (O(n))
재할당되는 것은 비효율적이므로 그 전에 reserve나 resize로 capacity를 가변적으로 늘릴 수 있습니다.
큰 capacity에 비해 적은 원소가 들어와도 size를 줄이고
swap이나 shrink_to_fit()을 통해 버퍼를 줄일 수 있습니다.

 

메모리 확장에 비용은 왜 클까? 

vector의 특징은 메모리 상의 시퀀스를 유지하려고 합니다. (속도가 빠른 이유)
하지만 공간이 부족하게 되면 기존에 있던 요소들과 함께 새로운 메모리를 할당 받아야 합니다. (시퀀스 유지를 위해)
쉽게 말해 방 하나를 더 갖기 위해 큰 집으로 이사가는 것 입니다.

결과적으로 vector는 더 큰 공간을 새로 할당하면서 적지 않은 오버헤드가 발생합니다.
이런 문제를 reserve 함수로 미리 할당 후 재할당을 예방하는 것입니다.

C++부터 Move semantic으로 이 동작 비용이 크게 감소함

 

벡터 vs 배열

배열은 고정된 자료구조로 선언해줄 때 크기를 반드시 지정해주어야 합니다. 

이러한 배열의 문제점을 해결하기 위해 배열을 동적 할당하여 사용해야 했습니다.
그 방법 중 하나로 고안된 vector는 크기가 가변적인 배열을 만들어주는 특징을 가지고 있습니다.

• 속도와 성능은 배열이 vector보다 좋습니다. 
  따라서 크기가 가변적이지 않다면 그냥 배열을 사용하는게 좋습니다.
• vector가 메모리 관리 측면에서 배열보다 좋기 때문에
  배열의 크기가 가변적이고 얼마만큼의 원소가 들어올 지 예상할 수 없다면 vector를 사용하는게 더 좋습니다.

 

벡터 vs 스택

알고리즘 문제를 풀다 보면 stack과 vector 자료구조를 사용해야 할 때가 자주 발생합니다.
vector을 사용하여 문제를 풀던 도중 stack 자료구조와의 속도 차이가 궁금하여 측정해 보았습니다.

vector와 stack을 비교하면 수치상 큰 속도 차이가 발생합니다.
왜 그럴까요?

stack의 특징을 이해하면 쉽게 이해할 수 있습니다.

vector, deque, list container 같은 내부 컨테이너와 달리 stack은 내부 컨테이너가 없습니다.
stack은 자체적으로 stack을 처리하는 것이 아니라 표현을 제한하는 껍데기일 뿐
실제로 구현을 담당하는 것은 다른 컨테이너에게 위임하는 것입니다.
따라서 stack을 선언하고 사용하면 기본 값은 deque가 선언됩니다.

• 알고리즘 문제를 풀 때는 vector를 사용하는게 훨씬 빠릅니다.
• vector를 사용하면 배열로 쓰려는 건지 stack으로 쓰려는 건지 모호해 가독성이 떨어집니다.
  대형 프로젝트나 협업이 필요할 때는 가독성을 위해 vector로 구현한 stack을 사용하는게 좋습니다.

 

백터 vs 덱

deque는 vector의 단점을 보완하기 위해 만들어진 container 입니다.

vector와 비슷한 점이 많지만 deque는 컨테이너 끝 부분과 첫 부분의 삽입,제거도 효율이 높습니다.
deque는 Random access iterator를 통한 index로 접근이 가능합니다.
동적으로 확장, 축소가 가능한 Dynamic Array로 구현되어 있습니다.
그리고 가장 큰 차이점은 연속된 메모리에 올라가 있지 않습니다.
몇 바이트 단위의 chunk로 쪼개어져 있으며 이 chunk는 내부적으로 관리가 됩니다.

반복자

• 입력 반복자(input iterator)
  - 현 위치의 원소를 한 번만 읽을 수 있는 반복자
  - ex. istream
• 출력 반복자(output iterator)
  - 현 위치의 원소를 한 번만 쓸 수 있는 반복자
  - ex. ostream
• 순방향 반복자(forward iterator)
  - 입력, 출력 반복자 기능에 순방향으로 이동(++)이 가능한 재할당될 수 있는 반복자
  - ex. replace
• 양방향 반복자(bidirectional iterator)
  - 순방향 반복자 기능에 역방향으로 이동(--)이 가능한 반복자
  - list, set, multiset, map, multimap
• 임의 접근 반복자(random access iterator)
  - 양방향 반복자 기능에 +, -, +=, -=, [ ] 연산이 가능한 반복자
  - vector, deque

• vector는 새 원소 추가에 메모리 재할당 후 이전 원소를 복사하는 방식으로 삽입 시 성능이 저하됩니다.
• deque는 이러한 vector의 단점을 보완하기 위해서 이전 원소를 복사하지 않는 방식을 사용합니다.
  -> 여러 개의 메모리 블록을 할당하고 하나의 블록처럼 여기는 기능을 제공합니다.
• 저장 원소가 많고 메모리 할당량이 큰 경우 vector에 비해 확장 비용이 절감됩니다.
  -> 전체가 재할당되는 vector보다 늘어나야 하는 크기만큼의 chunk가 하나 더 할당되기 때문입니다.

단, 연속적인 메모리 공간이 아니므로,
vector에서 가능했던 원소들 간 포인터 연산이 불가능합니다.

---

참조 : https://imksh.com/13

[C++] vector가 꼭 정답일까? vector, deque, list 비교

참조 : https://cannabuffer.tistory.com/entry/C-STL-Vector

[C++ STL] Vector

참조 : https://hgu-can.tistory.com/entry/C-stdvector-pushback-vs-emplaceback-%EC%B0%A8%EC%9D%B4%EC%A0%90

[C++] std::vector push_back vs emplace_back 차이점

참조 : https://openmynotepad.tistory.com/10

emplace_back 과 push_back 의 차이

참조 : https://blockdmask.tistory.com/76

[C++] list container 정리 및 사용법