STL :: 컨테이너(list)

STL :: 컨테이너(list)

출처 : http://blog.daum.net/coolprogramming/77

list는 '시퀀스 컨테이너'이며 '노드 기반 컨테이너'입니다. 그래서 데이터의 삽입, 삭제가 시퀀스 중간에 자주 발생할 때 사용하면 좋은 컨테이너입니다.

 

list의 주요 개념을 그림으로 표현하면

 

 

1, list의 반복자

위 그림처럼 list는 앞쪽과 뒤쪽 모두에 데이터를 추가(push_front(), push_back())할 수 있는 함수들을 제공합니다. 또 list는 이중 연결 리스트로 구현되어 있어 앞뒤로 이동 가능한 '양방향 반복자'를 제공합니다. 연결 리스트의 특징인 중간에 삽입, 삭제가 빈번하게 발생할 때 효율적인 컨테이너입니다.

 

list 간단한 예제(데이터 앞쪽, 뒤쪽 추가)

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

voidmain( )
{
    list<int> lt;


    lt.push_back(10); // 리스트 뒤쪽에 추가
     lt.push_back(20);
    lt.push_back(30);
    lt.push_back(40);
    lt.push_back(50);

    list<int>::iterator iter;
    for( iter = lt.begin() ; iter != lt.end() ; iter++)
        cout << *iter << ' ';
    cout << endl;

    lt.push_front(60); // 리스트 앞쪽에 추가
     lt.push_front(70);
    lt.push_front(80);
    for( iter = lt.begin() ; iter != lt.end() ; iter++)
        cout << *iter << ' ';
    cout << endl;

}

1. 10 20 30 40 50
   80 70 60 10 20 30 40 50

 list는 데이터를 앞뒤에 추가할 수 있는 '시퀀스 컨테이너'로 push_front()와 push_back()함수를 제공합니다.(push_front()를 제공하는 컨테이너는 list와 deque뿐입니다.)

10~50까지 리스트 뒤쪽에 추가되며 60, 70, 80은 계속 앞쪽에 추가됩니다.

 

 

 

  list는 '연속 메모리 기반 컨테이너'가 아니므로 operator[]연산자는 가지고 있지 않고 반복자를 통해서만 컨테이너의 요소들에 접근할 수 있습니다. list는 양방향 반복자를 제공합니다. 그래서 반복자에 산술 연산은 불가능하다.(산술 연산이 가능한 반복자는 '임의 접근 반복자'뿐입니다. '연속 메모리 기반 컨테이너'가 임의 접근 반복자를 제공합니다.) 8개의 STL 컨테이너 모두 양방향 반복자 이상을 제공하며 이 중 '연속 메모리 기반 컨테이너'인 string, vector, deque는 산술 연산이 가능한 임의 접근 연산자를 제공합니다.

 

다음은 양방향 반복자를 사용하는 예제입니다.

#include<iostream>
#include<list>
using namespace std;
voidmain()
{
    list<int> lt;


    lt.push_back(10);

    lt.push_back(20);
    lt.push_back(30);
    lt.push_back(40);
    lt.push_back(50);

    list<int>::iterator iter;
    for( iter = lt.begin() ; iter != lt.end(); iter++)
        cout << *iter << ' ';
    cout << endl;

    iter--;


// iter += 2; 산술 연산은 불가능

    cout << *iter << endl;
    cout << *--iter << endl;
    cout << *--iter << endl;
    cout << *--iter << endl;
    cout << *--iter << endl;

}


1. 10 20 30 40 50
   50
   40
   30
   20
   10

 양방향 반복자로 반복자에 ++, -- 연산자 모두 가능하며 산술연산은 불가능합니다.

 

 

  모든 STL 컨테이너는 시작과 끝을 가리키는 반복자 쌍을 반환하는 begin()과 end()를 가진다고 했습니다. 또 모든 컨테이너는 이와 반대인 rbegin(), rend() 함수로 끝과 시작을 가리키는 반복자 쌍을 제공합니다.

 

rbegin()과 rend()함수의 사용

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

voidmain()
{
    list<int> lt;

    lt.push_back(10);

    lt.push_back(20);
    lt.push_back(30);
    lt.push_back(40);
    lt.push_back(50);

    list<int>::iterator iter;
    for( iter = lt.begin() ; iter != lt.end(); iter++)
        cout << *iter << ' ';
    cout << endl;

    list<int>::reverse_iterator riter;
    for( riter = lt.rbegin() ; riter != lt.rend(); riter++)
        cout << *riter <<' ';
    cout << endl;
}


1. 10 20 30 40 50
   50 40 30 20 10

 list의 뒤에서 앞쪽으로 이동하도록 reverse_iterator를 제공합니다. 이 시작과 끝을 가리키는 반복자 쌍을 반환하는 함수가 rbegin()과 rend()입니다. 반복자의 자세한 내용은 뒤쪽에서 다시 공부합니다.

 

 

2, list의 주요 특징과 함수

  list의 장점 중 하나가 데이터 요소의 삽입, 삭제시에 다른 '시퀀스 컨테이너'보다 '효율적이다'는 것입니다. 이유는 '연속 메모리 기반 컨테이너'처럼 컨테이너 요소들이 밀려나지 않기 때문입니다.

모든 컨테이너는 insert()함수와 erase()함수를 가지고 있어 반복자가 가리키는 위치의 요소를 삽입하거나 삭제할 수 있습니다. 또 STL이 제공하는 여러 삽입, 삭제 알고리즘을 사용할 수 있습니다.

이때 '연속 메모리 기반 컨테이너'는 주의할 점이 있습니다. 연속 메모리 기반 컨테이너는 요소의 삽입과 삭제가 '선형 시간'이라는 것입니다. 또 메모리가 재할당될 수 있고 컨테이너의 모든 다른 요소들이 복사될 수 있다는 것입니다.

 

vector와 list의 삽입 예제

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

voidmain()
{
    vector<int> v;
    list<int> lt;

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


    lt.push_back(10);

    lt.push_back(20);
    lt.push_back(30);
    lt.push_back(40);
    lt.push_back(50);

    vector<int>::iterator viter = v.begin();
    viter++;
    viter = v.insert( viter, 80); // vector의 두 번째 요소로 삽입
     cout << *viter << endl;

    list<int>::iterator liter = lt.begin();
    liter++;

    liter = lt.insert( liter, 80); // list의 두 번째 요소로 삽입
      cout << *liter << endl;

    cout << " vector : ";
    for( viter = v.begin() ; viter != v.end(); viter++)
        cout << *viter << ' ';
    cout << endl;

    cout << " list : ";
    for( liter = lt.begin() ; liter != lt.end(); liter++)
        cout << *liter << ' ';
    cout << endl;
}



1. 80
   80
    vector : 10 80 20 30 40 50
    list : 10 80 20 30 40 50

 결과는 같지만 내부적인 동작은 전혀 다릅니다. vector의 요소는 밀려나며 메모리 재할당 및 복사가 발생할 수 있습니다.

아래는 위 예제의 그림입니다.

와

 

 

아래는 erase()함수 예제입니다.

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

voidmain()
{
    vector<int> v;
    list<int> lt;

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



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

    vector<int>::iterator viter = v.begin();
    viter++;
    viter = v.erase( viter); // vector의 두 번째 요소로 삭제
     cout << *viter << endl;

    list<int>::iterator liter = lt.begin();    liter++;
    liter = lt.erase( liter); // list의 두 번째 요소로 삭제
     cout << *liter << endl;

    cout << " vector : ";
    for( viter = v.begin() ; viter != v.end(); viter++)
        cout << *viter << ' ';
    cout << endl;

    cout << " list : ";
    for( liter = lt.begin() ; liter != lt.end(); liter++)
        cout << *liter << ' ';
    cout << endl;
}


1. 30
   30
    vector : 10 30 40 50
    list : 10 30 40 50

 erase()함수를 사용한 삭제도 '삽입' 동작과 같은 특징을 보입니다.