C++ STL list

• C++에서의 list(리스트)는 시퀀스 컨테이너 중 하나로서, 노드를 기반으로 한 이중 연결 리스트(doubly linked list)로 구현되어 있습니다.
• 리스트는 원소들의 삽입과 삭제가 용이하며(시간복잡도가 O(1)입니다.), 따라서 vector에 비해 원소를 수정하거나 삭제하는 경우가 많을 때 주로 사용됩니다.
• 리스트는 특성 상 임의적 접근이 불가능하며, STL의 sort함수도 사용할 수 없는 대신, 자체적으로 정렬을 지원하는 멤버함수들을 가지고 있습니다.
• list 컨테이너를 사용하기 위해서는 아래와 같이 <list> 헤더를 포함해야 하고, 선언할 때는 컨테이너에 들어갈 원소의 타입을 명시해주어야 합니다.

#include <list>
std::list<type> l; // namespace std 사용 시 std 생략가능

 

• 기존에 사용하던 배열처럼 생성할 때 크기를 지정해주거나 특정 원소 값으로 초기화시켜서 사용할 수도 있습니다.

list<int> l1(10); // 크기가 10인 리스트 l1 선언(기본값은 0으로 초기화)
list<int> l2(10, 7); // 크기가 10이고, 7로 초기화된 리스트 l2 선언

 

<리스트의 멤버 함수>

-list<int> l; list<int>::iterator itr; 와 int element; 로 선언되어 있다고 가정합니다-

 

 1) 삽입과 삭제

l.push_front(element);

-> 리스트의 가장 앞에 원소를 추가합니다.

 

l.push_back(element);

-> 리스트의 가장 뒤에 원소를 추가합니다.

 

l.insert(itr, element);

-> 반복자가 가리키는 자리에 원소를 추가합니다.

 

l.pop_front();

-> 리스트의 가장 앞의 원소를 제거합니다.

 

l.pop_back(element);

-> 리스트의 가장 뒤의 원소를 제거합니다.

 

l.remove(element);

-> 리스트에 element와 같은 원소를 모두 삭제합니다.

 

l.clear();

-> 리스트의 모든 원소를 삭제합니다.

 

 2) 원소 참조

*리스트는 벡터나 덱과는 달리 인덱스를 이용한 접근이 불가능하며, 반복자를 이용하여 하나씩 탐색하는 것이 일반적입니다.

l.front();

l.back();

-> l.front()는 리스트의 가장 앞의 원소를 참조하여 반환하고, l.back()은 리스트의 가장 뒤의 원소를 참조하여 반환합니다.

 

l.begin();

l.end();

-> l.begin()은 리스트의 가장 앞 원소의 반복자를 반환하고, l.end()는 리스트의 가장 뒤 원소의 위치 + 1의 반복자를 반환합니다.

 

 

 3) 정렬

l.sort(compare);

-> 리스트를 compare에 따라 정렬합니다. 조건이 없을 경우 기본적으로 오름차순으로 정렬합니다.

 

l.reverse();

-> 리스트의 원소의 순서들을 반대로 뒤집습니다. (front - back => back - front)

 

l.unique();

-> 리스트를 순회하며 각 노드의 양 옆의 원소를 비교하며 같은 경우 삭제합니다.

-> 리스트를 정렬한 후 사용하면 위의 원리에 따라 중복되는 값을 모두 제거할 수 있습니다.

 

 

 4) 사이즈 관련

l.size()

-> 리스트의 크기를 반환합니다.

 

l.empty();

-> 리스트가 비었는 지의 여부를 확인합니다. 비어있으면 1, 그렇지 않으면 0을 반환합니다.

 

---