티스토리 뷰
vector 컨테이너는 C++에서 자주 사용되는 컨테이너로 GeeksforGeeks에서는 다음과 같이 정의되어 있습니다 :
벡터는 요소가 삽입되거나 삭제 될 때 자동으로 크기를 조정할 수 있는 동적 배열과 동일하며 컨테이너에서 자동으로 처리합니다. 벡터 요소는 반복자를 사용하여 액세스하고 통과 할 수 있도록 인접한 저장소에 저장됩니다. 벡터에서는 데이터가 끝에 삽입됩니다. 때때로 배열을 확장 할 필요가있을 수 있기 때문에 마지막에 삽입할 때 시간이 달라질 수 있습니다(differential time). 마지막 요소를 제거하면 크기 조정(resizing)이 발생하지 않으므로 상수 시간이 소요됩니다(또는 상수 시간 복잡도를 가집니다). 시작 또는 중간에 삽입하거나 및 제거하는 것은 선형 시간(linear in time)입니다.
또한 cppreference에서는 더욱더 자세히 정의합니다 :
벡터의 저장은 필요에 따라 자동으로 처리되어 확장 및 축소됩니다. 벡터는 컨테이너가 자라는 것을 핸들하기 위해 더 많은 메모리를 할당하기 때문에 일반적으로 정적 배열(static memory)에 비해 더 많은 공간을 차지합니다. 이 방법은 요소(element)가 삽입될 때마다 메모리를 벡터를 다시 할당할 필요가 없게 만들며, 오직 메모리가 모두 소진되었을 때만 추가적인 메모리를 위해 재할당됩니다. 할당된 메모리의 총량은 capacity() 함수를 통해서 질의할 수 있습니다. 여분의 메모리는 shrink_to_fit() 함수를 통해서 시스템에 되돌려질 수 있습니다(snce C++11)
재할당은 일반적으로 퍼포먼스의 관점에서 비싼 연산입니다. reverse() 함수는 요소의 수를 미리 알고 있는 경우 재할당을 제거하는 데 사용될 수 있습니다.
벡터에 대한 일반적인 연산에 대한 복잡도는 다음과 같습니다 :
- 임의 접근 = constant O(1)
- 벡터의 끝에 요소를 추가하거나 삽입 - O(1)
- 요소를 삽인하거나 제거하는 것 - 벡터 끝까지의 거리 n에 대해 O(n)
std::vector(bool 이외의 경우 T에 대해)는 Container, AllocatorAwareContainer, SequenceContainer, ContiguousContainer(since C++17) 및 ReversibleContainer를 만족합니다.
아래에서는 vector에 대해서 알아보도록 하겠습니다.
생성자(Constructors)
vector의 원형은 std::vector<T, Allocator>::vector로 수많은 생성자를 지원하고 있습니다.
1. 디폴트 생성자. 빈 컨테이너를 생성합니다. allocator가 제공되지 않는다면, allocator는 디폴트로 생성되는 인스턴스로부터 얻어집니다.
/* until C++17 */
vector();
explicit vector( const Allocator& alloc );
/* since C++17 */
vector() noexpt( const Allocator& alloc );
explicit vector( const Allocator& alloc ) noexpt;
2. count 개수만큼 요소를 값 복사하여 컨테이너를 생성합니다.
/* until C++11 */
explicit vector(size_type count, const T& value = T(), const Allocator& alloc = Allocator());
/* since C++11 */
vector(size_type count, const T& value, const Allocator& alloc = Allocator());
3. 디폴트로 삽입되는 T의 인스턴스를 count 개수만큼 가진 컨테이너를 생성합니다. 복사가 수행되지 않습니다.
/* since C++11 ,until C++14 */
explicit vector( size_type count );
/* since C++14 */
explicit vector( size_type count, const Allocator& alloc = Allocator() );
4. 범위가 지정되어 있는 컨텐츠들을 포함하는 컨테이너를 생성합니다 : [first, last).
- 이 생성자는 InputIt가 온전한 타입이면, vector(static_cast(first), static_cast(last), a)와 같습니다(until C++11)
- 이 오버로드는 InputIt이 LegacyInputIterator 를 만족할 때에, (2)번 오버로드와의 모호성을 회피할 때만 참여합니다.
template<class InputIt>
vector( InputIt first, InputIt last, const Allocator& alloc = Alocator() );
5. 복사 생성자입니다. 다른 것의 컨텐츠의 복사본을 가진 컨테이너를 생성합니다. alloc이 제공되지 않으면, allocator는 호출된 것에 의해 얻어집니다( std::allocator_traits::select_on_container_copy_construction(other.get_allocator()) ).
vector( const vector& other );
/* since C++11 */
vector( const vector& other, const Allocator& alloc );
6. 이동 생성자입니다. 이동 시맨틱을 사용하여 other의 컨텐츠를 가진 컨테이너를 생성합니다. Allocator는 other가 가지고 있는 allocator로부터 이동 생성에 의해 얻어집니다. 이동(move) 이후, other는 empty()여야 함을 보장받습니다.
/* since C++11, until C++17 */
vector( vector&& other );
/* since C++17 */
vector( vector&& other ) noexpt;
7. Allocator가 확장된 이동 생성자입니다. 새로운 컨테이너에 대해 alloc을 allocator로 사용하여, other로부터 컨텐츠들을 이동합니다; 만약 alloc != other.get_allocator()이면, 이것은 요소 별로(element-wise) 이동하는 결과를 초래합니다( 이 경우, other은 move 이후 empty여야함을 보장받지 못합니다 ).
/* since C++17 */
vector( vector&& other, const Allocator& alloc );
8. 이니셜라이저 리스트 init의 내용물들을 가진 컨테이너를 생성합니다.
/* since c++11 */
vector( std::initializer_list<T> init, const Allocator& alloc = Allocator() );파라미터
| alloc | 이 컨테이너의 모든 메모리 할당에 사용할 할당자 |
| count | 컨테이너의 크기 |
| value | 컨테이너가 포함하는 요소들을 초기화할 값 |
| first, last | 복사할 요소들의 범위 |
| other | 컨테이너가 가질 요소들을 초기화하는 데 소스로 사용되어야 할 다른 컨테이너 |
| init | 컨테이너가 가질 요소들을 초기화할 이니셜라이저 리스트 |
복잡도
| 1 | 상수 복잡도 |
| 2-3 | count에 대한 선형 복잡도 |
| 4 | first와 last 간의 거리에 대한 선형 복잡도 |
| 5 | other의 size에 대한 선형 복잡도 |
| 6 | 상수 |
| 7 | alloc != other.get_allocator()일 때, 선형 복잡도, 아닐 때 상수 복잡도 |
| 8 | init의 size에 대한 선형 복잡도 |
예외
| Allocator::allocate를 호출하는 것이 예외를 던질 수 있습니다. |
반복자(Iterators)
반복자는 컨테이너를 순회할 수 있도록 도와주는 요소입니다. std::vector에서는 다음과 같은 반복자들을 사용할 수 있습니다 :
| begin() | 벡터의 첫 번째 요소를 가리키는 반복자를 반환합니다. |
| end() | 벡터의 마지막 요소의 다음을 가리키는 이론적인 요소(theorectical element)를 가리키는 반복자를 반환합니다. |
| rbegin() | (반대 방향에서 시작하는) 벡터의 마지막 요소를 가리키는 역방향 반복자를 반환합니다. 마지막 요소에서 첫 번째 요소로 이동합니다. |
| rend() | 벡터의 첫 번째 요소 앞에 오는 이론적인 요소(theorectical element)를 가리키는 역방향 반복자를 반환합니다. |
| cbegin() | 벡터의 첫 번째 요소를 가리키는 const 반복자를 반환합니다. |
| cend() | 벡터의 마지막 요소의 다음을 가리키는 이론적인 요소(theorectical element)를 가리키는 const 반복자를 반환합니다. |
| crbegin() | (반대 방향에서 시작하는) 벡터의 마지막 요소를 가리키는 const 역방향 반복자를 반환합니다. 마지막 요소에서 첫 번째 요소로 이동합니다. |
| crend() | 벡터의 첫 번째 요소의 다음을 가리키는 이론적인 요소(theorectical element)를 가리키는 const 반복자를 반환합니다. |
사용법
- 반복자를 통해 손쉽에 vector 컨테이너를 정방향 또는 역방향으로 순회할 수 있습니다. 예시는 다음과 같습니다 :
#include <vector>
#include <iostream>
using namespace std;
int main()
{
vector<int> vec;
/* 원소를 0에서 4까지 삽입합니다.
* 결과 : [1, 2, 3, 4, 5] */
for (int i = 1; i <= 5; ++i)
{
vec.push_back(i);
}
/* for문을 이용한 순회(정방향)
* 출력 결과 : "1 2 3 4 5" */
for (auto it = vec.begin(); it != vec.end(); ++it)
{
cout << *it << " ";
}
/* for-range문을 이용한 순회(정방향)
* 출력 결과 : "1 2 3 4 5" */
for (auto it : vec)
{
cout << it << " ";
}
/* for-range문을 이용한 순회(정방향, const)
* 출력 결과 : "1 2 3 4 5" (단, 요소의 값을 변경하는 것이 불가능) */
for (const auto& it : vec)
{
cout << it << " ";
}
/* for문을 이용한 순회(역방향, const)
* 출력 결과 : "5 4 3 2 1" (단, 요소의 값을 변경하는 것이 불가능) */
for (auto it = vec.crbegin(); it != vec.crend(); ++it)
{
cout << *it << " ";
}
return 0;
}
일반적으로 배열의 처음부터 끝까지 순회하는 경우 for-range문을 이용해서 순회하는 것이 코드를 짜기에는 덜 타이핑해서 선호하는 편입니다. const iterator의 경우, vector를 순회하면서 요소를 조작할 필요가 없는 경우, 반드시 붙여주시는 것이 좋습니다.
용량(Capacity)
| size() | 벡터 요소의 개수를 반환합니다. |
| max_size() | 벡터가 가질 수 있는 요소의 최대 개수를 반환합니다. |
| capacity() | 요소의 수로 표현된 벡터에 현재 할당된 저장 공간의 크기를 반환합니다. |
| resize(const size_t) | 컨테이너를 입력된 사이즈만큼으로 조정합니다. 초과된 요소들은 삭제됩니다. 이것으로 size() 결과값이 변화할 수 있지만, capacity()는 고정됩니다. |
| empty() | 컨테이너가 비었는 지 여부를 반환합니다. |
| shrink_to_fit() | 컨테이너의 capacity를 크기에 맞게 줄이고 capacity를 초과하는 모든 요소들을 파괴합니다. 이것으로 size() 결과값이 고정되지만, capacity()는 변화합니다. |
| reserve() | 최소한 n개의 요소들을 담기에 충분하도록 vector에 요청합니다. |
벡터는 연속적인 메모리를 가지는 컨테이너로써, 메모리 공간을 전부 사용중일 때 추가적인 입력을 받는다면, 컴파일러에 따라 다르지만 기존 벡터의 capacity의 1.5배 ~ 2배 정도 확장된 메모리를 새로 할당하여 기존 벡터를 옮겨담는 작업을 수행합니다.
사용법
#include <vector>
#include <iostream>
using namespace std;
int main()
{
vector<int> vec;
/* 원소를 0에서 15까지 삽입합니다. */
for (int i = 1; i <= 15; ++i)
{
vec.push_back(i);
}
/* size() : 벡터가 담고 있는 요소의 개수를 반환합니다
* 결과 : 15 */
cout << vec.size() << endl;
/* max_size() : 벡터가 가질 수 있는 요소의 최대 개수를 반환합니다
* 결과 : 4611686018427387903 */
cout << vec.max_size() << endl;
/* capacity() : 현재 할당된 저장 공간의 크기를 반환합니다
* 결과 : 19 */
cout << vec.capacity() << endl;
/* resize(10) : 벡터의 요소를 10개로 만듭니다
* 결과 : 1 2 3 4 5 6 7 8 9 10 (11이후부터는 절삭) */
vec.resize(10);
cout << vec.capacity() << endl; /* 19 */
cout << vec.size() << endl; /* 10 */
/* empty() : 벡터가 비었는 지를 bool로 반환합니다
* 결과 : false */
cout << vec.empty() << endl;
/* shrink_to_fit() : capacity를 size만큼으로 축소합니다.
* 결과 : */
vec.shrink_to_fit();
cout << vec.capacity() << endl; /* 10 */
cout << vec.size() << endl; /* 10 */
vec.push_back(11);
cout << vec.capacity() << endl; /* 15 */
cout << vec.size() << endl; /* 11 */
/* reserve() : 컨테이너의 capacity를 지정한 수만큼 확보합니다 */
vec.reserve(20);
cout << vec.capacity() << endl; /* 20 */
cout << vec.size() << endl; /* 11 */
return 0;
}
요소 접근(Element access)
| 참조 연산자 [g] | 벡터의 'g'번째 위치의 요소에 대한 레퍼런스를 반환합니다. |
| at(g) | 벡터의 'g'번째 위치의 요소에 대한 레퍼런스를 반환합니다. |
| front() | 벡터의 첫 번째 요소에 대한 레퍼런스를 반환합니다. |
| back() | 벡터의 마지막 요소에 대한 레퍼런스를 반환합니다. |
| data() | 벡터가가 소유한 요소들을 저장하는 데 내부적으로 사용하는 메모리 배열에 대한 직접 포인터(direct pointer)를 반환합니다. |
벡터는 배열을 흉내내기 위해 요소에 접근할 수 있는 [] 연산자를 제공하고 있지만 범위 밖의 인덱스를 참조하게 되면 raw 배열과 마찬가지로 미정의된 동작을 유발할 수 있습니다. 이 때 at(g) 함수를 통해 요소에 접근한다면, 범위 밖 인덱스에 대해 예외를 던지므로 조금 더 안전하게 접근할 수 있습니다.
사용법
#include <vector>
#include <iostream>
using namespace std;
int main()
{
vector<int> vec;
/* 원소를 0에서 15까지 삽입합니다. */
for (int i = 1; i <= 15; ++i)
{
vec.push_back(i);
}
/* 참조 연산자 []
* 결과 : 5 */
cout << vec[4] << endl;
/* at(g)
* 결과 : 15 */
cout << vec.at(14) << endl;
/* front()
* 결과 : 1 */
cout << vec.front() << endl;
/* back()
* 결과 : 15 */
cout << vec.back() << endl;
/* data()
* 결과 : vec의 주소 */
cout << vec.data() << endl;
cout << *vec.data() << endl; /* 1 */
return 0;
}
수정자(Modifiers)
| assign(...) | 벡터의 요소들을 이전의 값들을 대체하면서 새로운 값들로 할당합니다. |
| push_back(g) | 요소 'g'를 벡터의 마지막에 삽입합니다. |
| pop_back() | 벡터의 마지막 요소를 팝(pop)하거나 제거하는 데 사용됩니다. |
| insert(...) | 지정된 위치의 요소 앞에 새 요소를 삽입합니다. |
| erase(...) | 지정된 위치나 범위의 요소들을 제거하는 데 사용됩니다. |
| swap(...) | 하나의 벡터의 내용물을 같은 타입의 다른 벡터와 스왑합니다. 크기가 달라집니다. |
| clear() | 벡터 컨테이너의 모든 요소들을 제거하는 데 사용됩니다. |
| emplace(g) | 지정된 위치에 새 요소 'g'를 삽입하면서 컨테이너를 확장합니다. |
| emplace_back(g) | 벡터 컨테이너의 새 요소 'g'를 삽입하는 데 사용되며, 새 요소는 벡터의 끝에 추가됩니다. |
사용법
#include <vector>
#include <iostream>
using namespace std;
int main()
{
vector<int> vec;
/* 원소를 0에서 15까지 삽입합니다. */
for (int i = 1; i <= 15; ++i)
{
vec.push_back(i);
}
/* assign(std::initializer_list)
* 결과 : 5 4 3 2 1 */
vec.assign({ 5,4,3,2,1 });
/* assign(std::vector<T>::iterator, std::vector<T>::iterator>)
* 결과 : 8 7 6 5 4 3 2 */
vector<int> vec_assign2 = { 2, 3, 4, 5, 6, 7, 8 };
vec.assign(vec_assign2.rbegin(), vec_assign2.rend());
/* assign(const size_t, const T&)
* 결과 : 5 5 5 */
vec.assign(3, 5);
/* push_back(T&& or const T&)
* 결과 : 5 5 5 3 */
vec.push_back(3);
/* pop_back()
* 결과 : 5 5 5 */
vec.pop_back();
/* insert(std::vector<T>::const_iterator, std::initializer_list)
* 결과 : 5 5 1 2 3 4 5 */
vec.insert(vec.begin() + 2, { 1,2,3,4 });
/* insert(std::vector<T>::const_iterator, std;::vector<T>::iterator, std::vector<T>::iterator)
* 결과 : 10, 20, 30, 5, 5, 1, 2, 3, 4, 5 */
vector<int> vec_insert2 = { 10, 20, 30, 40 };
vec.insert(vec.begin(), vec_insert2.begin(), vec_insert2.end() - 1);
/* insert(std::vector<T>::const_iterator, const size_t, const T&)
* 결과 : 10, 20, 30, 5, 5, 1, 2, 3, 4, 5, 24, 24 */
vec.insert(vec.end(), 2, 24);
/* insert(std::vector<T>::const_iterator, const T& or T&&)
* 결과 : 10, 20, 30, 40, 5, 5, 1, 2, 3, 4, 5, 24, 24*/
vec.insert(vec.begin() + 3, 40);
/* erase(std::vector<T>::const_iterator)
* 결과 : 10, 20, 30, 40, 5, 5, 1, 2, 3, 4, 5, 24
* 반환 : 삭제할 요소의 다음 요소의 위치를 가리키는 반복자
* 경고 : 인자로 end()를 집어넣으면 미정의된 행동을 유발합니다. */
vec.erase(vec.end() - 1);
/* erase(std::vector<T>::const_iteraotr, std::vector<T>::const_iterator)
* 결과 : 10, 20, 30, 40, 1, 2, 3, 4, 5, 24
* 주의 : 두 번째 인자로 들어가는 반복자의 위치에 있는 원소는 삭제되지 않습니다.
* 즉, begin() + 4, begin() + 5의 요소만 삭제됩니다 */
vec.erase(vec.begin() + 4, vec.begin() + 6);
/* swap(std::vector<T>&)
* 결과 : 5, 4, 3, 2, 1 */
vector<int> vec_swap = { 5, 4, 3, 2, 1 };
vec.swap(vec_swap);
/* clear()
* 결과 : 아무 요소도 없음 */
vec.clear();
/* emplace(std::vector<T>::iterator, T&&)
* 결과 : 5 */
vec.emplace(vec.begin(), 5);
/* emplace_back(T&&)
* 결과 : 5, 10 */
vec.emplace_back(10);
return 0;
}
push_back vs emplace_back
- push_back은 삽입할 객체를 받지만, emplace_back은 삽입할 객체의 생성자를 위한 인자를 받아 vector 내에서 직접 객체를 생성합니다. 이러한 행동은 매개 변수 전달에 소요되는 임시 객체의 생성, 복사, 파괴의 비용을 지불하지 않아도 되므로 성능상 더 유리합니다.
- 자세한 내용은 https://stackoverflow.com/questions/4303513/push-back-vs-emplace-back 를 참조하시기 바랍니다.
다른 컨테이너와의 비교
vector vs list
- 벡터는 미리 일정 크기의 메모리를 할당해 놓고, 그 이상의 값들이 추가되면 더 큰 메모리를 할당하여 요소들을 옮깁니다(연속적 메모리).
- 요소를 마지막에 추가/제거하는 연산이 리스트보다 빠릅니다.
- 요소를 삭제하여도 메모리 해제를 하지 않습니다(clear 함수 역시).
- 임의 접근이 가능합니다. 탐색의 경우, O(1)입니다.
- 리스트는 엘리먼트를 추가할 때마다 메모리를 할당합니다(비연속적 메모리).
- 요소를 중간에 추가/제거하는 연산이 벡터보다 빠릅니다.
- 요소를 삭제할 때 즉시 메모리에서 해제됩니다.
- 임의 접근이 불가능합니다. 탐색의 경우, 최악의 시간 복잡도가 O(n)이 될 수 있습니다.
vector vs deque
- 덱은 벡터의 메모리 할당 단점을 보완한 컨테이너입니다. 메모리가 부족하면 벡터처럼 메모리를 재할당하고 삭제하는 과정없이 새로운 단위의 메모리 블록을 할당하고 원소를 삽입합니다.
- 새 원소를 중간에 삽입/삭제하면 원소 수가 작은 메모리 영역으로 밀어내거나 당깁니다.
레퍼런스
[STL]vector 벡터 정리 및 예제
cppreference.com - std::vector
cppreference.com - std::vector<T, Allocator>::vector
GeeksforGeeks
C++STL std::vector - emplace_back
push_back vs emplace_back
'개발 > Algorithm' 카테고리의 다른 글
| 행렬 곱셈 연산 최적화 (0) | 2019.10.22 |
|---|---|
| 소수 생성 알고리즘(Prime-generating Algorithm) (1) | 2019.09.14 |
| 순열 알고리즘 (Permutation Algorithm) (3) | 2019.09.06 |
- Total
- Today
- Yesterday
- P4 Stream
- C# lambda expression
- visual studio 핫 리로드
- c++ 핫 리로드
- UE4
- c++ hot reload
- Perforce Streams
- 구글테스트
- 언리얼 엔진
- C# 익명함수
- GoogleTest
- Perforce Stream
- 코드 저작권
- Visual Studio C1083
- C# 람다식
- 행렬
- 퍼포스 스트림
- C++
- Auto
- DXGI
- C7568
- 구간합
- code copyright
- MSVC C1083
- C++ Compile error
- P4 Streams
- 퍼포스 개요
- visual studio hot reload
- game hot reload
- 알고리즘
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 15 | 16 | 17 | 18 | 19 | 20 | 21 |
| 22 | 23 | 24 | 25 | 26 | 27 | 28 |
| 29 | 30 | 31 |