[Basic C++] #35_list, 순차 컨테이너

 

[Basic C++] #35_list, 순차 컨테이너

 

C++ 개발에서 표준 라이브러리(STL)의 List에 대해 알아보겠습니다.

"전문가를 위한 C"의 16 항목, "컨테이너와 반복자 이해하기"에 해당하는 내용입니다.

 

---

 

Overview

 

1. 개념
2. 초기화
3. 접근
4. 반복자
5. 삽입, 제거
6. 크기
7. splice
8. 그 외 자체 제공 메서드

 

#0. 개념

1. list?

• "list" 또한 "vector" 그리고 "deque"와 같이 순차 컨테이너입니다.
• C++의 "list"는 이중 연결 리스트로 모든 위치에서 상수 시간의 삽입과 삭제 성능을 보여줍니다.
• 다만, 개별 항목에 접근하는 데에 비교적 느린 성능을 보여줍니다.
• list는 "operator[]"와 같이 랜덤 액세스가 불가능합니다. 따라서, 개별 항목에 접근하기 위해 반복자가 필요합니다. 

 

#1. 점근

 

list<int> l;

// 1. front(): 첫 번째 항목의 참조 반환
l.front();

// 2. back(): 마지막 항목의 참조 반환
l.back();

// 3. begin(): 첫 번째 항목을 가리키는 반복자 반환
l.begin();

// 4. end(): 마지막 항목 직후의 위치를 가리키는 반복자 반환
l.end();

5. 이하 vector와 동일 ( cbegin(), cend(), etc )

 

#2. 반복자

 

list<int> myList;
list<int>::iterator it = myList.begin();

// 반복자의 앞 뒤 이동
++it;
--it;

// 반복자의 임의의 위치로 이동은 불가능합니다. 
it+5;	// 에러!!
it+3;	// 에러!!

 

Details

 

• list의 반복자는 앞, 뒤 이동은 가능하지만, +5 등의 임의의 위치로 이동하는 것은 불가능합니다! 

 

#3. 삽입, 제거

 

list<int> myList;

// 1. push_front(): 맨 앞에 새로운 항목 추가
myList.push_front(2);

// 2. pop_front(): 맨 앞에 항목을 제거합니다
myList.pop_front();

// 3. emplace_front(): 맨 앞에 임시 객체를 추가합니다
int a = 5;
myList.emplace_front(a+3);

 

Details

 

• 대부분의 메서드는 vector 컨테이너와 동일합니다.
• 다만, list는 이중 연결 리스트로, 컨테이너의 앞쪽에서 삽입과 제거를 수행할 수 있습니다. 

 

#4. 크기, 용량

 

• list는 vector와 다르게 내부의 메모리 관리 구조를 노출하지 않습니다. 
• 따라서, size(), empty(), 그리고 resize() 메서드들은 지원하지만, 
• reserve(), 그리고 capacity() 메서드들은 지원하지 않습니다.

 

#5. splice, 바꿔치기

 

// 1. 기본
void splice( const_iterator pos, list& other );

// 2. 이동 시맨틱 (우측 참조형)
void splice( const_iterator pos, list&& other );

// 3. list의 반복자가 가리키는 특정 항목만
void splice( const_iterator pos, list& other, const_iterator it );

// 4. 위의 이동 시맨틱 (우측 참조형)
void splice( const_iterator pos, list&& other, const_iterator it ); // C++11 부터

// 5. 다른 list의 first 반복자  ~ last 반복자 구간을 pos에 삽입합니다.
void splice( const_iterator pos, list& other, 
             const_iterator first, const_iterator last);
             
// 6. 위의 이동 시맨틱 (우측 참조형)
void splice( const_iterator pos, list&& other, 
             const_iterator first, const_iterator last );
             
/********************************************************************/

#include <list>
#include <functional>
#include <iostream>
using namespace std;

int main ()
{
    list<string> list1{ "a", "b", "c", "d", "e"};
    list<string> list2{ "X", "Y", "Z" };
    
    // list1의 반복자 선언
    list<string>::const_iterator it1 = list1.begin();
    or
    // auto it1 = list1.begin();
    
    it1++;	// 0 -> 1로 이동
    
    list1.splice(it1, list2);
    
    // 결과 : a X Y Z b c d e 
}

 

Details

 

• list의 "splice()" 메서드는 특정 list의 전체 혹은 일부 항목들을 통째로 다른 list의 임의 위치에 삽입하는 작업을 수행합니다.
• "splice()"는 상수 시간의 성능을 보여줍니다. 
• 이때, 삽입되는 list의 원본 항목들은 삭제됩니다.
• * splice() 메서드의 경우 잘라 붙이기로 이해하면 됩니다.

 

#6. 그 외 자체 메서드

 

list<int> list1{1, 2, 3, 4, 5};

// 1. remove(val): val 과 같은 값을 갖는 특정 항목 제거
list1.remove(3);

// 2. remove_if(Predicate): 단항 조건자 Predicate에 해당하는 항목을 모두 제거합니다.
bool Predicate(int num)
{
    return num < 4;
}

list1.remove_if(Predicate);

// 3. unique(): list에서 중복되는 항목을 제거합니다. 
list1.push_back(2);

list1.unique();

// 4. merge(): 오름차순으로 정렬되어있는 두 list를 병합합니다. 기준은 오름차순입니다.
list<int> list2 { 6, 7, 8, 9, 10};

list1.merge(list2);	// list2의 모든 항목은 복제가 아니라 전송됩니다.

// 5. sort(): 오름차순으로 정렬합니다. Predicate를 인자로 받을 수 있습니다.
list1.sort(/*Predicate*/);

// 6. reverse(): 항목들을 역순으로 재배치합니다. 
list1.reverse();