[C++] list container 정리 및 사용법

• 안녕하세요, BlockDMask 입니다.

• 오늘은 STL의 sequence container 의 vector, deque, list중 세번째 인 list에 대해서 알아보겠습니다.

• 날이 정말 덥군요. 저는 시원한 카페에 앉아서 포스팅 해보도록하겠습니다. 'ㅁ'

• 저는 자료구조를 C언어로 배웠는데요. 
  C++의 list는 딱 더블 링크드리스트(doubly linked list)와 구조가 같습니다.
  다만 C++에서는... 미리 구현되어있다는 점이 다릅니다.

• C에서는 자료구조를 사용하려면 처음부터 만들어서 사용했었었는데, 너무 편하고 좋네요.

• 이렇게 도구가 많아도 제대로 사용할 줄 알아야 자신의 도구가 되겠죠?

• 그럼 정리내용을 보러 가겠습니다.

1) list container 

• 시퀀스 컨테이너 (sequence container)의 일종이므로 순서를 유지하는 구조입니다.
  
  
• 노드 기반 컨테이너 입니다.
  
  
• 이중 연결 리스트(doubly linked list)라고 생각하면 됩니다.
  
  
• 앞에 vector, deque과는 다르게 멤버 함수 에서 정렬(sort, merge), 이어붙이기(splice) 가 있습니다.
  
  
• 원소를 탐색할때, 임의접근 반복자(at(), []) 는 불가능하고, 양방향 반복자 (++, --) 를 이용해서 탐색을 합니다.
  
  
• push_front(), push_back(), pop_front(), pop_back() 멤버 함수를 이용해서 list 양 끝에서 삽입, 삭제가 가능합니다.
  
  
• insert(), erase() 멤버 함수를 통해서 노드 중간에서도 삽입, 삭제가 가능합니다.
  
  
• 그림으로 보겠습니다.
  

2) list의 사용

• <list> 헤더파일을 사용합니다.
• using namespace std; 를 선언해주면 편리합니다.
• 선언의 기본은 : list< [Data Type] > [변수 이름];
  ex1) list<int> lt1;
  ex2) list<string> lt2;

3) list의 생성자와 연산자

• list lt;
  비어있는 list 컨테이너 lt 를 생성합니다.
  
  
• list lt(10);
  default(0)값으로 초기화 된 원소 10개를 가진 list를 생성합니다.
  
  
• list lt(3, 2);
  2값으로 초기화 된 원소 3개를 가진 list를 생성합니다.
  
  
• list lt2(lt1);
  list lt1을 lt2로 복사합니다.
  
  
• 연산자("==", "!=", "<", ">", "<=", ">=") 사용 가능합니다.

4) list의 멤버 함수

-> list 컨테이너에는 at, [] 가 없습니다. (반복자가 ++, -- 하는 방식으로만 원소 접근가능)
-> list<int> lt; 로 선언했다고 가정하고 작성하겠습니다.

• lt.assign(3, 4);
  - 4로 초기화된 3개의 원소를 할당한다.
  
  
• lt.front()
  - 맨 앞의 원소를 반환(return), 참조 합니다.
  
  
• lt.back()
  - 맨 뒤의 원소를 반환(return), 참조 합니다.
  
  
• lt.begin()
  - 맨 앞의 원소를 가리키는 iterator를 반환합니다.
  - ex) list<int>::iterator iter;
  - iter = lt.begin();
  
  

• lt.end()
  - 맨 마지막의 다음 원소를 가리키는? (맨마지막 을 알 수 있는) iterator를 반환합니다.
  - ex) list<int>::iterator iter;
  - iter = lt.end();
  

• lt.rbegin()
  - 뒤에서부터 원소를 순차적으로 접근할때 편리하게 쓰입니다.
  - begin()과 동일하게 사용하면 됩니다.
  
  
• lt.rend()
  - 뒤에서부터 원소를 순차적으로 접근할때 편리하게 쓰입니다.
  - end()와 동일하게 사용하면 됩니다.
  
  
• lt.push_back(k)
  - 뒤쪽으로 원소 k 를 삽입합니다.
  
  
• lt.push_front(k)
  - 앞쪽으로 원소 k 를 삽입합니다.
  
  
• lt.pop_back()
  - 맨 마지막 원소를 제거합니다.
  
  
• lt.pop_front()
  - 맨 첫번째 원소를 제거합니다.
  
  
• lt.insert(iter, k)
  - iter가 가리키는 위치에 원소 k를 삽입합니다.
  - 삽입한 원소를 가리키는 iterator를 반환합니다.
  
  
• lt.erase(iter)
  - iterator가 가리키는 원소를 삭제합니다.
  - 반환값은 삭제한 원소의 다음 원소를 가리키는 iterator를 반환합니다.

• lt.size()
  - 원소의 개수를 반환합니다.
  
  
• lt.remove(k)
  - k 와 같은 원소를 모두 제거합니다 (편리..)
  
  

• lt.remove_if(Predicate)
  - 단항 조건자 predicate에 해당하는 원소를 모두 제거합니다 (더! 편리..)
  
  

• lt.reverse()
  - 원소들의 순차열을 뒤집습니다.
  
  
• lt.sort()
  - 모든 원소를 default(오름차순) 으로 정렬합니다.
  - 소트의 파라미터로 이항조건자가 올수 있습니다. 그때는 그 기준으로 정렬합니다.
  
  
• lt2.swap(lt1)
  - lt2와 lt1을 swap(바꿉)니다.
  
  
• lt2.splice(iter2, lt1)
  - lt2에서 iter2이 가리키는 곳에 lt1의 모든 원소를 잘라 붙입니다.
  - lt2.splice(iter2, lt1, iter1) : lt2의 iter2가 가리키는 곳에 lt1의 iter1이 가리키는 원소를 잘라 붙입니다.
  - lt2.splice(iter2, lt1, iter1_1, iter1_2) : lt2의 iter2가 가리키는 곳에 lt1의 [iter1_1 , iter1_2) 까지의 원소를 잘라 붙입니다.
  **[ start, end ) 까지는 start보다는 크거나같고, end보다는 작은 원소를 뜻합니다.
  
  
• lt.unique()
  - 인접한(양옆의) 원소가 같으면 유일하게 만듭니다.(하나만빼고 삭제)
  
  

• lt2.merge(lt1)
  - lt1을 lt2내부로 합병 정렬합니다. 기준은 default 오름차순 입니다.
  - 두번째 파라미터로 이항 조건자가 올 수 있습니다. 그때는 그 기준으로 정렬합니다.
  

5) 이상하고 다양한 예제

• 오늘 예제는 기본이 되는 삽입 삭제 등을 제외하고, list에만 존재하는 remove, remove_if, sort, splice, unique, merge 예시로 준비해봤습니다.

test1,2) remove_if 와 remove입니다. 

• remove_if(predicate)를 통해서 원소의 값이 100~200 사이인 원소들를 제거했고,
  remove(10)을 통해서 원소의 값이 10인 원소들을 제거했습니다.
  

#include<iostream>
#include<list>
 
using namespace std;
 
//100과 200사이이면 true 
bool predicate(int num){
    return num>=100 && num<=200;
}
int main(void){
    list<int> lt;
    
    lt.push_back(10);
    lt.push_back(20);
    lt.push_back(108);
    lt.push_back(60);
    lt.push_back(10);
    lt.push_back(100);
    lt.push_back(40);    
    lt.push_back(50);
    lt.push_back(10);
    lt.push_back(109);
    lt.push_back(30);    
    lt.push_back(220);
    lt.push_back(10);
        
 
    list<int>::iterator iter;
    
    cout << "orign) ";
    for(iter = lt.begin(); iter!= lt.end(); iter++){
        cout <<*iter << " ";
    }    
    cout << endl << endl;
    
    //predicate 함수가 참이면 remove 한다. 
    //100~200 사이 원소 제거 
    lt.remove_if(predicate);
    
    cout << "test1) " ; 
    for(iter = lt.begin(); iter!= lt.end(); iter++){
        cout << *iter << " ";
    }    
    cout << endl << endl;
 
 
    //원소가 10 인 원소 제거 
    lt.remove(10);
    
    cout << "test2) ";
    for(iter = lt.begin(); iter!= lt.end(); iter++){
        cout << *iter << " ";
    }    
    cout << endl << endl;
    return 0;    
}

• test1,2 결과입니다

test3,4) unique와 sort입니다.

• unique를 통해서 자기 자신과 자신의 다음 노드가 동일한 인자이면 1개만 남기고 제거 함을 볼 수 있고
• sort1 은 오름차순, sort 2는 내림차순으로 정렬 됨음 볼 수 있습니다.
• ( list container 객체의 타입을 string으로 선언했기 때문에 사전순, 역 사전순으로 정렬됩니다.)

#include<iostream>
#include<list>
#include<functional>
 
using namespace std;
 
int main(void){
    list<string> lt;
    
    lt.push_back("b");
    lt.push_back("c");
    lt.push_back("a");
    lt.push_back("q");
    lt.push_back("a");
    lt.push_back("a");
    lt.push_back("a");
    lt.push_back("k");
    lt.push_back("j");
    lt.push_back("p");
    lt.push_back("q");
    lt.push_back("o");
    lt.push_back("e");
    lt.push_back("a");
    lt.push_back("a");
 
 
    list<string>::iterator iter;
    
    cout << "orign) ";
    for(iter = lt.begin(); iter!= lt.end(); iter++){
        cout <<*iter << " ";
    }    
    cout << endl << endl;
 
 
    //unique멤버 함수를 통해서 붙어있는 인자 삭제. 
    cout << "unique) ";
    lt.unique();
    for(iter = lt.begin(); iter!= lt.end(); iter++){
        cout <<*iter << " ";
    }    
    cout << endl << endl;
 
    //sort 기본값인 오름차순 을 통해서 
    //string은 사전순으로 정렬. 
    cout << "sort 1) ";
    lt.sort();
    for(iter = lt.begin(); iter!= lt.end(); iter++){
        cout <<*iter << " ";
    }    
    cout << endl << endl;
 
    //sort 내림차순. 
    cout << "sort 2) ";
    lt.sort(greater<string>());
    for(iter = lt.begin(); iter!= lt.end(); iter++){
        cout <<*iter << " ";
    }    
    cout << endl << endl;
 
    return 0;    
}

• test3,4 결과입니다
  a가 총 a / a a a / a a 가 존재하는데 unique 함수 이후로 a / a / a로 바뀜을 확인 할 수 있습니다.

test 5) splice 입니다.

    #include<iostream>
    #include<list>
    #include<functional>
    
    using namespace std;
    
    int main(void){
        list<string> lt1;
        
        lt1.push_back("a");
        lt1.push_back("b");
        lt1.push_back("c");
        lt1.push_back("d");
        lt1.push_back("e");
    
        list<string> lt2;
        lt2.push_back("X");
        lt2.push_back("Y");
        lt2.push_back("Z");
    
        list<string>::iterator iter;
        
        cout << "[lt1] orign) ";
        for(iter = lt1.begin(); iter!= lt1.end(); iter++){
            cout <<*iter << " ";
        }    
        cout << endl ;
 
        cout << "[lt2] orign) ";
        for(iter = lt2.begin(); iter!= lt2.end(); iter++){
            cout <<*iter << " ";
        }    
        cout << endl << endl << endl;
 
    /////////////////////////////////////////////////////
        iter = lt2.begin();
        iter++;
        
        //lt2의 iter부분 부터 lt1을 잘라서 붙입니다. 
        lt2.splice(iter, lt1);
        cout << "[lt1] splice) ";
        for(iter = lt1.begin(); iter!= lt1.end(); iter++){
            cout <<*iter << " ";
        }    
        cout << endl <<endl;
        
        cout << "lt1.size() : "<<lt1.size() << endl; 
        cout << endl <<endl;        
        
        
        cout << "[lt2] splice) ";
        for(iter = lt2.begin(); iter!= lt2.end(); iter++){
            cout <<*iter << " ";
        }    
        cout << endl <<endl;
        
        
        cout << "lt2.size() : "<<lt2.size() << endl; 
    
        return 0;    
    }

• test 5 결과입니다.
  lt2인 X Y Z 사이에 lt1인 a b c d e가 잘려 들어갔음을 볼 수 있습니다.
  또한 lt1이 비어있음을 알 수 있습니다. size가 0 입니다.

test 6) merge 입니다.

• merge함수가 제대로 동작하기 위해서는 합칠 두 list인 lt1, lt2가 이미 정렬이 되어있어야 합니다.
  

#include<iostream>
#include<list>
#include<functional>
 
using namespace std;
 
int main(void){
    list<int> lt1;
 
    lt1.push_back(100);
    lt1.push_back(200);
    lt1.push_back(300);
    lt1.push_back(400);
    lt1.push_back(500);
 
    list<int> lt2;
    
    lt2.push_back(111);
    lt2.push_back(444);
    lt2.push_back(555);
 
    
    list<int>::iterator iter;
    
    cout << "[lt1] orign) ";
    for(iter = lt1.begin(); iter!= lt1.end(); iter++){
        cout <<*iter << " ";
    }    
    cout << endl ;
 
    cout << "[lt2] orign) ";
    for(iter = lt2.begin(); iter!= lt2.end(); iter++){
        cout <<*iter << " ";
    }    
    
    
    cout << endl << endl << "test 6) lt2.merge(lt1);"<< endl << endl;
    lt2.merge(lt1);
    
    
    cout << "[lt1] merge) ";
    for(iter = lt1.begin(); iter!= lt1.end(); iter++){
        cout <<*iter << " ";
    }    
    cout << endl ;
 
    cout << "[lt2] merge) ";
    for(iter = lt2.begin(); iter!= lt2.end(); iter++){
        cout <<*iter << " ";
    }    
    cout << endl << endl << endl;
        
 
    return 0;    
}

• test 6 결과입니다.
  잘 섞여서 들어가는 것을 확인 할 수있습니다.