[std] Vector

 

 

STL (Standard Template Libaray) 가장 기본적인 data structure

[정의]

길이(크기)가 가변적인 array list

♣ Vector의 Capacity (할당된 메모리 공간의 크기)를 넘어서는 시점에서 자동으로 메모리 재할당 및 기존 원소값들의 복사가 발생하는 원리로 크기의 가변성을 보장한다.

 

 

---

[Time Complexity Analysis]

• 임의의 위치 접근 (index 사용) : O(1)
• 맨 뒤 원소 삽입/삭제 : amortized O(1)
• 임의의 위치 원소 삽입/삭제: O( N + M ) // N: 삽입될 원소 갯수, M: 해당 원소 인덱스 뒤의 원소 갯수 (한칸 씩 뒤로 밀어줘야 함) 

분류	임의의 위치 접근	맨 뒤 원소 삽입/삭제	임의의 위치 원소 삽입/삭제
Function name	at, []	push_back / pop_back	insert / erase
Time Complexity	O(1)	amortized O(1)	O(N + M)  N: 삽입, 삭제할 원소 갯수 M: 원소의 이동 갯수 (해당 원소 이전 or 이후 원소 갯수)

 

※ amortized O(1) : vector의 capacity가 16이라고 했을 때 16개를 넘어가는 즉 , vector[16]에 원소를 삽입할 때는

기존에 할당된 배열이 아니라 추가로 배열을 할당한다. (기존 배열의 주소는 해제되고  모든 배열이 복사된다, 

따라서 Vector가 가지고있던 원소 갯수만큼 복사가 일어나므로 O(N)이된다.)

 

※ M: 배열에서의 삽입/삭제는 원소를 한칸씩 당겨오는 작업 or 밀어내는 작업 이 필요하게된다.

이 그림 하나로 배열에서의 임의 위치 삽입/삭제가 O(N)을 갖는다는 것을 알 수 있다.

 

 

---

[용도]

임의의 위치에 접근(참조) + 순차적인 삽입/삭제(특히 맨 끝자리)가 이루어질 때 배열 대신 사용하기 편하다. 
∵ 길이를 알아서 가변적으로 할당해주기 때문이다.

Ω 임의 위치 삽입/삭제가 빈번하게 일어나거나, 원소 갯수가 아주 자주 바뀌는 경우 시간 복잡도가 O(N)이기 때문에 효율적이지 못하다.

 

[예제]

#include <iostream>
#include <vector>
#include <algorithm>
int main(void) {
    std::vector<int> vec;
    std::vector<int>::iterator itr;
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(40);
    vec.push_back(30);
    vec.push_back(5);
    sort(vec.begin(), vec.end());
    for(itr = vec.begin(); itr != vec.end(); ++itr) {
        std::cout << *itr << " ";
    }
    std::cout << '\n';
//    size explain the number of elements this vector has
    std::cout << "this vector size : " << (int) vec.size() << std::endl;
//    capacity explain how much memory space this vector is allocated 
    std::cout << "this vector capacity: " << (int) vec.capacity() << std::endl;
    return 0;
}

[Reference]

http://www.cplusplus.com/reference/vector/vector/insert/