2.1.1.1절. 특징

vector 은 map 과 함께 가장 자주 사용되는 컨테이너이다. 단순히 배열을 모든 자료형을 원소로 가질수 있도록 일반화 시킨것이라고 보면된다. 배열과 같이 첨자연산이 가능하다. 각각의 요소에 랜덤하게 접근이 가능하며, vector 의 마지막 요소를 삭제하는데는 상수시간이 소요된다. 반면 처음과 중간에 있는 요소를 삭제하는데에는 linear time(선형시간) 이 소요된다.

처음과 중간에 있는 요소를 삭제하는데에 linear time 이 걸리는 이유는 배열과 매우 비슷하게 만약 중간에 있는 요소를 삭제 했을경우 그 뒤에 있는 요소들을 모두 한칸씩 앞으로 밀어넣어야 하는 연산을 필요로 하기 때문이다(즉 마지막에 요소를 추가하거나 삭제할때 효율적임).

그러므로 만약 중간에 있는 요소를 자주 삭제하는 연산이 필요할경우에 vector 를 사용하는건 매우 비효율적이 될수 있다. 이럴경우에는 list 같은 다른 컨테이너를 사용해야 할것이다.

STL에서 제공하는 다른 컨테이너들과 마찬가지로 vector 도 자신이 알아서 메모리 관리를 한다.

2.1.1.2절. 선언

vector 컨테이너는 다음과 같이 선언되어 있다.

vector<int> myint;
vector<class myobj> myobj;
vector<vector <myint> > v_myint; 
					

또한 vector 은 최초에 생성될때, 기본적인 크기와 채워질 값을 지정할수 있다.

vector<string> mydata(20, "hello");
					

2.1.1.3절. 자주 사용되는 멤버 함수들

위에서 보면 vector 를 단지 특정 형(type)에 관계없이 멤버 요소를 가질수 있는 배열 정도로만 치부할수도 있을것이다. 그러나 vector 은 클래스 템플릿의 특징을 살려서 매우 다양한 함수들을 제공하며, 우리는 이러한 함수들을 통해서 별도로 코딩할필요 없이 원하는 작업을 할수 있게 된다.

이러한 함수들은 굉장히 많기 때문에 비교적 사용빈도가 높은 것들만을 설명하도록 하겠다.

#include <vector>
#include <string>
 
int main()
{
    vector<string> mydata;
 
    // iterator 을 만든다. 
    // iterator 로 순환(참조)할 컨테이너의 타입에 맞게 만들어준다. 
    vector<string>::iterator mi; 
 
    mydata.push_back("hello");
    mydata.push_back("world");
    mydata.push_back("ok");
 
    mi = mydata.begin();  // mydata  의 첫번째 원소의 위치를 가르킨다. 
    while ( mi != mydata.end())
    {
        cout << *mi <<endl;
        mi++;
    }
    cout << mydata[0] << endl;   // 배열과 같이 첨자로 접근 가능하다. 
}
						

iterator begin();
iterator end();
						

void push_back(const T&);
iterator insert(iterator pos, const T& x);
						

vector<string> mydata;
 
mydata.push_back("hello");
mydata.push_back("world");
mydata.push_back("ok");
 
// hello 다음에 "yundream" 을 삽입한다.
mydata.insert(mydata.begin()+1, "yundream");  
 
// 혹은 iterator 을 선언해서 삽입가능하다.  
vector<string>::iterator mi;
mi = mydata.begin(); 
mydata.insert(mi + 2, "hahaha");
						

void pop_back();
iterator erase(iterator pos);
iterator erase(iterator first, iterator last);
						

void swap(vector&); 
						

vector<string> ok1, ok2;
...
...
ok1.swap(ok2); // ok1 의 내용을 ok2로 덮어쓴다.  
						

size_type size();
bool empty();
						

vecotr<string> mydata;
mydata.push_back("1");
mydata.push_back("2");
mydata.push_back("3");
mydata.push_back("4");
for(int i = 0; i < mydata.size(); i++)
{
    cout << mydata[i] << endl;	
}
						

void reserve(size_type n);
size_type capacity() const;
						

2.1.2.1절. 특징

이름에서도 알수 있겠지만 queue 자료구조를 위해 최적화 되었다. 기본적인 사용방법은 vector 와 매우 같으며, vector 와는 달리 컨테이너의 맨 앞에서 행해지는 삽입/삭제에 대해서 매우 빠른 연산(상수시간)이 가능하다. 보통의 queue 자료구조는 맨앞에 원소의 삽입을 하지 않는게 원칙이지만 deque 는 맨앞에 원소의 삽입도 지원한다.

이는 자료구조의 맨의 요소를 빈번하게 읽고/삭제 해야하는 queue 의 특성을 효율적으로 지원할수 있어야 하기 때문이다.

이외에는 vector 와 완전히 사용방법이 똑같다고 보면 된다. vector 과 마찬가지로 각 요소에 랜덤하게 접근가능하다. vector 로 만들어진 코드를 dequeu 로 변경하고 싶으면 선언에서 vector 만 deque 로 변경시켜 주면 된다.

하지만 중간에 요소를 삽입/삭제하는데에는 vector 와 같이 선형시간이 소비된다. 중간에 요소 삽입 ,삭제 작업이 많이 요구된다면 vector 이나 deque 대신 list 를 쓰는게 더욱 효율적이다. vector 과 마찬가지로 생성되면서 할당기가 만들어져서 자동적으로 메모리를 관리한다.

2.1.2.2절. 선언

vector와 같다.

deque<int> myint;
deque<class myobj> myobj;
deque<vector <myint> > v_myint; 
					

2.1.2.3절. 자주 사용되는 멤버 함수들

모든 사용방법 심지어는 함수 이름들까지도 vector와 똑같다. 위의 vector 를 설명한곳에서 vector 을 deque로만 변경시키면 된다.

vector 에서는 제공되지 않는 함수로 pop_front()와, push_front()가 있다. pop_front()는 맨앞의 원소를 삭제할때, push_front() 는 맨앞에 원소를 삽입할때 사용한다.

void push_front(const T&);
void pop_front();
					

deque<int> myque;
 
myque.push_back(1);
myque.push_back(2);
myque.push_back(3);
myque.push_back(4);
myque.push_back(5);
 
cout << myque.size() << ":" << myque[0] << endl;
myque.push_front(0);
cout << myque.size() << ":" << myque[0] << endl;
 
myque.pop_front();
cout << myque.size() << ":" << myque[0] << endl;
myque.pop_front();
cout << myque.size() << ":" << myque[0] << endl;
 
deque<int>::iterator mi;
mi = myque.begin();
 
while( mi != myque.end())
{
    cout << *mi << endl;
    *mi++;
}
					

2.1.3.1절. 특징

STL 에서 제공하는 list 는 double linked list 를 일반화 시킨 템플릿 버젼이라고 생각하면 된다. double linked list 의 특징을 또한 그대로 가지고 있다. vector 와 deque 는 임의 접근이 가능하다고 했다. 이는 vector, deque 가 배열의 특징을 가지기 때문으로 첨자를 이용한 임의 접근이 가능하다. 그러나 list 는 이러한 임의 접근을 할수가 없다(doublke linked list 도 마찬가지). 대신에 중간에서의 요소 삽입/삭제를 매우 효율적으로 처리할수 있다. vector, deque 와 같은 메모리 연산이 일어나지 않기 때문이다. 단지 다음요소를 가르킬수 있도록 포인터만 재조정해 주면 되기 때문이다.

임의 접근이 안되므로 당연히 첨자를 이용해서는 요소에 접근할수 없다. 단지 이터레이터를 이용해서 접근이 가능하다. double linked list 의 요소에 접근하기 위해서는 포인터를 이용해야 하는것과 마찬가지이다.

임의 접근이 포기되는대신에 linked list 의 특징을 이용할수 있는 다양한 다른 기능들이 함수로 제공되어 진다.

그러나 list 도 단점이 있는데, 특 특정 원소에 접근하기 위해서는 처음부터 원소를 쭉 찾아서 접근해야 한다는 점이다. 임의 접근이 안된다. 그러므로 원소들이 서로 멀리 떨어져 있는 상황에서 연산을 하게 되면 비효율적이 될수가 있다.

2.1.3.2절. 선언

다른 vector 와 deque 와 동일하다.

2.1.3.3절. 자주 사용되는 멤버 함수들

list 의 linked list 로써의 특징때문에 원소의 삽입/삭제에 대해서 가장 폭넓은 지원을 해준다. push_back(), push_pop(), pop_front(), pop_back() 등의 모든 함수들을 지원하며, 중간에 요소를 입력하기 위한 erase(), insert() 도 지원한다. 물론 erase 와 insert 는 vector 과 deque 에서도 지원하지만 효율에서 많은 차이가 난다. list 는 이러한 모든 연산을 상수시간에 끝낼수 있다. 링크만 다시 만들면 되기 때문이다.

이렇게 메모리 재배치를 통하지 않고 링크 재배치만을 통해서 요소의 삽입/삭제가 가능하다는 장점때문에 다른 컨테이너에서는 제공하지 않는 몇가지 특별한 함수들을 제공한다.

void reverse();
void splice(iterator position, list<T, Alloc>& x);
					

#include <list>
 
int main()
{
    list<int> mylist;
    list<int> mylist2;
 
    mylist.push_back(0);
    mylist.push_back(1);
 
    mylist2.push_back(2);
    mylist2.push_back(3);
 
    // mylist 마지막에 mylist2 를 붙인다. 
    mylist.splice(mylist.end(), mylist2);
 
    list<int>::iterator mi;
    mi = mylist.begin();
 
    while( mi != mylist.end())
    {
        cout << *mi << endl;
        *mi++;
    }
 
    // mylist 를 역으로 재배치 한다. 
    mylist.reverse();
    mi = mylist.begin();
 
    while( mi != mylist.end())
    {
        cout << *mi << endl;
        *mi++;
    }
}