포스트

list

C++ STL의 list에 대해서 정리했습니다.

게시 업데이트
Preview Image
By 김종민
14 분읽는 시간
list

list는 시퀀스 컨테이너로 원소들이 순차적으로 컨테이너에 저장된다.
시퀀스 컨테이너 중에서는 유일하게 노드 기반 컨테이너다.

노드 기반 컨테이너기 때문에 양방향 반복자를 제공한다.
list는 내부적으로 양방향 연결 리스트로 구현되어 있다.


인터페이스

list는 시퀀스 컨테이너가 가지고 있는 인터페이스를 모두 가지고 있다.

추가적으로 list의 특성 때문에 별도로 가지고 있는 인터페이스들도 존재한다.


원소의 삽입과 제거

list는 deque과 비슷하게 컨테이너 앞과 뒤의 원소 삽입/제거를 지원한다.

push_back()은 컨테이너 맨 뒤에 원소를 삽입한다.
pop_back()은 컨테이너 맨 뒤의 원소를 삭제한다.

push_front()는 컨테이너 맨 앞에 원소를 삽입한다.
pop_front()는 컨테이너 맨 앞의 원소를 삭제한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#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);

    // 10 20 30이 순차적으로 출력된다.
    for(list<int>::iterator iter = lt.begin(); iter != lt.end(); iter++)
        cout << *iter << ' ';
    cout << endl;

    lt.push_front(40);
    lt.push_front(50);

    // 50 40 10 20 30이 순차적으로 출력된다.
    for(list<int>::iterator iter = lt.begin(); iter != lt.end(); iter++)
        cout << *iter << ' ';
    cout << endl;
}


양방향 반복자

list는 양방향 반복자를 지원하기 때문에 []연산자를 사용할 수 없다.
또한 +, -, +=, -=도 사용할 수 없다. 따라서 ++, --을 이용한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#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();
    ++iter;     // 이 시점에 20을 가리킨다.
    ++iter;     // 이 시점에 30을 가리킨다.

    cout << *iter << endl;

    --iter;     // 이 시점에 20을 가리킨다.

    cout << *iter << endl;
}


중간 요소의 삽입/삭제

list의 중간 요소의 삽입과 삭제는 상수의 시간 복잡도를 가진다.
이는 양방향 연결 리스트의 특징에서 기인한다.

vector의 경우, 중간에 요소를 삽입하게 되면 메모리가 재할당될 수 있다.
뿐만 아니라 삽입 지점부터 원소 모두를 한 칸씩 밀어야만 한다.

deque의 경우, vector보다 효율적이긴 하지만 삽입 지점부터 원소 모두를 한 칸씩 밀어내야만 하는 것은 변함이 없다.

하지만 list는 중간에 요소를 삽입한 후 포인터를 이용하여 연결하면 된다.
따라서 O(n)의 시간 복잡도를 가진다. 중간 원소 삭제 연산 역시 마찬가지다.

아래는 vector와 list의 차이를 보여준다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <iostream>
#include <vector>
#include <list>

using namespace std;

int main(void)
{
    vector<int> vec;
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);
    vec.push_back(40);  // 이 시점에서 capacity는 4다.

    list<int> lt;
    lt.push_back(10);
    lt.push_back(20);
    lt.push_back(30);
    lt.push_back(40);

    vector<int>::iterator viter = vec.begin();
    viter += 2;

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

    // 이 위치에서 viter와 liter는 같은 요소를 가리킨다.

    // 원소의 개수와 capacity가 동일하므로
    // 현재 원소의 개수의 2배만큼의 메모리가 재할당되며
    // 모든 원소를 복사하면서 600을 삽입한다.
    vec.insert(viter, 600);

    // 단순히 20과 30 사이에 600을 삽입한다.
    lt.insert(liter, 600);
}


값을 이용한 삭제

list는 vector와 deque과는 달리 값을 이용하여 원소를 삭제할 수 있다.

remove()는 같은 값을 가진 모든 원소를 삭제한다. 이때 내부적으로 모든 요소를 탐색하며 값을 비교하는 과정을 거친다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <iostream>
#include <list>

using namespace std;

int main(void)
{
    list<int> lt;
    lt.push_back(10);
    lt.push_back(20);
    lt.push_back(40);
    lt.push_back(30);
    lt.push_back(50);
    lt.push_back(10);

    list<int>::iterator iter;
    // 10 20 40 30 50 10이 출력된다.
    for(iter = lt.begin(); iter != lt.end(); iter++)
        cout << *iter << ' ';
    cout << endl;

    lt.remove(10);

    // 20 40 30 50이 출력된다.
    for(iter = lt.begin(); iter != lt.end(); iter++)
        cout << *iter << ' ';
    cout << endl;
}

remove_if()와 커스텀 단항 조건자를 사용하면 조건에 맞는 원소들만을 제거할 수 있다.
이때 단항 조건자는 bool을 반환하는 함수류를 말한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include <iostream>
#include <list>

using namespace std;

bool Predicate(int number)
{
    return 10 <= number && number <= 30;
}

int main(void)
{
    list<int> lt;
    lt.push_back(10);
    lt.push_back(20);
    lt.push_back(40);
    lt.push_back(30);
    lt.push_back(50);
    lt.push_back(10);

    list<int>::iterator iter;
    // 10 20 40 30 50 10이 출력된다.
    for(iter = lt.begin(); iter != lt.end(); iter++)
        cout << *iter << ' ';
    cout << endl;

    lt.remove_if(Predicate);

    // 40 50이 출력된다.
    for(iter = lt.begin(); iter != lt.end(); iter++)
        cout << *iter << ' ';
    cout << endl;    
}


원소를 잘라 붙이기

list는 다른 list에 있는 원소나 구간을 잘라내어 자신의 리스트의 중간에 삽입할 수 있다.
이때 splice()를 사용한다.

아래의 코드는 list 전체를 잘라 붙이는 코드의 예시다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <iostream>
#include <list>

using namespace std;

int main(void)
{
    list<int> lt1;
    lt1.push_back(10);
    lt1.push_back(20);
    lt1.push_back(30);
    lt1.push_back(40);
    lt1.push_back(50);

    list<int> lt2;
    lt2.push_back(100);
    lt2.push_back(200);
    lt2.push_back(300);
    lt2.push_back(400);
    lt2.push_back(500);

    list<int>::iterator iter = lt1.begin();
    ++iter;
    ++iter;

    lt1.splice(iter, lt2);

    for(iter = lt1.begin(); iter != lt1.end(); iter++)
        cout << *iter << ' ';
    cout << endl;   

    for(iter = lt2.begin(); iter != lt2.end(); iter++)
        cout << *iter << ' ';
    cout << endl;   
}

다음 코드는 list의 특정 원소 그리고 특정 구간을 잘라 붙이는 예시다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#include <iostream>
#include <list>

using namespace std;

int main(void)
{
    list<int> lt1;
    lt1.push_back(10);
    lt1.push_back(20);
    lt1.push_back(30);
    lt1.push_back(40);
    lt1.push_back(50);

    list<int> lt2;
    lt2.push_back(100);
    lt2.push_back(200);
    lt2.push_back(300);
    lt2.push_back(400);
    lt2.push_back(500);

    list<int>::iterator iter1 = lt1.begin();
    ++iter1;
    ++iter1;
    
    list<int>::iterator iter2 = lt2.begin();

    lt1.splice(iter1, lt2, iter2);

    for(iter = lt1.begin(); iter != lt1.end(); iter++)
        cout << *iter << ' ';
    cout << endl;   

    for(iter = lt2.begin(); iter != lt2.end(); iter++)
        cout << *iter << ' ';
    cout << endl;   

    lt1.splice(iter1, lt2, lt2.begin(), lt2.end());

    for(iter = lt1.begin(); iter != lt1.end(); iter++)
        cout << *iter << ' ';
    cout << endl;   

    for(iter = lt2.begin(); iter != lt2.end(); iter++)
        cout << *iter << ' ';
    cout << endl;   
}


원소 역순 배치

list의 reverse()를 이용하면 원소들의 순서를 역순으로 뒤집을 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#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;

    // 10 20 30 40 50이 출력된다.
    for(iter = lt.begin(); iter != lt.end(); iter++)
        cout << *iter << ' ';
    cout << endl;    

    lt.reverse();

    // 50 40 30 20 10이 출력된다.
    for(iter = lt.begin(); iter != lt.end(); iter++)
        cout << *iter << ' ';
    cout << endl; 
}


정렬

vector, deque과 같은 시퀀스 컨테이너는 원소들의 순서가 있기 때문에 정렬이 가능하다.
list도 시퀀스 컨테이너기 때문에 마찬가지다.

하지만 algorithm 헤더에 포함된 sort()는 [] 연산자를 이용한 퀵 정렬로 구현되기 때문에 양방향 반복자만을 지원하는 list는 sort()를 사용할 수 없다.

따라서 list의 멤버 함수로 sort()가 지원된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include <iostream>
#include <list>

using namespace std;

int main(void)
{
    list<int> lt;

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

    // 오름차순으로 list가 정렬된다.
    lt.sort(less<int>());
}

sort()를 사용할 때는 정렬 조건을 포함하는 함수 객체를 사용한다.
함수 객체를 정의하여 이를 전달하는 방법도 가능하다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <iostream>
#include <list>

using namespace std;

// 내림차순 정렬 구현
struct Greater
{
    bool operator() (int left, int right) const
    {
        return left > right;
    }
};

int main(void)
{
    list<int> lt;

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

    // 60 50 40 30 20 10으로 정렬된다.
    lt.sort(Greater());
}


원소 중복 제거

list의 unique()를 이용하면 인접한 중복되는 원소들을 제거할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>
#include <list>

using namespace std;

int main(void)
{
    list<int> lt;

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

    lt.unique();

    // 10 20 30 40 50 40이 출력된다.
    for(list<int>::iterator iter = lt.begin(); iter != lt.end(); iter++)
        cout << *iter << ' ';
    cout << endl;
}

위의 예시를 살펴보면 40은 인접하지 않기 때문에 중복이 제거되지 않는다.
이런 상황에서 독립적인 원소만 남길 원하면 sort() 후 unique()를 사용한다.


리스트 합병

list끼리 합병해야 한다면 merge()를 통해 두 list를 합병할 수 있다.
주의해야 할 점은 list가 모두 같은 조건으로 정렬되어 있어야 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include <iostream>
#include <list>

using namespace std;

int main(void)
{
    list<int> lt1;
    lt1.push_back(10);
    lt1.push_back(20);
    lt1.push_back(30);
    lt1.push_back(40);
    lt1.push_back(50);

    list<int> lt2;
    lt2.push_back(25);
    lt2.push_back(35);
    lt2.push_back(60);

    cout << "list 1: ";
    for(list<int>::iterator iter = lt1.begin(); iter != lt1.end(); iter++)
        cout << *iter << ' ';
    cout << endl;
    
    cout << "list 2: ";
    for(list<int>::iterator iter = lt2.begin(); iter != lt2.end(); iter++)
        cout << *iter << ' ';
    cout << endl;

    cout << "==================" << endl;

    // lt2를 lt1으로 합병 정렬한다.
    lt1.merge(lt2);

    cout << "list 1: ";
    for(list<int>::iterator iter = lt1.begin(); iter != lt1.end(); iter++)
        cout << *iter << ' ';
    cout << endl;
    
    cout << "list 2: ";
    for(list<int>::iterator iter = lt2.begin(); iter != lt2.end(); iter++)
        cout << *iter << ' ';
    cout << endl;    
}

또한 merge()에 조건자를 사용하여 합병할 수 있다.

정렬 기준이 틀렸거나 합병할 list가 정렬되어 있지 않다면 merge()는 실패하며 오류가 발생한다.


정리

  • list는 시퀀스 컨테이너이자, 노드 기반의 컨테이너다.
  • list의 삽입/삭제 연산은 연결 리스트 기반이라 매우 효율적이다.
  • list는 양방향 반복자를 지원하므로 []를 사용할 수 없다.
  • list는 algorithm의 sort() 대신 멤버 함수 sort()를 사용한다.
C++, STL
C++ STL
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.