[Algorithm] STL vector

STL vector

 

-정의: vector 자료구조는 배열과 거의 동일한 기능을 수행하는 자료구조로, 배열과 마찬가지로 원소가 메모리에 연속하게 저장되어 있기 때문에 배열과 마찬가지로 인덱스로 원소에 O(1)에 접근할 수 있음

 

-특징: 원소가 연속하게 저장되므로 [] 연산자 또는 at 으로 읽기에는 빠르지만  insert(), erase(), push_back() 등은 비효율적으로 동작한다.

 

-함수: http://www.cplusplus.com/reference/vector/vector/

 

-주의할 점

 

   (1) size()의 반환 값은 unsigned int

 

vector<int> v1 = {1,2,3};
for(int i=0; i<= v1.size() -1; i++)
	cout << v1[i] << ' ';

    -> 위 코드의 문제점

   

    이 코드가 v1이 비어있을 때 문제. unsigned int 0에서 int 1을 빼면 unsigned int 2^{32}-1232−1이 되기 때문. 그래서 i가 0부터 2^{32}-1232−1까지 돌게 됨. 이를 막기 위해 int로 강제 형변환을 시켜주거나 그냥 v1.size에서 무언가를 빼지 않아야 함.

 

 

    (2) insert, erase가 중간에 있는 원소에 대해 사용했을 경우에는 배열과 마찬가지로 O(N)의 시간을 필요로 한다는 점 또한 주의해야함.

 

 

 

 

 

참고

https://blog.encrypted.gg/725?category=773649