C++ STL_Sequence Container - list, forward_list

List

#include <list>
list<type> l

list는 양방향 linked_list
head <-> node1 <-> node2 <-> tail

node의 주소가 제각각이기 때문에 첨자 연산자를 사용할 시 시간복잡도가 높아져 허용하지 않는다.
std::advance(<iterator>, <index>)를 이용해 접근이 가능하며
list.remove(<index>)를 이용해 데이터를 지울 수 있다.

예제

list<int> list0{1, 2, 3};
// list0[2];
list<int>::iterator iter = list0.begin();
std::advance(iter, 2);

cout << *iter << endl;

for (int num : list0)
	cout << num << ' ';
cout << endl;

list0.remove(2);

for (int num : list0)
	cout << num << ' ';

실행 결과

1 2 3
1 3

list.sort(), list.merge(), list.unique()

list.sort()
algorithm의 sort는 random access가 가능한 배열만 사용할 수 있으며 list에 사용할 시에 시간복잡도가 높아져 허용되지 않는다.

대신 list에는 고유의 sort 함수가 있다.

list.merge(<list>)
두 리스트를 합칠 수 있다.
단, 두 리스트는 정렬되어 있어야한다.

list.unique()
중복 원소 제거

예제

std::list<int> list0{ 4, 1, 2, 3 };
list0.sort();

for (int n : list0)
	cout << n << ' ';
cout << endl;
list<int> list1{ 1, 2, 3, 4 };

list0.merge(list1);	// 두 list가 정령되어 있어야 한다.
for (int n : list0)
	cout << n << ' ';
cout << endl;

list0.unique();	// 중복 제거
for (int n : list0)
	cout << n << ' ';
cout << endl;

실행 결과

1 2 3 4
1 1 2 2 3 3 4 4
1 2 3 4

list.remove(), list.remove_if()

list.remove(<number>)
번호의 자리에 있는 데이터를 삭제한다.

여기서 주의할 점은
[0, 1, 2, 3] 의 리스트에서
list.remove(2)를 할시에
1이 삭제된다.

즉 index가 아닌 순서로 어떤 데이터를 삭제할지 판단한다.

list.remove_if(<function>)
function의 조건식에 따라 list의 데이터를 삭제한다.

예제

	std::list<int> list0{ 1, 2, 3, 4 };

	list0.remove(3);

	for (int n : list0)
		cout << n << ' ';
	cout << endl;

	list0.remove_if(condition);

	for (int n : list0)
		cout << n << ' ';

실행 결과
1 2 4
1

forward_list

#include <forward_list>
std::forward_list<int> flist

node가 자신을 가리키지 못하는 노드를 알지 못한다.

node1 -> node2 -> node3
위 구조에서 node2는 node1의 주소를 알지 못한다.

flist.insert_after(<iterator>, <data>)
iterator가 가리키는 값의 뒤에 data가 삽입된다.

예제

list<int> list0{ 1, 2, 3 };

list0.insert(list0.begin(), 10);

std::forward_list<int> flist0{ 1, 2, 3 };

flist0.insert_after(flist0.begin(), 10);

for (int n : list0)
	cout << n << ' ';
cout << endl;

for (int n : flist0)
	cout << n << ' ';
cout << endl;

실행 결과

10 1 2 3
1 10 2 3