2024-09-27 • 8 min read

stl[1] - Vector와 Pair

STL의 기본인 Vector와 Pair에 대해서 보도록 합니다.

Vector

vector 헤더 안에 작성되어 있습니다.

std::vector is a sequence container that encapsulates dynamic size arrays.

레퍼런스 사이트에 의하자면, vector는 sequence container로서
dynamic size array를 캡슐화 하여 제공한다고 합니다.

여기서 sequence container는 순차 컨테이너 로 번역될 수 있는데, 순차적으로 데이터를 저장하는 Array를 생각하면 가장 정확할 것 같습니다. 즉, vector는 dynamic size array, 동적 크기 확장을 지원하는 배열 자료구조가 되겠네요

Vector는 배열과 큰 차이가 없기 때문에 쉽게 사용을 검토해 볼 수 있으면서, std::sort 알고리즘 함수를 편리하게 사용할 수 있기 때문에 사용할수록 편리해집니다.

배열과 큰 차이가 없이 순차적으로 배치되어 있다는 특징 때문에, 기존 stl의 순회 방법인 iterator를 사용한 접근 방법 외에도 braket operator [] 를 사용해 random access를 O(1)에 할 수 있습니다.
이는 다시 말해 일반 배열과 완전히 동일한 방법으로도 사용할 수 있다는 것입니다.

Vector's member function.

front(), back()

배열의 앞 원소와 뒷 원소를 가져오는 멤버 펑션입니다.
각각 V[0], V[V.size()-1] 과 동일합니다.
시간복잡도는 O(1) 입니다.

size()

배열의 크기를 반환합니다.
굳이 계산하자면 sizeof(V) / sizeof(V[0]) 정도가 됩니다.
시간복잡도는 O(1) 입니다.

push_back()

배열의 뒤에 원소를 추가하는 멤버 펑션입니다.
배열의 크기가 1 증가하며, 값도 동시에 들어갑니다.

V.push_back(12345); 와 같이 사용합니다.

시간복잡도가 Amortized O(1) 으로 꽤나 복잡한 편입니다. Vector 컨테이너의 구현을 위해 어쩔수 없이 이러한 시간복잡도를 가지게 되었는데, 설명이 굉장히 길게 필요하다 보니 아마 별도의 글로 분리할 것 같습니다.

pop_back()

배열의 뒤 마지막 원소를 삭제합니다.
배열의 크기가 1 감소하지만, 배열의 capacity == 메모리 용량은 줄어들지 않습니다.
시간복잡도는 O(1) 입니다.

begin(), end()

배열의 앞 iterator와 뒷 iterator를 가져오는 멤버 펑션입니다.
*it를 통해 출력해보면 각각 V[0], V[V.size()] 와 동일합니다.

V[V.size()-1]을 참조하는 rbegin() 과
V[-1]을 참조하는 rend() 도 존재합니다.

iterator의 축약 구문을 사용하면 Vector에 대한 출력을 굉장히 편리하게 진행할 수 있습니다.
시간복잡도는 O(1) 입니다.

int main(){
  vector<int> V;
  V.push_back(1);
  V.push_back(2);
  V.push_back(3);
  V.push_back(4);
  V.push_back(5);
  for(int k : V){
    cout << k << "\n";
  }
}

Vector의 사용처

기존의 배열이 사용하던 거의 모든 곳에서 그 역할을 대체 할 수 있으며, 대체 했을 경우 iterator를 사용 가능하게 되므로 일반 배열보다 정렬이나 최대/최솟값 등을 구하기가 압도적으로 편해집니다.

개인적으로는 추후 다루게 될 <Algorithm> 헤더의 함수들과 사용하기 편하게 하기 위해서

#define all(v) v.begin(), v.end() 매크로 상수 정의를 통해서 "처음부터 끝까지" 에 대한 정의를 미리 해두고 있습니다.

이 경우 정렬을 할 때 sort(all(V)) 로 정렬할 수 있어 매우 편리합니다.

Pair

std::pair는 별다른 멤버 함수가 크게 존재하지 않는 아주 간단한 형태의 자료구조입니다. 기본으로

== operator
> operator
< operator

등의 비교 연산자가 적용되어 있어서 비교가 가능하면서, 두 연관성 있는 값을 서로 묶어줍니다. 이는 백준 문제 해결에 있어서 대단히 유용한 특성을 가지게 되는데, 예를 들어서 {x,y} 좌표쌍을 pair에 저장하면 변수 하나에 담아 비교할 수 있어 대단히 편하게 됩니다.

pair<int,int> A = {3,5}; 와 같이 사용합니다.

Vector + Pair

Vector와 Pair를 같이 사용해 정렬을 하면 문제를 굉장히 쉽게 해결할 수 있는데, 대표적인 유형이 Silver V에 상주하고 있는 다양한 기준에 맞게 정렬하는 문제들입니다.

x좌표에 따라 정렬하고, x좌표가 같으면 y좌표에 따라서 정렬을 해야하는 문제입니다. 심지어 N이 1e5로 O(NlogN) 이상의 정렬을 사용해야 합니다.

편의상 std::sort를 통해 한번에 정렬 해주도록 하고, Vector와 Pair를 사용하지 않는 소스코드는 아래와 같습니다.

void fastio(){ cin.sync_with_stdio(0); cin.tie(0); cout.tie(0); }

struct st{
    int x;
    int y;
};

bool operator<(st A, st B){
    if(A.x != B.x) return A.x < B.x;
    return A.y < B.y;
}

st arr[123456];

int main(){
    fastio();
    int N;
    cin >> N;
    for(int i=0; i<N; i++){
        cin >> arr[i].first >> arr[i].second;
    }

    sort(arr, arr+N);

    for(int i=0; i<N; i++){
        cout << arr[i].first << " " << arr[i].second << "\n";
    }
    return 0;
}

보통 위 소스코드와 같이 < 연산자에 대한 오버로딩을 하거나, 혹은 동일한 역할을 하는 함수를 Functor로 std::sort의 세 번째 인자로 넘겨주는 방식으로 구현합니다.

이제, 이 구현을 Vector + Pair 조합으로 해보도록 하겠습니다.

vector<pair<int,int>> V;

int main(){
    fastio();
    int N;
    cin >> N;
    for(int i=0; i<N; i++){
        int a,b;
        cin >> a >> b;
        V.push_back({a,b});
    }

    sort(V.begin(), V.end());

    for(pair<int,int> now : V){
        cout << now.first << " " << now.second << "\n";
    }
    return 0;
}

iterator 가 되면서 출력을 위한 for문이 Range-Based For loop 이 되었고, 연산자가 기본으로 지정되어있기 때문에 따로 오버로딩 해줄 필요성이 없어지게 됩니다.

참고로

역순 정렬 : 음수를 붙여 저장한후 정렬하고 다시 양수로 바꾸어 출력합니다.
세가지 값 이상 : pair<int,pair<int,int>> 와 같이 pair를 중첩 사용합니다
first/second : define 구문으로 x,y로 바꿔 사용할 수 있습니다
#define x first #define y second

등을 통해 보다 편리하게 더 많은 문제들을 해결할 수 있습니다.

추후 그래프 알고리즘에서 노드 번호와 가중치를 동시에 저장하는 등의 필요에 의해 std::pair를 사용하게 되므로, 반드시 익혀둘 필요가 있습니다.

해결 가능한 문제들

boj 10814 나이순 정렬
boj 10825 국영수
boj 2535 아시아 정보올림피아드

이외 여러 정렬 기준을 적용해야 하는 Silver V~Silver III 수준의 문제들 을 쉽게 해결해 볼 수 있습니다.