[C++ STL] 벡터 (Vector)

개요

가변 길이 배열이라고 생각하면 된다.

벡터 내부의 원소들이 실제로 메모리에서 연속적으로 저장되어 있다.

시간 복잡도

• 임의 위치 원소 접근 (at, []): O(1)
• 맨 뒤에 원소 삽입 및 제거 (push_back, pop_back): O(1)
  • 엄밀하게 말하자면 amortized O(1) (amortized는 분할 상환이라는 뜻)
  • 보통 벡터는 현재 가지고 있는 원소의 개수보다 더 많은 공간을 미리 할당해 놓음 (부족할 때마다 2배씩 늘리는 방식)
  • 이런 상태에서 원소를 삽입하면 O(1)로 작동하지만, 만약 벡터가 꽉 차서 벡터의 공간을 늘려야 하는 경우 크기가 두 배인 새로운 벡터를 만들고 기존 벡터에 있는 모든 값들을 복사하는 작업을 하게 되므로 O(n)의 시간 복잡도가 소요됨
  • 다만, 이것을 평균적으로 보았을 때는 O(1)으로 수행됨을 알 수 있음

vector의 원소 push의 시간 복잡도가 일정하지 않음을 보여주는 예시

• 중간에 원소 삽입 및 제거 (insert, erase 함수): O(n)
  • 배열처럼 한 칸씩 밀어서 이동시킴
  • 중간에 데이터를 삽입하거나 제거하는 작업이 많은 경우에는 벡터 사용을 지양해야 함

주요 기능 및 특징

반복자

벡터의 반복자의 타입은 RandomAccessIterator 타입이다.

벡터 사이즈

size() 함수는 벡터의 사이즈를 size_type 타입으로 리턴한다.

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> vec;
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);
    vec.push_back(4);
    vec.push_back(5);

    std::vector<int>::size_type s1 = vec.size();
    std::cout << s1 << std::endl; // 5

    // auto 키워드가 std::vector<int>::size_type으로 자동 추론
    for (auto i = 0; i < vec.size(); i++)
    {
        std::cout << i << std::endl; // 0 1 2 3 4
    }
}

임의 원소 접근

• [] 사용
• at 함수 사용
• front, back 함수 사용

맨 뒤에 원소 삽입 / 제거

원소 삽입에 push_back(), 원소 제거에 pop_back()을 사용한다.

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> vec;

    // push_back 함수
    // 맨 뒤에 요소 push
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);
    vec.push_back(40);

    for (std::vector<int>::size_type i = 0; i < vec.size(); i++)
    {
        std::cout << "vec의 " << i + 1 << " 번째 원소: " << vec[i] << std::endl;
    }

    // pop_back 함수
    // 맨 뒤의 요소 pop
    vec.pop_back(); // 40
    vec.pop_back(); // 30

    for (std::vector<int>::size_type i = 0; i < vec.size(); i++)
    {
        std::cout << "vec의 " << i + 1 << " 번째 원소: " << vec[i] << std::endl;
    }
}

중간에 원소 삽입 / 제거

원소 삽입에 insert(), 원소 제거에 erase()를 사용한다.

• insert(std::vector<T>::iterator pos, const T& value)
  • pos 앞에 원소 삽입
• erase(std::vector<T>::iterator pos)
  • pos 번째 원소 제거
• erase(std::vector<T>::iterator first, std::vector<T>::iterator last)
  • last는 포함되지 않는 것 주의 [first, last)

참고 및 이미지 출처

모두의 코드 - 씹어먹는 C++ PDF [https://modoocode.com/312]