STL Container - Sequence Container

STL Container는 같은 타입의 여러 객체를 저장하는 일종의 집합이라 할 수 있다. 컨테이너는 class template으로, 컨테이너 변수를 선언할 때 컨테이너에 포함할 요소의 타입을 명시할 수 있다. 컨테이너에는 복사 생성과 대입을 할 수 있는 타입의 객체만을 저장할 수 있으며, 요소의 추가 및 제거를 포함한 다양한 작업을 도와주는 여러 멤버 함수를 포함하고 있다.

STL Sequence Container

데이터를 선형으로 저장하며, 특별한 제약이나 규칙이 없는 가장 일반적인 컨테이너이다. 시퀀스 컨테이너에서는 삽입된 요소의 순서가 그대로 유지된다.

모든 요소가 직선 순서대로 배치되어 있어야한다.
반복자가 최소한 순방향 반복자(forward iterator) 이상이어야한다.
시퀀스 컨테이너의 요소들은 명확한 순서를 가지므로, 특정 위치를 참조하는 연산이 가능해야한다.

vector

vector 컨테이너는 대표적인 시퀀스 컨테이너로 배열과 비슷하여 사용이 쉬우며 자주 사용된다. vector는 임의 접근 반복자(Random Access Iterator)를 지원하는 배열 기반 컨테이너이다. vector의 가장 큰 특징 중 하나는 원소가 하나의 메모리 블록에 연속하게 저장된다는 것이다. vector는 요소가 추가되거나 삭제될 때마다 자동으로 메모리를 재할당하여 크기를 재할당하여 크기를 동적으로 변경한다. 메모리 할당 크기를 알 수 있게 capacity() 함수를 제공하며 한번에 메모리를 할당할 수 있는 reserve() 함수도 제공된다. 원소가 연속하게 저장되므로 [] 연산자 또는 at 으로 읽기에는 빠르지만 insert(), erase(), push_back() 등은 비효율적으로 동작한다.

#include <vector>

vector<T> 객체명(생성자 인수);

생성자 인수로는 벡터 컨테이너의 초기 크기를 전달하며, 생략하면 요소를 가지지 않는 빈 벡터를 생성한다.

생성자

설명

멤버함수

예제

#include <iostream>
#include <vector>
using namespace std;

int main(){

    vector<int> v;
    vector<int> v2(5);    // 0으로 초기화된 5개의 원소
    // 메모리크기 8만큼 할당
    v.reserve(8);

    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);

    for (vector<int>::size_type i = 0; i < v.size(); ++i)
        cout << v[i] << endl;
    cout << endl;

    // 벡터의 원소 갯수를 10개로 확장, 추가된 공간은 디폴트 0으로 채워진다.
    v.resize(10);                
}

여기서 v.size()만큼 for문을 실행하려면 v.size()의 타입과 i 가 같아야 한다.

vector<int>::size_type : 벡터의 size 의 반환 타입을 가져온다 (unsigned int)

deque

depue는 double-ended queue를 의미하며, 양방향 큐이다. 컨테이너의 양 끝에서 빠르게 요소를 삽입하거나 삭제할 수 있다.

구조

deque<T> 변수명;

생성자

Member Function

예제

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

int main(){
    // deque 선언 및 초기화
    deque<int> dq;
    dq.push_back(20);
    dq.push_back(30);
    dq.push_front(10);

    cout << "deque : ";
    copy(dq.begin(), dq.end(), ostream_iterator<int>(cout," "));

    dq.pop_front();
    cout << "deque : ";
    deque<int>::iterator iter;
    for(iter=dq.begin();iter!=dq.end();++iter){
        cout << * iter << ' ';
    }
    cout << endl;
}

list

STL List는 double linked list, forward_list는 single linked list와 같다.

list는 노드 기반 컨테이너로 at()과 [] 연산자가 없으며 임의 접근 반복자가 아닌 양방향 반복자(++, --)를 제공
중간에 원소를 삽입(insert), 제거(erase) 하더라도 상수 시간 복잡도(O(n))의 수행 성능

구조

template < class T, class Allocator = allocator<T> > class list;

list<int> intList;
list<string> stringList;

생성자

Member Function

예제

#include <iostream>
#include <list>
using namespace std;

int main(){

    list<int> list1;

    list1.push_back(10);
    list1.push_back(20);
    list1.push_back(30);
    list1.push_back(40);
    list1.push_back(50);

    list<int>::iterator iter;
    for (iter = list1.begin(); iter != list1.end(); ++iter){
        cout << *iter << ' ';
    }
    cout << endl;
  // 10 20 30 40 50

    // erase 삭제
  	iter = list1.begin();
    iter++;
    iter++;

    list<int>::iterator iter2 = list1.erase(iter);
    for (iter = list1.begin(); iter != list1.end(); ++iter){
        cout << *iter << ' ';
    }
    cout << endl;
  	// 10 20 40 50
  
  
    cout << "iter2 : " << *iter2 << endl;
  	// iter2 : 40

    list1.push_back(10);
    list1.push_back(10);

    for (iter = list1.begin(); iter != list1.end(); ++iter){
        cout << *iter << ' ';
    }
    cout << endl;
   	// 10 20 40 50 10 10

    // 리스트에서 원소 10 제거
    list1.remove(10);

    for (iter = list1.begin(); iter != list1.end(); ++iter){
        cout << *iter << ' ';
    }
    cout << endl;
  	// 20 40 50
  
    return 0;
}

forward_list

<forward_list> 헤더에 존재한다.
단순연결리스트 자료구조를 이용하여 만든 sequence container
단방향리스트로만 충분한 경우에 사용(한 방향으로만 이동 가능하다.)
std::list 보다 삽입/삭제 속도가 더 빠르며, 메모리를 더 적게 사용한다.(차이는 크지 않다.)

구조

template< class T, class Allocator = std::allocator<T> > class forward_list;

forward_list<int> singleList;

특징

특별한 이유가 없다면 forward_list는 기존의 list의 설계에 맞춘다.
std::list의 insert와 erase를 forward_list에서 구현이 복잡해지고 성능 측면에서 좋지 않아 제공하지 않는다.
다른 STL의 container에 있는 size 함수를 제공하지 않는다. 이유는 요소 수를 보존하는 멤버를가지고 있으면 C언어에서 구현한 것과 비교해서 불필요한 메모리를 사용한다. 만약 이런 멤버를 가지고 있지 않으면서 size 함수를 지원하면 호출할 때마다 모든 요소를 세어야 하므로 계산량이 O(N)이 된다.

멤버 변수

Member types

Member Function

예시

#include <iostream>
#include <forward_list>

using namespace std;

int main(){
  // forward_list 객체의 선언 및 초기화
	forward_list<int> singleList = {10, 20, 400, 30}; 
	forward_list<int> singleList2 = {40, 50};
	forward_list<int>::iterator itr;
	// 값이 400인 모든 요소를 삭제함.
	singleList.remove(400);              

  // singleList 첫 번째 요소를 가리키도록 반복자를 초기화
	itr = singleList.begin();            

  //singleList2 모든 요소를 singleList 첫 번째 요소 다음에 삽입
	singleList.splice_after(itr, singleList2); 

}

참조페이지

PreviousSTL Container - Associate Container NextSTL Container - Container Adapter

Last updated 2 years ago