C++ STL - Sequence Container; vector, deque, list, forward_list

시퀀스 컨테이너(sequence container)

시퀀스 컨테이너 컨테이너의 종류 중 하나로 원소를 선형으로 저장한다는 특징이 있다.

수정하지 않는 한 원소들의 순서는 삽인된대로 유지된다.

 

다음과 같은 종류가 있다.

• 벡터(vector)
• 덱(deque)
• 리스트(list)
• 순방향 리스트(forward_list)

 

---

벡터(vector)

벡터는 동적배열로 구현된 클래스 템플릿이다.

원소들을 연속적인 메모리 공간에 저장하기 때문에 반복자 뿐만아니라 배열처럼 임의접근이 가능하다. (vec[i])

 

코드

#include <iostream>
#include <vector>

int main(){
    std::vector<int> vec = {1, 2, 3};	// 선언과 동시에 초기화
    std::vector<int>::iterator it;
    
    vec.push_back(4);	// 뒤에 원소 4 삽입 -> {1, 2, 3, 4}

    it = vec.begin() + 2;
    vec.insert(2, 9);	// 위치 2에 원소 9 삽입 -> {1, 2, 9, 3, 4}

    it = vec.begin() + 1;
    vec.erase(1);	// 위치 1의 원소 삭제 -> {1, 9, 3, 4}

    return 0;
}

 

 

덱(deque)

덱은 벡터와 마찬가지로 동적배열로 구현된 클래스 템플릿이다.

벡터와 다른 점은 앞과 뒤에서만 삽입(push)과 삭제(pop)가 가능하는 것이며, 동적 배열으로 구현되었지만 확장시 연속된 메모리 공간을 사용하지 않고 필요한 만큼의 Chunk를 할당받아 사용한다.

 

코드

#include <iostream>
#include <deque>

int main(){
    std::deque<int> deq = {1, 2, 3};	// 선언과 동시에 초기화
	
    deq.pop_front();	// 맨 앞 원소 삭제 -> {2, 3}	
    
    deq.pop_back();	// 맨 뒤 원소 삭제 -> {2}
    
    deq.push_front(4);	// 앞에 원소 4 삽입 -> {4, 2}
    
    deq.push_back(6);	// 뒤에 원소 6 삽입 -> {4, 2, 6}
   
    return 0;
}

 

 

리스트(list)

리스트는 이중 연결 리스트(doubly linked list)로 구현된 클래스 템플릿이다.

원소들을 연속적인 메모리 공간에 저장하지 않기 때문에 배열처럼 임의 접근이 불가능하다.

포인터로 연결되기 때문에 순서 중간의 원소 삽입 삭제 속도가 빠르다.

 

코드

#include <iostream>
#include <list>

int main(){
    std::list<int> ls = {1, 2, 3};	// 선언과 동시에 초기화
    std::list<int>::iterator it;
    
    it = ls.begin();	// -> {>1<, 2, 3}
    
    ls.push_front(4);	// 앞에 원소 4 삽입 -> {4, >1<, 2, 3}
    
    ls.push_back(6);	// 뒤에 원소 6 삽입 -> {4, >1<, 2, 3, 6}
    
    it++;	// -> {4, 1, >2<, 3, 6}
    
    ls.insert(it, 9);	// 위치 it:2에 원소 9 삽입 -> {4, 1, 9, >2<, 3, 6}

    it++;	// -> {4, 1, 9, 2, >3<, 6}
    
    ls.erase(it);	// 위치 it:3의 원소 삭제 -> {4, 1, 9, 2, 6}

    return 0;
}

 

 

순방향 리스트(forward_list) : C++11에서 추가

순방향 리스트는 단일 연결 리스트(singly linked list)로 구현된 클래스 템플릿이다.

리스트와 차이점은 순방향 검색만 가능하며 역방향으로는 접근할 수 없다.

순방향으로만 포인터를 사용하므로 메모리가 적게든다.

 

코드

#include <iostream>
#include <forward_list>

int main(){
    std::forward_list<int> fls = {1, 2, 3};	// 선언과 동시에 초기화
    std::forward_list<int>::iterator it;
    
    it = fls.begin();	// -> {>1<, 2, 3}
    
    fls.push_front(4);	// 앞에 원소 4 삽입 -> {4, >1<, 2, 3}
     
    fls.insert_after(it, 6);	// 위치 it:2의 뒤에 원소 6 삽입 -> {4, 1, >6<, 2, 3}

    it++;	// -> {4, 1, 6, >2<, 3}
    
    ls.erase(1);	// 위치 it:3의 뒤의 원소 삭제 -> {4, 1, 6, 3}

    return 0;
}

 

 

---

비교