[C++STL] 시퀀스 컨테이너 - list

list는 노드 기반 컨테이너이므로 원소가 각각의 노드에 저장된다. 각 노드는 앞쪽, 뒤쪽 노드와 연결된 형태로 이중 연결 리스트이다. list는 push_back, push_front, pop_back, pop_front, insert, erase 등의 멤버 함수를 갖는다. 또한 노드 기반 컨테이너로 at(), [] 연산자가 없으며 임의 접근 반복자가 아닌 양방향 반복자를 제공한다. 아래 예제는 list의 원소 추가와 반복자를 보인 예제이다.

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

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;
	lt.push_front(100);
	lt.push_front(200);
	for (iter = lt.begin(); iter != lt.end(); ++iter)
	{
		cout << *iter << " ";
	}
	cout << endl;
	return 0;
}

list는 원소를 앞쪽, 뒤쪽에 모두 추가할 수 있으며 양방향 반복자를 제공하므로 ++ 연산과 *연산 != 연산으로 list의 모든 원소를 출력할 수 있다. list의 가장 큰 특징 중 하나는 순차열 중간에 원소를 삽입(insert()), 제거(remove())하더라도 성능이 저하되지 않는다. vector나 deque는 기존 원소들을 미뤄내고 다시 복사를 해야하는 중간에 insert나 erase를 사용 하면 성능이 크게 저하되지만 list는 노드를 서로 연결하기만 하면 되기 때문에 성능 저하를 걱정할 필요가 없다. vector와 list의 insert, erase 함수는 내부적으로는 차이가있지만 기능적으로는 차이가 없기 때문에 예제는 스킵하겠다. 조건자를 이용해 원소를 제거할 수 있는데 remove_if() 멤버 함수는 단항 조건자가 참인 모든 원소를 제거한다. 아래는 remove_if() 멤버 함수의 예제이다.

#include <iostream>
#include <list>
using namespace std;
bool	predicate(int n) 
{
	return (10 <= n && 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;
	lt.remove_if(predicate);
	for (iter = lt.begin(); iter != lt.end(); ++iter)
	{
		cout << *iter << " ";
	}
	cout << endl;
	return 0;
}

remove_if 이후 출력해보면 10,20,30은 제거되고 40,50만 출력되는 것을 확인할 수 있다.

순서가 있는 노드 기반 컨테이너 list는 이런 특징을 잘 반영하듯 splice()라는 멤버 함수를 가진다. splice()는 다른 list 컨데이너의 순차열을 잘라붙일 수 있다. 아래는 splice()의 예제이다.

#include <iostream>
#include <list>
using namespace std;
bool	predicate(int n) 
{
	return (10 <= n && 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> lt2;
	lt2.push_back(100);
	lt2.push_back(200);
	lt2.push_back(300);
	lt2.push_back(400);
	lt2.push_back(500);

	list<int>::iterator iter;
	iter = lt.begin();
	iter++;
	iter++;
	lt.splice(iter, lt2);
	for (iter = lt.begin(); iter != lt.end(); ++iter)
	{
		cout << *iter << " ";
	}
	cout << endl;
	for (iter = lt2.begin(); iter != lt2.end(); ++iter)
	{
		cout << *iter << " ";
	}
	cout << endl;

	return 0;
}

lt.splice(iter, lt2)는 lt2의 모든 원소를 iter가 가리키는 lt1에 잘라붙인다. 출력 결과는 10 20 100 200 300 400 500 30 40 50 이렇게 출력된다. lt1.splice(iter1, lt2, iter2)와 같이 쓸수도 있는데 iter1이 가리키는 위치에 iter2가 가리키는 위치의 lt2의 원소를 잘라 붙인다는 뜻이다.

• reverse()는 list의 순서를 뒤집는다. 만약 10, 20, 30, 40, 50 순으로 원소가 나열되어있는 객체를 lt.reverse() 멤버 함수를 실행하면 50, 40, 30, 20, 10으로 순서가 뒤집어진다.

• unique는 원소 중복을 방지한다. 만약 10, 10, 20, 20, 30, 30, 40, 40, 50, 50 이렇게 중복되는 원소를 가진 list 객체 lt가 있다면 lt.unique() 멤버 함수를 호출해서 중복되는 원소를 제거하고 10, 20, 30, 40, 50 이렇게 출력된다. 다만 인접해있는 중복되는 원소를 제거된다.

• sort() vector나 deque는 sort() 알고리즘을 사용하여 빠르게 정렬할 수 있지만 list는 sort() 알고리즘을 수행할 수 없다. sort 알고리즘은 임의 접근 반복자를 지원하는 컨테이너만 사용할 수 있기 때문인데 따라서 list는 자체 정렬 멤버 함수 sort()를 제공하고 list 객체 lt가 있다면 lt.sort() 이렇게 멤버 함수를 호출해서 정렬할 수 있다. 디폴트는 오름차순으로 정렬이 된다. lt.sort(greater< int >())는 내림차순, lt.sort(less< int >())는 오름차순 lt.sort(사용자 정의 함수)는 사용자 정의 함수로 정렬할 수 있다.