6. STL 사용하기 - std::list

STL 이란?

C++ 에서 제공하는 STandard Library를 STL이라고 한다. 자바에서는 자바에서 제공하는 API라고 볼 수 있다.

지금까지 list에 대해 직접 설계해보았고 list에 대한 설명이 충분했다.

이번에는 STL을 직접 사용하면서 어떤 기능이 있고 언제, 어떻게 사용할 지 생각해보도록 하자.

※ 시간이 오래 걸리는 Method는 제외한다. (효율적 사용)

---

std::list 

Construct

Method	Description
(constuctor)	리스트 생성시 입력 값
operator=	= 기호에 대한 연산 방법

 

Iterators

Method	Description
begin()	리스트 Head에 속한 데이터 위치
end()	리스트 마지막 위치 != Tail, null 값
rbegin()	reverse, 리스트 Tail에 속한 데이터 위치
rend()	reverse, 리스트 마지막 위치 != Head, null 값

 

Capacity

Method	Description
empty()	리스트 Head에 속한 데이터 위치
size()	리스트 마지막 위치 != Tail, null 값

 

Element access:

Method	Description
front()	Head의 데이터를 반환
back()	Tail의 데이터를 반환

 

Modifiers:

Method	Description
push_front()	Head를 추가
push_back()	Tail을 추가
pop_front()	Head를 제거
pop_back()	Tail을 제거
insert()	특정 위치에 데이터를 추가
erase()	특정 위치의 데이터를 삭제

 

Operations:

Method	Description
sort()	리스트를 정렬
reverse()	리스트를 뒤집음

 

---

 

Code

#include <iostream>
#include <list>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    // constructor
    list<int> emptyList1;                    // {}
    list<int> l1(3, 10);                    // {3, 3, 3}
    list<int> l2(l1.begin(), l1.end());        // {3, 3, 3}
    list<int> l3(l1);                        // {3, 3, 3}
    int arr[3] = {1, 2, 3};                    
    list<int> l4 (arr, arr + 3);            // {1, 2, 3}

    // operator=
    list<int> emptyList2 = list<int>();        // {}
    list<int> l5 = l4;                        // {1, 2, 3}
    list<int> l6 = {1, 2, 3};                // {1, 2, 3}

    // Iterators
    for (list<int>::iterator it = l6.begin(); it != l6.end(); it++) {
        cout << *it << " ";
    }
    cout << "\n";


    for (list<int>::reverse_iterator it = l6.rbegin(); it != l6.rend(); it++) {
        cout << *it << " ";
    }
    cout << "\n\n";

    // Capacity
    cout << "emptyList1 is empty ? - " << (emptyList1.empty() ? "Yes\n" : "No\n"); 
    cout << "l6 is empty ? - " << (l6.empty() ? "Yes\n" : "No\n"); 
     cout << "size of l6 : " << l6.size() << "\n\n";

     // Element access
     cout << "l6's front : " << l6.front() << '\n';
     cout << "l6's back : " << l6.back() << "\n\n";

     // Modifiers
     cout << "Stack\n";
     l6.push_back(10);                        // {1, 2, 3, 10}                
     l6.push_back(20);                        // {1, 2, 3, 10, 20}
     while (!l6.empty()) {
         cout << l6.back() << " ";
         l6.pop_back();
    }
    cout << "\n";

    cout << "Queue\n";
    l4.push_front(10);                        // {10, 1, 2, 3}
    l4.push_front(20);                        // {20, 10, 1, 2, 3}
    while (!l4.empty()) {
        cout << l4.front() << " ";
        l4.pop_front();
    }
    cout << "\n";

    cout << "Insert\n"; 
     l5.insert(l5.end(), 5);                    // {1, 2, 3, 5}
     l5.insert(l5.begin(), 42);                // {42, 1, 2, 3, 5}
     auto it = l5.begin();                     // {42(it), 1, 2, 3, 5}
    advance(it, 2);                            // {42, 1, 2(it), 3, 5} 
     l5.insert(it, 16);                        // {42, 1, 16, 2(it), 3, 5}
    l5.insert(it, 3, 25);                    // {42, 1, 16, 25, 25, 25, 2(it), 3, 5}
     l5.insert(it, {3, 0});                    // {42, 1, 16, 25, 25, 25, 3, 0, 2(it), 3, 5}
     for (it = l5.begin(); it != l5.end(); it++) {
         cout << *it << " ";
    }
    cout << "\n"; 

    cout << "Erase\n";
    auto it1 = l5.begin();                     // {42(it1), 1, 16, 25, 25, 25, 3, 0, 2, 3, 5}
    auto it2 = l5.begin();                    // {42(it1, it2), 1, 16, 25, 25, 25, 3, 0, 2, 3, 5}
    advance(it2, 4);                        // {42(it1), 1, 16, 25, 25(it2), 25, 3, 0, 2, 3, 5}
    cout << "value of it1 before deletion : " << *it1 << ", ";
    it1 = l5.erase(it1);                    // {1(it1), 16, 25, 25(it2), 25, 3, 0, 2, 3, 5}
    cout << "value of it1 after deletion : " << *it1 << "\n";
    cout << "value of it2 before deletion : " << *it2 << ", ";
    it2 = l5.erase(it2);                    // {1(it1), 16, 25, 25(it2), 3, 0, 2, 3, 5}
    cout << "value of it2 after deletion : " << *it2 << "\n";
    auto it3 = l5.erase(it1, it2);                        // {25(it1, it2), 3, 0, 2, 3, 5}
    cout << "delete from it1 to it2 : ";
    for (it = l5.begin(); it != l5.end(); it++) {
        cout << *it << ' ';
    }
    cout << "\n";
    cout << "it1 = " << *it1 << ", it2 = " << *it2 << ", it3 = " << *it3 <<"\n"; 
    cout << "↑↑↑↑↑↑↑ 오류 발견, 반환 값은 it2 \n\n";

    // Operations
    l5.sort(); 
    cout << "Sorted N log N\n";
    for (it = l5.begin(); it != l5.end(); it++) {
        cout << *it << " ";
    }
    cout << "\n";

    l5.reverse();
    cout << "Reverse\n";
    for (it = l5.begin(); it != l5.end(); it++) {
        cout << *it << " ";
    }
    cout << "\n";

    return 0;
}

 

실행결과

 

범위 erase시 it1이 남아있는 것을 보아 2가지를 의심할 수 있음.

1. array 구조 list일 시, iterator가 index를 참조하므로 it1이 남아 있을 수 있음.

2. Node 구조 list일 시, iterator를 delete하지 않음. 메모리 누수

C++ STL의 경우, 웬만하면 예외처리를 하지 않으므로 사용법을 정확히 숙지하는 것이 좋다.

 

참고

cpp STL reference

https://cplusplus.com/reference/list/list/

 

Repository

https://github.com/jihwankim128/datastructure

GitHub - jihwankim128/datastructure

 

list 만들어 보기

이중 연결 리스트 포스트

4. STL 따라잡기 - 이중 연결 리스트 (Doubly Linked List) 구현