[STL] list 정리 및 예제

[STL] list 정리 및 예제

list 컨테이너는 vector와 deque 처럼 시퀀스 컨테이너로 원소가 상대적인 순서를 유지한다.

그러나 list는 노드 기반 컨테이너로 원소가 노드 단위로 저장되며 list는 이중 연결 리스트로 구현된다.

[기타/C++ STL] - [STL] vector 벡터 정리 및 예제

[기타/C++ STL] - [STL] deque 정리 및 예제

템플릿 형식
template<typename T, typename Allocator=allocator<T>> calss list	T 는 list 컨테이너 원소의 형식

생성자
list lt	lt는 빈 컨테이너이다.
list lt(n)	lt는 기본값으로 초기화된 n개의 원소를 갖는다.
list lt(n, x)	lt는 x 값으로 초기화된 n개의 원소를 갖는다.
list lt(lt2)	lt는 lt2 컨테이너의 복사본이다
list lt(b,e)	lt는 반복자 구간 [b,e)로 초기화된 원소를 갖는다.

멤버 함수
lt.assign(n,x)	lt에 x 값으로 n개의 원소를 할당한다.
lt.assign(b,e)	lt를 반복자 구간 [b,e)로 할당한다.
lt.back()	lt의 마지막 원소를 참조한다.
p=lt.begin()	p는 lt의 첫 원소를 가리키는 반복자다
lt.clear()	lt의 모든 원소를 제거한다.
lt.empty()	lt가 비었는지 조사한다.
p=lt.end()	p는 lt의 끝을 표식하는 반복자다
q=lt.erase(p)	p가 가리키는 원소를 제거한다. q는 다음 원소를 가리킨다.
q= lt.erase(b,e)	반복자 구간 [b,e)의 모든 원소를 제거한다. q는 다음 원소다
lt.front()	lt의 첫 번째 원소를 참조한다.
q=lt.insert(p,x)	p가 가리키는 위치에 x 값을 삽입한다. q는 삽입한 원소를 가리키는 반복자다
lt.insert(p,n,x)	p가 가리키는 위치에 n 개의 x 값을 삽입한다.
lt.insert(p,b,e)	p가 가리키는 위치에 반복자 구간 [b,e)의 원소를 삽입한다.
x=lt.max_size()	x는 lt가 담을 수 있는 최대 원소의 개수
lt.merge(lt2)	lt2를 lt로 합병 정렬한다.
lt.merge(lt2, pred)	lt2를 lt로 합병 정렬한다. pred(조건자)를 가지누으로 합병한다.
lt.pop_back()	lt의 마지막 원소를 제거한다.
lt.pop_front()	lt의 첫번째 원소를 제거한다.
lt.push_back(x)	lt의 끝에 x를 추가한다.
lt.push_front(x)	lt의 앞쪽에 x를 추가한다.
p=lt.rbegin()	p는 lt의 역 순차열의 첫 원소를 가리키는 반복자다
lt.remove(x)	x 원소를 모두 제거한다.
lt.remove_if(pred)	pred(단항 조건자)가 '참'인 모든 원소를 제거한다.
p=lt.rend()	p는 lt의 역 순차열의 첫 원소를 가리키는 반복자다
lt.resize(n)	lt의 크기를 n으로 변경하고 확장되는 공간의 값을 기본값으로 초기화한다.
lt.reverse()	lt 순차열을 뒤집는다.
lt.size()	lt 원소의 갯수다
lt.sort()	lt의 모든 원소를 오름 차순 으로 정렬한다.
lt.sort(pred)	lt의 모든 원소를 pred(조건자)를 기준으로 정렬한다.
lt.splice(p, lt2)	p가 가리키는 위치에 lt2의 모든 원소를 잘라 붙인다.
lt.splice(p, lt2, q)	p가 가리키는 위치에 lt2의 q가 가리키는 원소를 잘라 붙인다.
lt.splice(p, lt2, b, e)	p가 가리키는 위치에 lt2의 순차열 [b,e)를 잘라 붙인다.
lt.swap(lt2)	lt와 lt2를 swap 한다.
lt.unique()	인접한 원소의 값이 같다면 유일한 원소의 순차열로 만든다.
lt.unique(pred)	인접한 원소가 pred(이항 조건자)의 기준에 맞다면 유일한 원소의 순차열로 만든다

연산자
lt1 == lt2	lt1과 lt2의 모든 원소가 같은가? (bool)
lt1 != lt2	lt1과 lt2의 모든 원소 중 하나라도 다른 원소가 있는가
lt1 < lt2	문자열 비교처럼 lt2가 lt1보다 큰가?
lt1 > lt2	문자열 비교처럼 lt1이 lt2보다 큰가?

멤버 형식
allocator_type	메모리 관리자 형식
const_iterator	const 반복자 형식
const_pointer	const value_type* 형식
const_reference	const value_type& 형식
const_reverse_iterator	const 역 반복자 형식
difference_type	두 반복자 차이의 형식
iterator	반복자 형식
pointer	value_type* 형식
reference	value_type& 형식
reverse_iterator	역 반복자 형식
size_type	첨자(index)나 원소의 개수 등의 형식
value_type	원소의 형식

list는 시퀀스 컨테이너로 시퀀스 컨테이너가 갖는 모든 특징을 갖는다.

list는 노드 기반 컨테이너로 at()과 [] 연산자가 없으며 임의 접근 반복자가 아닌 양방향 반복자를 제공한다.

그래서 모든 원소를 탐색하려면 양방향 반복자의 연산인 ++, --를 사용한다.

list의 가장 큰 특징 중 하나는 순 차열 중간에 원소를 삽입(insert), 제거(erase) 하더라도 상수 시간 복잡도의 수행 성능을 보인다는 점이다.

배열 기반 컨테이너 vector 나 deque 처럼 원소를 밀어내지 않고 노드를 서로 연결하기만 되기 때문이다.

또한 노드 기반 컨테이너의 삽입과 제거 동작은 반복자를 무효화시키지 않는다.

반복자가 가리키는 원소 자체가 제거되지 않는 한 반복자가 가리키는 원소는 그대로 존재한다.

하지만, 배열 기반 컨테이너(vector, deque)의 반복자는 원소의 삽입과 제거 동작이 발생하면 메모리가 재할당되거나 원소가 이동할 수 있으므로 반복자가 무효화된다.

노드 기반 컨테이너로 insert()나 erase()는 배열 기반보다 효율적으로 동작하며 값의 비교로 원소를 제거하는 remove(), remove_if()를 제공한다.

또한 list는 다른 list와 결합할 때 좋은 컨테이너이다. splice() 멤버 함수는 노드의 연결 연산만으로 두 list를 하나의 리스트로 결합할 수 있으며, merge() 멤버 함수는 두 list를 하나의 list로 정렬하며 결합한다.

또한 당양한 기능을 수행하는 reverse(), sort(), unique()등의 멤버 함수도 제공한다.

#include <iostream> #include <list> using namespace std; bool Predicate(int n){     return n >= 30; } int main(){     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;     for (iter = lt.begin(); iter != lt.end(); ++iter){         cout << *iter << ' ';     }     cout << endl;     iter = lt.begin();     iter++;     iter++;     // erase 삭제     list<int>::iterator iter2 = lt.erase(iter);     for (iter = lt.begin(); iter != lt.end(); ++iter){         cout << *iter << ' ';     }     cout << endl;     cout << "iter2 : " << *iter2 << endl;     lt.push_back(10);     lt.push_back(10);     for (iter = lt.begin(); iter != lt.end(); ++iter){         cout << *iter << ' ';     }     cout << endl;     // 리스트에서 원소 10 제거     lt.remove(10);     for (iter = lt.begin(); iter != lt.end(); ++iter){         cout << *iter << ' ';     }     cout << endl;     // Predicate 함수에 해당하는 원소 제거 (30보다 크다)     lt.remove_if(Predicate);     for (iter = lt.begin(); iter != lt.end(); ++iter){         cout << *iter << ' ';     }     cout << endl;     return 0; }

결과 : 10 20 30 40 50 10 20 40 50 iter2 : 40 10 20 40 50 10 10 20 40 50 20

#include <iostream> #include <list> using namespace std; bool Predicate(int first, int second){     return second-first >=0; } int main(){     list<int> lt1;     list<int> lt2;     lt1.push_back(10);     lt1.push_back(20);     lt1.push_back(30);     lt1.push_back(40);     lt1.push_back(50);     lt2.push_back(100);     lt2.push_back(200);     lt2.push_back(300);     lt2.push_back(400);     lt2.push_back(500);     list<int>::iterator iter;     cout << "lt1 : ";     for (iter = lt1.begin(); iter != lt1.end(); ++iter){         cout << *iter << ' ';     }     cout << endl;     cout << "lt2 : ";     for (iter = lt2.begin(); iter != lt2.end(); ++iter){         cout << *iter << ' ';     }     cout << endl << "==================" << endl;     iter = lt1.begin();     ++iter;     ++iter;        //30 원소의 위치를 가리킴     lt1.splice(iter, lt2); // iter가 가리키는 위치(30)에lt2의 모든 원소를 잘라서 붙인다.     cout << "lt1 : ";     for (iter = lt1.begin(); iter != lt1.end(); ++iter){         cout << *iter << ' ';     }     cout << endl;     cout << "lt2 : ";     for (iter = lt2.begin(); iter != lt2.end(); ++iter){         cout << *iter << ' ';     }     cout << endl << "==================" << endl;     lt1.reverse();    // 리스트 역순 뒤집기     cout << "lt1 reverse : ";     for (iter = lt1.begin(); iter != lt1.end(); ++iter){         cout << *iter << ' ';     }     cout << endl << "==================" << endl;     lt1.push_front(50);     lt1.push_front(50);     lt1.push_back(10);     lt1.push_back(50);     cout << "lt1 : ";     for (iter = lt1.begin(); iter != lt1.end(); ++iter){         cout << *iter << ' ';     }     cout << endl;     lt1.unique();        // 인접한 중복 원소를 합친다.     cout << "lt1 unique : ";     for (iter = lt1.begin(); iter != lt1.end(); ++iter){         cout << *iter << ' ';     }     cout << endl;     lt1.unique(Predicate);    // Predicate에 따라 다음 원소가 크거나 같으면 제거한다.     cout << "lt1 unique Predicate: ";     for (iter = lt1.begin(); iter != lt1.end(); ++iter){         cout << *iter << ' ';     }     cout << endl << "==================" << endl;     lt1.sort();    // 오름차순으로 정렬한다.     cout << "lt1 sort : ";     for (iter = lt1.begin(); iter != lt1.end(); ++iter){         cout << *iter << ' ';     }     cout << endl << "==================" << endl;     lt2.push_back(30);     lt2.push_back(60);     lt2.push_back(10);     lt2.push_back(99);     lt2.sort();          cout << "lt1 : ";     for (iter = lt1.begin(); iter != lt1.end(); ++iter){         cout << *iter << ' ';     }     cout << endl;     cout << "lt2 : ";     for (iter = lt2.begin(); iter != lt2.end(); ++iter){         cout << *iter << ' ';     }     cout << endl;     lt1.merge(lt2);    // lt1에 lt2를 오름차순 정렬 순서로 합병한다.     cout << "lt1 merge : ";     for (iter = lt1.begin(); iter != lt1.end(); ++iter){         cout << *iter << ' ';     }     cout << endl;     cout << "lt2  merge : ";     for (iter = lt2.begin(); iter != lt2.end(); ++iter){         cout << *iter << ' ';     }     cout << endl;     return 0; }

결과 : lt1 : 10 20 30 40 50 lt2 : 100 200 300 400 500 ================= lt1 : 10 20 100 200 300 400 500 30 40 50 lt2 : ================= lt1 reverse : 50 40 30 500 400 300 200 100 20 10 ================= lt1 : 50 50 50 40 30 500 400 300 200 100 20 10 10 50 lt1 unique : 50 40 30 500 400 300 200 100 20 10 50 lt1 unique Predicate : 50 40 30 20 10 ================ lt1 sort : 10 20 30 40 50 ================ lt1 : 10 20 30 40 50 lt2 : 10 30 60 99 lt1 merge : 10 10 20 30 30 40 50 60 99 lt2 merge :

- splice() 를 사용하면, 다른 리스트의 원소를 잘라서 붙일 수 있다.

- merge() 와의 차이점은 합병하면서 정렬을 수행한다. 따라서 merge는 lt1과 lt2가 오름차순 정렬되어 있다는 가정하에 동작한다.

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

출처: https://hyeonstorage.tistory.com/326?category=614599 [개발이 하고 싶어요]