C++ :: STL list 컨테이너

list 컨테이너는 노드 기반 컨테이너로 원소가 노드 단위로 저장됩니다. 자료구조의 이중 연결리스트로 구현됩니다.

 

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

list는 노드 기반 컨테이너이기 때문에 임의 접근 반복자가 아닌 양방향 반복자를 제공합니다. 따라서 모든 원소를 탐색하기 위해서는 양방향 반복자인 ++와 --를 사용하면 됩니다. 

 

⭐️ list의 push_back, push_front 반복자

#include <iostream>
#include <list>
using namespace std;
 
int main(void){
    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(100);
    lt.push_front(200);
 
    for(iter = lt.begin() ; iter != lt.end() ; ++iter)
        cout << *iter << ' ';
    cout << endl;
 
    return 0;
}

 

⭐️ list의 push_back, push_front 반복자 실행결과

10 20 30 40 50 
200 100 10 20 30 40 50 

 

list의 특징 중 하나는 중간에 원소를 삽입하거나 제거해도 상수 시간 복잡도의 수행 성능을 보인다는 점입니다. 또한 반복자가 가리키는 원소 자체가 제거되지 않으면 반복자가 가리키는 원소는 계속 존재합니다. 

 

⭐️ list의 insert()와 erase()

#include <iostream>
#include <list>
using namespace std;
 
int main(void){
    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 = lt.begin();
    list<int> :: iterator iter2;
    ++iter;
    ++iter;
 
    iter2 = lt.erase(iter);
 
    for(iter = lt.begin() ; iter != lt.end() ; ++iter)
        cout << *iter << ' ';
    cout << endl;
 
    cout << "iter2: " << *iter2 << endl;
 
    iter = iter2;
    iter2 = lt.insert(iter, 300);       // iter2(40)이 가리키는 위치에 300 삽입
    for(iter = lt.begin() ; iter != lt.end() ; ++ iter)
        cout << *iter << ' ';
    cout << endl;
 
    cout << "iter : " << *iter2 <<  endl;
    return 0;
}

 

⭐️ list의 insert()와 erase() 실행결과

10 20 40 50 
iter2: 40
10 20 300 40 50 
iter : 300

 

 

다음은 list의 remove() 멤버 함수 예제입니다.

 

⭐️ list의 remove()

#include <iostream>
#include <list>
using namespace std;
 
int main(void){
    list<int> lt;
 
    lt.push_back(10);
    lt.push_back(20);
    lt.push_back(30);
    lt.push_back(10);
    lt.push_back(40);
    lt.push_back(50);
    lt.push_back(10);
    lt.push_back(10);
 
    list<int> :: iterator iter;
    for(iter = lt.begin() ; iter != lt.end() ; ++iter)
        cout << *iter << ' ';
    cout << endl;
 
    lt.remove(10);
    for(iter = lt.begin() ; iter != lt.end() ; ++ iter)
        cout << *iter << ' ';
    cout << endl;
 
    return 0;
}

 

⭐️ list의 revmoe() 실행결과

10 20 30 10 40 50 10 10 
20 30 40 50

 

remove() 함수는 값을 이용하여 노드를 제거합니다. 위에서 lt.remove(10)은 노드의 값이 10인 노드를 모두 제거하라는 뜻과 같습니다. 조건자를 이용하여 원소를 제거해야 한다면 remove_if() 멤버함수를 이용합니다.

 

⭐️ list의 remove_if()

#include <iostream>
#include <list>
using namespace std;
 
bool Predicate(int n){
    return 10 <= n && n <= 30;
}
 
int main(void){
    list <int> lt;
 
    lt.push_back(10);
    lt.push_back(20);
    lt.push_back(30);
    lt.push_back(40);
    lt.push_back(50);
    lt.push_back(10);
 
    list<int> :: iterator iter;
    for(iter = lt.begin() ; iter != lt.end() ; ++iter)
        cout << *iter << ' ';
    cout << endl;
 
    lt.remove_if(Predicate);
    for(iter = lt.begin() ; iter != lt.end() ; ++iter)
        cout << *iter << ' ';
    cout << endl;
 
    return 0;
}

 

⭐️ list의 remove_if() 실행결과

10 20 30 40 50 10 
40 50 

 

spice는 다른 list 컨테이너의 순차열을 잘라붙일 수 있습니다.

 

⭐️ list의 spice()

#include <iostream>
#include <list>
using namespace std;
 
int main(void){
    list<int> lt1;
    list<int> lt2;
 
    lt1.push_back(10);
    lt1.push_back(20);
    lt1.push_back(30);
    lt1.push_back(40);
    lt1.push_back(50);
 
    lt2.push_back(100);
    lt2.push_back(200);
    lt2.push_back(300);
    lt2.push_back(400);
    lt2.push_back(500);
 
    list<int>::iterator iter;
    cout << "lt1: ";
    for(iter = lt1.begin() ; iter != lt1.end() ; ++iter)
        cout << *iter << ' ';
    cout << endl;
 
    cout << "lt2: ";
    for(iter = lt2.begin() ; iter != lt2.end() ; ++iter)
        cout << *iter << ' ';
    cout << endl << "===============" << endl;
 
    iter = lt1.begin();
    ++iter;
    ++iter;
 
    lt1.splice(iter, lt2);
 
    cout << "lt1: ";
    for(iter = lt1.begin() ; iter != lt1.end() ; ++iter)
        cout << *iter << ' ';
    cout << endl;
 
    cout << "lt2: ";
    for(iter = lt2.begin() ; iter != lt2.end() ; ++iter)
        cout << *iter << ' ';
    cout << endl;
 
    return 0;
}

 

⭐️ list의 spice() 실행결과

lt1: 10 20 30 40 50 
lt2: 100 200 300 400 500 
===============
lt1: 10 20 100 200 300 400 500 30 40 50 
lt2: 

 

reverse()는 이중 연결 리스트의 탐색 경로를 바꿈으로서 순차열을 리버스시킵니다.

 

⭐️ list의 reverse()

#include <iostream>
#include <list>
using namespace std;
 
int main(){
    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.reverse();
    for(iter = lt.begin() ; iter != lt.end() ; ++ iter)
        cout << *iter << ' ';
    cout << endl;
 
    return 0;
}

⭐️ list의 reverse() 실행결과

10 20 30 40 50 
50 40 30 20 10 

 

원소를 중복되지 않게 하나씩 남기고 싶다면 unique() 멤버함수를 사용합니다. 다음 예제는 인접한 원소를 유일하게 만드는 unique() 예제입니다.

 

 ⭐️ list의 unique()

#include <iostream>
#include <list>
 
using namespace std;
 
int main(){
    list<int> lt;
 
    lt.push_back(10);
    lt.push_back(10);
    lt.push_back(20);
    lt.push_back(30);
    lt.push_back(30);
    lt.push_back(30);
    lt.push_back(40);
    lt.push_back(50);
    lt.push_back(10);
 
    list<int> :: iterator iter;
    for(iter = lt.begin() ; iter != lt.end() ; ++iter)
        cout << *iter << ' ';
    cout << endl;
 
    lt.unique();
    for(iter = lt.begin() ; iter != lt.end() ; ++iter)
        cout << *iter << ' ';
    cout << endl;
 
    return 0;
}

 

 ⭐️ list의 unique() 실행결과

10 10 20 30 30 30 40 50 10 
10 20 30 40 50 10 

 

다음은 리스트를 정렬해보도록 하겠습니다. sort() 알고리즘은 임의 접근 반복자를 지원하는 컨테이너만 사용할 수 있습니다. 때문에 list는 자체 정렬 멤버 함수 sort()를 사용합니다.

 

⭐️ list의 sort()

#include <iostream>
#include <list>
using namespace std;
 
int main(void){
    list<int> lt;
    lt.push_back(20);
    lt.push_back(10);
    lt.push_back(50);
    lt.push_back(30);
    lt.push_back(40);
 
    list<int> :: iterator iter;
    for(iter = lt.begin() ; iter != lt.end() ; ++iter)
        cout << *iter << ' ';
    cout << endl;
 
    lt.sort();
    for(iter = lt.begin() ; iter != lt.end() ; ++iter)
        cout << *iter << ' ';
    cout << endl;
    
    return 0;
}

 

⭐️ list의 sort() 실행결과

20 10 50 30 40 
10 20 30 40 50 

 

두 list를 합병해야 하는 경우 merge() 멤버 함수를 사용합니다. 이 때 두 list는 정렬되어 있어야 합니다.

 

⭐️ list의 merge()

#include <iostream>
#include <list>
using namespace std;
 
int main(){
    list<int> lt1;
    list<int> lt2;
 
    lt1.push_back(10);
    lt1.push_back(20);
    lt1.push_back(30);
    lt1.push_back(40);
    lt1.push_back(50);
 
    lt2.push_back(25);
    lt2.push_back(35);
    lt2.push_back(60);
 
    list<int> :: iterator iter;
    cout << "lt1: ";
    for(iter = lt1.begin() ; iter != lt1.end() ; ++iter)
        cout << *iter << ' ';
    cout << endl;
 
    cout << "lt2: ";
    for(iter = lt2.begin() ; iter != lt2.end() ; ++iter)
        cout << *iter << ' ';
    cout << endl << "========================" << endl;
 
    lt1.merge(lt2);
 
    cout << "lt1: ";
    for(iter = lt1.begin() ; iter != lt1.end() ; ++iter)
        cout << *iter << ' ';
    cout << endl;
 
    cout << "lt2: " ;
    for(iter = lt2.begin() ; iter != lt2.end() ; ++iter)
        cout << *iter << ' ';
    cout << endl;
 
    return 0;
}

 

⭐️ list의 merge() 실행결과

lt1: 10 20 30 40 50 
lt2: 25 35 60 
========================
lt1: 10 20 25 30 35 40 50 60 
lt2: 

 

 

📚 출처

공동환(2012), 뇌를 자극하는 C++ STL, 한빛미디어.