[c++] STL 벡터 컨테이너

개요

알고리즘 ps중 가장 많이 사용되는 stl을 뽑으라면 단연 vector containor가 1순위로 뽑힐 것이다.
그런데 계속 쓰는 메소드들만 사용하고, 어떤 메소드들이 있는지 알지도 못해서 계속 구글을 뒤지는 일이 많아졌다.
이게 좀 불편해서 여기에 정리하려 한다.

들어가기 앞서 모든 정보는 레퍼런스 사이트에서 가져왔음을 알린다.
모든 정보는 c++14를 기반으로 작성되었으며, 하위 버전 c++에서는 동작하지 않는 기능일 수 있다.

std::vector

vector container는 수열과 비슷한 컨테이너이다. 비슷한 자료구조로는 배열이 있다. 그러나 배열과는 다르게 크기를 변경할 수 있다. 그러나 크기에 비해 배열보다는 더 많은 메모리를 차지하게 된다.

vector의 특징

• 연속성
  각 요소들은 선형적으로 정렬되어 있다. 모든 요소들은 위치값을 통해 접근할 수 있다.
• 동적 배열
  각 요소들에 대해 직접적으로 접근 할 수도 있지만 포인터를 통해서도 접근할 수 있다.
• 할당자의 존재
  프로그래머가 복잡하게 메모리 동적 할당을 할 필요가 없이 알아서 메모리를 관리해 준다.

vector내 템플릿들

• T
  요소들의 자료형이다.
• Alloc
  공간을 할당하기 위해 필요한 할당자 객체의 자료형이다. 기본적으로는 allocator 클래스가 지정되어 있지만, 필요에 따라 다른 클래스로 변경할 수 있다.

멤버 함수들

1. 기초함수들

이름	내용
(생성자)	생성자이다.
(소멸자)	소멸자이다.
(operator=)	대입 연산자 오버라이딩이다.

생성자

vector의 생성자는 총 6개다.

이름	원형	설명
기본 (1)	vector();	비어있는 컨테이너 하나를 생성한다.
채움 (2)	vector (size_type n, const value_type& val, const allocator_type& alloc = allocator_type());	n의 크기를 가진 벡터하나를 생성한다. 만약 val값이 주어지면 모든 요소를 val값으로 초기화한다.
범위 (3)	template <class InputIterator> vector (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());	반복자 first,last를 입력받고 생성한 벡터를 반복자의 값으로 채운다.
복사 (4)	vector (const vector& x);	입력받은 벡터를 복사해 새로운 벡터를 생성한다.
이동 (5)	vector (vector&& x);	x라는 벡터를 그대로 옮겨서 벡터를 생성한다. 이때 x는 제거되지 않지만, 안정된 상태(valid state)로 남아있다.
리스트로 초기화(6)	vector (initializer_list<value_type> il, const allocator_type& alloc = allocator_type());	입력받은 il이라는 리스트를 그대로 복사하여 벡터를 생성한다.

다음은 레퍼런스 사이트의 예제이다.

// 벡터의 생성자들
#include <iostream>
#include <vector>

int main ()
{
 // 상단의 표와 같은 순서로 사용되는 생성자들.
 std::vector<int> first;                                // int자료형을 가진 벡터
 std::vector<int> second (4,100);                       // [100,100,100,100]
 std::vector<int> third (second.begin(),second.end());  // second벡터의 반복자를 통해 초기화
 std::vector<int> fourth (third);                       // 세번째 벡터를 복사함

 // 6번째 생성자는 배열로도 초기화가 가능하다.
 int myints[] = {16,2,77,29};
 std::vector<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );

 std::cout << "The contents of fifth are:";
 for (std::vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)
   std::cout << ' ' << *it;
 std::cout << '\n';

 return 0;
}

소멸자

할당자에 의해 처리되므로 호출할 일이 없다.

operator=

이름	원형	설명
복사 (1)	vector& operator= (const vector& x);	우변 벡터x를 좌변 벡터에 복사한다.
이동 (2)	vector& operator= (vector&& x);	좌변 x벡터를 우변 벡터로 옮긴다. 이때 x는 제거되지 않지만, 안정된 상태(valid state)로 남아있다.
리스트로 초기화 (3)	vector& operator= (initializer_list<value_type> il);	리스트 하나를 받아서 그 값으로 벡터를 초기화한다.

다음은 예제이다. 레퍼런스 사이트에 있는 예제를 조금 수정했다.

#include <iostream>
#include <vector>

int main()
{
    //vector 두개 생성
    std::vector<int> foo(3, 0);
    std::vector<int> bar(5, 0); 
    
    bar = foo; //foo를 bar로 복사
    std::cout << "Size of foo: " << int(foo.size()) << '\n';
    std::cout << "Size of bar: " << int(bar.size()) << '\n';

    std::vector<int> v(5,10);
    v = {1,2,3,4,5}; //벡터를 리스트로 초기화
    for (auto &item : v)
    {
        std::cout << item << std::endl;
    }
    return 0;
}

결과값은 다음과 같다.

Size of foo: 3
Size of bar: 3
1
2
3
4
5

리스트가 정상적으로 복사된 것을 확인 할 수 있다.

2.반복자 관련 함수들

반복자가 무엇인지 잘 모른다면 이 블로그를 참조해 주길 바란다. 나중에 이 블로그에도 반복자에 대해 다뤄볼 예정이다.

반복자 관련 함수들은 총 8개이고, 4개의 변수반복자들을 반환하는 함수와 4개의 상수반복자들을 리턴하는 함수들로 나누어져 있다.

이름	원형	설명
begin()	iterator begin() noexcept;	벡터의 처음 부분 반복자를 반환한다.
end()	iterator end() noexcept;	벡터의 끝 한칸 뒤(pass-the-end)를 가리키는 반복자를 반환한다.
rbegin()	reverse_iterator rbegin() noexcept;	벡터의 가장 끝 원소를 가리키는 역반복자를 반환한다. 역반복자는 반복자와 다르게 더하면 앞의 원소로, 빼면 뒤의 원소로 이동한다.
rend()	reverse_iterator rend() noexcept;	벡터의 가장 앞 원소의 앞에 위치하는 가상 요소를 만들고 그 요소를 가리키는 역반복자를 반환한다.

함수들의 앞에 'c'를 붙여주면 그 반복자의 상수형을 반환한다. (ex. cbegin() )

다음은 예제이다.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> v({1,2,3,4,5}); // 리스트를 활용한 벡터 초기화

    for(auto i = v.begin(); i < v.end(); i++) {
        cout<< *i << endl; // 반복자를 이용한 순차탐색
    }

    for(auto i = v.rbegin(); i < v.rend(); i++) {
        cout<< *i << endl; // 역반복자를 이용한 역순차탐색
    }
}

3.크기 관련 함수들

벡터는 두가지 크기를 가지고있다. 'size'는 벡터의 요소의 크기, 'capacity'는 메모리의 크기이다. 이런 두가지 크기를 가지게 된 이유는 벡터의 동적성에 있다.
배열은 처음 정한 크기가 변하지 않는다. 그러나 벡터는 원래 메모리 크기가 어떠했든 자유자재로 줄어들고 늘어날 수 있다. 그러나 메모리를 처음부터 크게 할당하거나 아예 원소가 늘어날때마다 메모리를 늘려버리면 효율이 매우 떨어진다.
그렇기에 size가 capacity를 넘어설때마다 벡터는 size*2의 메모리를 할당한다. 이런 구조들 때문에 벡터에는 크기 관련 함수들이 다양하게 존재한다.

다음은 벡터의 크기관련 함수들이다.

이름	원형	설명
size()	size_type size() const noexcept;	요소들의 개수를 반환한다.