C++ List Container

해당 글은 공부를 하면서 적은 글이기 때문에 틀릴 수 있습니다. 참고용으로만 봐주세요~

 

0. 개요

---

vector와 array에 이어 list를 다시 한번 살펴보며 공부했습니다.

 

1. List Container

---

list도 vector, string, deque와 마찬가지로 STL 표준 시퀀스 컨테이너의 일종입니다.

때문에 순서를 유지하는 구조입니다.

 

list는 노드 기반 컨테이너이고, C++의 list 경우 이중 연결 리스트(doubly linked list)와 매우 유사합니다.

 

list는 vector와 마찬가지로 동적 할당을 받기 때문에 길이가 가변적이다는 특징이 있습니다.

하지만 vector나 array와 달리 메모리상 저장된 데이터가 연속적으로 존재하지 않습니다. 이러한 차이점으로 인해 vector와 장단점이 다릅니다.

 

vector나 array는 메모리 공간상 연속적인 위치에 존재하기 때문에 Index를 이용해 쉽게 접근이 가능했지만, list의 경우 노드 단위로 나뉘어 노드는 메모리에 할당받을 때 연속된 공간을 할당받지 않습니다. 노드에 데이터가 저장이 되고, 해당 노드는 단방향 혹은 쌍방향으로 다음 노드와 이전 노드의 주소를 가지고 있게 되어 있습니다.

때문에 index로 한번에 원하는 데이터에 접근이 불가능하다는 단점이 있습니다.

하지만 각 노드간의 주소로 연결되어 있기 때문에 중간지점에 노드 삽입과 삭제가 vector보다 빠르게 진행됩니다.

 

왜냐하면 노드가 이전, 다음 노드의 주소를 가지고 있기 때문에 해당 주소 연결만 다시 해주면되서 해당 작업이 훨씬 빠릅니다.

vector의 경우 중간 요소를 삭제하거나 삽입하면 데이터를 한 칸씩 뒤로 밀어주어야 하므로 선형시간이 걸렸습니다.

하지만  list의 경우 중간 요소를 삭제하거나 삽입하면 상수시간에 해결되기 때문에 차이가 큽니다.

 

이러면 list가 정말 좋아보이는데, list가 지닌 단점도 존재합니다.

위에서 말했다싶이 index를 이용해 빠르게 원하는 데이터에 접근하는 것이 불가능하다는 점입니다.

이러한 이유로 list의 시작 노드 혹은 끝 노드에서 출발해 하나하나 순회하면서 원하는 데이터가 존재하는 노드로 접근을 해야합니다. 노드의 개수가 많으면 많을 수 록, 시작 노드와 끝 노드에서 거리가 멀어질 수 록 탐색시간은 더욱 더 증가하게 됩니다.

 

정리해 보자면 다음과 같습니다.

list는 vector, string, deque와 같은 STL 표준 시퀀스 컨테이너이다.
list는 노드 기반 컨테이너이고, C++에서는 이중 연결 리스트와 매우 유사하다.
list는 길이가 가변적이다.
list는 검색, 탐색이 비효율적이다.
list는 삭제와 삽입이 용이하다.
list는 vecter나 array처럼 index를 이용해 접근할 수 없다.

 

list는 노드 기반이고 주소로 연결되었다는데 그러면  list는 도대체 어떤식으로 구성되어있는 걸까요?

 

list container의 구성

간략하게 위 그림처럼 구성되어 있습니다.

실제 list 구성과 다를 수 있지만, list는 시작 노드와 끝 노드의 주소를 알고 있고 각각의 노드들은 본인에 저장된 값과 본인의 이전, 다음 노드의 주소를 가지고 있습니다.

또 이때 각 노드의 주소는 메모리상 연속적인 메모리 주소가 아닙니다.

 

list가 시작 노드와 끝 노드의 주소만 알고 있기 때문에 index로 인한 접근이 불가능합니다. ([] 연산자와 .at() 함수가 없습니다.)

때문에 시작 노드 혹은 끝 노드에 접근해 다음 혹은 이전 노드로 계속 접근해가며 원하는 값을 지닌 노드를 탐색해야 합니다.

 

반면 삽입과 삭제는 노드 하나만 생성하고, 원하는 지점에서 노드간 연결을 끊어준 뒤, 새로 생성한 노드와 서로 주소를 연결해주면 되서 처리 속도가 빠릅니다.

 

간단하게 list의 구성을 살펴보았으니 이제 사용 방법에 대해 살펴봅시다.

 

2. list container 사용법

---

vector, array등과 마찬가지로 <list> 헤더를 포함해주어야 사용이 가능합니다.

namespace 또한 마찬가지로 std에 담겨있습니다.

 

다른 STL과 비슷하게 선언은 list<자료형(Data Type)> 변수명 입니다.

#include <list>
using namespace std;

void main()
{
    list<int> list_Test;

    return;
}

 

list의 멤버 함수

◈ list.assign();

    list에서 요소를 삭제하고 대상 목록에 요소의 새 집합을 복사합니다.

    전달되는 인자에 따라 특정 범위까지의 요소 대입, 다른 list의 요소로 복사 대입 전환 등을 해주는 함수 같다.

    자새한 것은 MSDN에 예제를 살펴보면 좋을 것 같다.

 

◈ list.front();

    list의 첫 번째 요소에 대한 참조를 반환합니다.

 

◈ list.back();

    list의 마지막 요소에 대한 참조를 반환합니다.

 

◈ list.begin();

    list의 첫 번째 요소의 주소를 지정하는 iterator를 반환합니다.

 

◈ list.cbegin();

    list의 첫 번째 요소의 주소를 지정하는 const_iterator를 반환합니다.

 

◈ list.end();

    list에서 마지막 요소 다음에 나오는 위치 주소를 지정하는 iterator를 반환합니다.

    즉, end iterator를 반환한다.

 

◈ list.cend();

    list에서 마지막 요소 다음에 나오는 위치 주소를 지정하는 const_iterator를 반환합니다.

 

◈ list.clear();

    list의 모든 요소를 지웁니다.

    clear() 함수를 이용해 요소를 지우고 나면 size()는 0이 된다.

 

◈ list.crbegin();

    역방향 list에서 첫 번째 요소의 주소를 지정하는 const_iterator를 반환합니다.

    -> list에서 end const_iterator를 반환.

 

◈ list.cend();

    역방향 list에서 마지막 요소 다음에 나오는 위치의 주소를 지정하는 const_iterator를 반환합니다.

    -> list에서 첫 번째 요소의 const_iterator를 반환.

 

◈ list.emplace(iterator, value);

    생성된 요소를 list의 지정된 위치에 삽입합니다.

 

◈ list.emplace_back(value);

    생성된 요소를 list 끝 부분에 추가합니다.

 

◈ list.emplace_front(value);

    생성된 요소를 list 시작 부분에 추가합니다.

 

◈ list.empty();

    list가 비어있는지 확인에 bool값을 반환합니다.

 

◈ list.erase(iterator);

    list의 지정된 위치에서 요소 또는 요소 범위를 제거합니다.

    인자로 iterator를 하나 더 전달해 제거할 범위를 지정해 사용할 수도 있다.

    이때, 두번 째 iterator는 제거되는 마지막 요소 바로 뒤의 위치라는 점을 주의해야 한다.

 

◈ list.get_allocator();

    list를 생성하는데 사용된 allocator 개체의 복사본을 반환합니다.

 

◈ list.insert(iterator, value);

    요소 하나 또는 여러 개나 요소의 범위를 list의 지정된 위치에 삽입합니다.

    보다 자세한 내용은 MSDN을 참고해주세요. 다양한 오버로딩된 함수가 존재합니다.

 

◈ list.max_size();

    list의 최대 길이를 반환합니다. 이때 반환은 size_t 입니다.

 

◈ list.marge(list<Type, Allocator> right);

    요소를 인수 목록에서 제거하고 대상 목록에 삽입한 다음 새로 조합된 요소 집합을 오름차순 혹은 기타 지정된 순서로 정렬합니다.

    Allocator는 list에 포함되어 있기 때문에 단순 list만 넣어주어도 된다. (표준 Allocator를 사용하지 않았을 경우는 잘 모르겠다.)

    sort()를 이용해 정렬해주거나, marge()의 인자로 list를 전달해줄 때 추가로 greater<>()나 less<>()를 전달해 정렬해주어도 된다.

    직접 정렬함수를 만들어주어도 정렬이 가능해보인다.

 

◈ list.pop_back();

    list의 끝에 있는 요소를 삭제합니다.

 

◈ list.pop_front();

    list의 시작 부분에 요소를 추가합니다.

 

◈ list.push_back();

    list의 끝에 요소를 추가합니다.

 

◈ list.push_front();

    list의 시작 부분에 요소를 추가합니다.

 

◈ list.remove(value);

    list에서 지정된 값과 일치하는 요소를 list에서 지웁니다.

 

◈ list.remove_if();

    지정된 조건자를 충족하는 요소를 list에서 지웁니다.

    해당 함수를 사용하기 위해서 템플릿 클래스를 직접 구현해 주어야 한다.

    클래스에서 연산자 오버로딩을 통해 직접 조건자를 만들어 주어야 한다.

 

◈ list.resize(size);

    list의 새 크기를 지정합니다.

    새 크기가 원래 크기보다 클 경우 list에 추가되는 새 요소의 값을 지정해 줄 수 있고, 새 요소의 값을 지정하지 않으면 기본가밧이 할당 된다.

 

◈ list.reverse();

    list에 요소가 나타내는 순서를 반대로 바꿉니다.

 

◈ list.size();

    list에 있는 요소의 수를 반환합니다.

 

◈ list. sort();

    오름차순 또는 기타 순서 관계를 기준으로 list의 요소를 정렬합니다.

 

◈ list.splice();

    인수 list에서 요소를 제거하고 대상 list에 삽입합니다.

 

◈ list.swap();

    두 list의 요소를 서로 맞 바꿔줍니다.

 

◈ list.unique()

    list에서 인접하는 중복 요소 또는 기타 이전 조건자를 충족하는 인접 요소를 제거합니다.

 

멤버 함수들을 살펴보면 모든 STL은 각각 사용감이 비슷하도록 만들어져있는 것을 알 수 있다.

emplace()와 insert()의 차이

insert(), push_back()의 경우 객체를 복사하여 삽입하는 방식을 취하기 때문에 임시객체가 생성되었다 삭제되는 과정이 불가피하다.

하지만 emplace()는 임시객체를 생성, 삭제하는 과정이 존재하지 않으며 함수의 인자는 객체의 생성자의 인자와 동일한 인자를 갖는다.

 

이는 직접 복사 생성자를 만들어 확인해 볼 수 있다.

 

보통 emplace()와 push_back()의 차이에 대한 내용이 있어서 insert와의 차이는 더 찾아봐야 정확히 알수있을 것 같다.

 

3. 참고 문헌

---

list 클래스

 

[emplace 함수] std 컨테이너에 개체 삽입시 발생하는 임시객체를 없애자.

 

[Effective Modern C++] 항목 42. 삽입 대신 생성 삽입을 고려하라