[STL] list 컨테이너

in STL



list 컨테이너의 가장 큰 장점은 특정 위치에 원소를 삽입(insert) 또는 제거(erase)할 때 상수 시간 복잡도를 보인다는 것이다. 그 이유는 list 컨테이너는 노드 기반 컨테이너이기 때문에 특정 위치에 삽입, 제거 할 때 원소들을 밀어내지 않고 노드 끼리 연결만 해주면 되기 때문이다. 아래 코드를 보자. 결과는 배열 기반 컨테이너와 같지만 성능상 이점이 있다.

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

void main() {
	list<int> lt;
	lt.push_back(10);
	lt.push_back(20);
	lt.push_back(30);
	lt.push_back(40);
	lt.push_back(50);
	//lt의 모습 10 20 30 40 50

	list<int>::iterator iter = lt.begin();
	++iter;
	++iter;
	//iter이 가리키는 곳 30

	list<int>::iterator iter2;
	iter2 = lt.erase(iter);
	cout << *iter2 << endl;
	//iter이 가리키는 곳 40
	//lt의 모습 10 20 40 50
	for (iter = lt.begin(); iter != lt.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;
	iter = iter2;
	iter2 = lt.insert(iter, 300);
	//iter2가 가리키는 곳 300
	//lt의 모습 10 20 300 40 50
	cout << *iter2 << endl;
	for (iter = lt.begin(); iter != lt.end(); iter++) {
		cout << *iter << " ";
	}
}

실행 결과

image

딱히 어려운 부분은 없다. 단지 성능에 이점이 있다는 걸 알고 넘어가자.

remove()

list에는 반복자를 이용해 원소를 지우는 erase()말고도 원소의 값을 이용해 원소를 지우는 remove()가 존재한다. remove()는 컨테이너의 모든 원소를 순차적으로 돌아서 해당 원소를 제거한다. 예시를 보자.

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

void main() {
	list<int> lt;
	lt.push_back(10);
	lt.push_back(20);
	lt.push_back(30);
	lt.push_back(10);
	lt.push_back(40);
	lt.push_back(10);
	lt.push_back(50);
	lt.push_back(10);
	//lt의 모습 10	20 30 10 40 10 50 10

	list<int>::iterator iter;
	for (iter = lt.begin(); iter != lt.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;
	cout << endl;
	lt.remove(10); //10 원소의 노드를 모두 제거
	//lt의 모습20 30 40 50
	for (iter = lt.begin(); iter != lt.end(); iter++) {
		cout << *iter << " ";
	}
}

실행 결과

image

이해하는데 어려움은 없을 것이다.

remove_if()

remove_if()는 단항 조건자가 참인 원소를 모두 제거한다. 조건자는 bool형을 반환하는 함수류(함수 객체,함수,함수 포인터)이다. 예시를 보자.

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

bool Predicate(int n) //단항 조건자
{
	return n >= 10 && n <= 30; //n이 10과 30 사이에 있으면 참
}

void main() {
	list<int> lt;
	lt.push_back(10);
	lt.push_back(20);
	lt.push_back(30);
	lt.push_back(40);
	lt.push_back(50);
	lt.push_back(10);
	//lt의 모습 10	20 30 40 50 10

	list<int>::iterator iter;
	for (iter = lt.begin(); iter != lt.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;
	cout << endl;
	lt.remove_if(Predicate); //단항 조건자가 참인 원소를 모두 제거
	//lt의 모습 40 50
	for (iter = lt.begin(); iter != lt.end(); iter++) {
		cout << *iter << " ";
	}
}

실행 결과

image

여기서 주의할 점은 remove_if()는 단항 조건자만 가능하다는 것이다.

splice()

splice()는 list의 특징인 노드 기반이라는 점을 잘 반영하듯 splice()를 제공하는데 이는 다른 list의 순차열을 원하는 list의 순차열에 잘라붙인다. 예시를 보자.

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

void main() {
	list<int> lt;
	lt.push_back(10);
	lt.push_back(20);
	lt.push_back(30);
	lt.push_back(40);
	lt.push_back(50);
	lt.push_back(10);
	//lt의 모습 10	20 30 40 50 10
	
	list<int> lt2;
	lt2.push_back(100);
	lt2.push_back(200);
	lt2.push_back(300);
	lt2.push_back(400);
	lt2.push_back(500);
	//lt2의 모습 100 200 300 400 500

	list<int>::iterator iter = lt.begin();
	cout << "lt 1:";
	for (iter = lt.begin(); iter != lt.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;
	cout << "lt 2:";
	for (iter = lt2.begin(); iter != lt2.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;
	cout << "===========================================" << endl;
	iter = lt.begin();
	++iter;
	++iter;
	//iter이 가리키는 곳 30
	
	lt.splice(iter, lt2); //lt에 iter이 가리키는 위치에 lt2를 잘라서 붙여라
	//lt의 모습 10 20 100 200 300 400 500 30 40 50
	cout << "lt 1:";
	for (iter = lt.begin(); iter != lt.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;
	cout << "lt 2:";
	for (iter = lt2.begin(); iter != lt2.end(); iter++) {
		cout << *iter << " ";
	}
}

실행 결과

image

결과에서 보이는거와 같이 잘라서 붙이기 때문에 lt2는 원소가 없는게 보인다.

이번에는 반복자를 이용해서 반복자가 가리키는 특정 원소만 잘라서 붙이거나 특정 list의 순차열을 잘라서 붙이는 예시를 보이겠다.

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

void main() {
	list<int> lt;
	lt.push_back(10);
	lt.push_back(20);
	lt.push_back(30);
	lt.push_back(40);
	lt.push_back(50);
	lt.push_back(10);
	//lt의 모습 10	20 30 40 50 10
	
	list<int> lt2;
	lt2.push_back(100);
	lt2.push_back(200);
	lt2.push_back(300);
	lt2.push_back(400);
	lt2.push_back(500);
	//lt2의 모습 100 200 300 400 500

	list<int>::iterator iter = lt.begin();
	list<int>::iterator iter2=lt2.begin();
	cout << "lt 1:";
	for (iter = lt.begin(); iter != lt.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;
	cout << "lt 2:";
	for (iter = lt2.begin(); iter != lt2.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;
	cout << "===========================================" << endl;
	iter = lt.begin();
	++iter;
	++iter;
	//iter이 가리키는 곳 30
	++iter2;
	//iter2가 가리키는 곳 200

	lt.splice(iter, lt2,iter2); //lt에 iter이 가리키는 위치에 iter2가 가리키는 lt2의 원소를 잘라붙여라
	//lt의 모습 10 20 200 30 40 50
	cout << "lt 1:";
	for (iter = lt.begin(); iter != lt.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;
	cout << "lt 2:";
	for (iter = lt2.begin(); iter != lt2.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;
	cout << "===========================================" << endl;
	lt.splice(lt.end(), lt2, lt2.begin(), lt2.end()); //lt에 마지막 부분에 lt2의 순차열인 [  lt2.begin() ,  lt2.end() )를 잘라 붙여라
	//lt의 모습 10 20 200 30 40 50 100 300 400 500
	cout << "lt 1:";
	for (iter = lt.begin(); iter != lt.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;
	cout << "lt 2:";
	for (iter = lt2.begin(); iter != lt2.end(); iter++) {
		cout << *iter << " ";
	}
}

실행 결과

image

위와 같이 반복자를 통해서도 가능하고 순차열 자체도 가능하다.

reverse()

reverse()는 list의 순차열을 모두 뒤집는 것이다. 예시를 보자.

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

void main() {
	list<int> lt;
	lt.push_back(10);
	lt.push_back(20);
	lt.push_back(30);
	lt.push_back(40);
	lt.push_back(50);
	//lt의 모습 10	20 30 40 50
	
	lt.reverse();
	//lt의 모습 50 40 30 20 10

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

실행 결과

image

어려운 것은 없다.

unique()

unique()는 좀 조심해서 사용해야 한다. 이유는 이 함수 자체가 원소가 중복되지 않게 해주는건 맞지만 인접한 원소만 확인을 하기 때문에 인접한 원소가 아니라면 원소가 중복되기 때문이다. 예시를 보자.

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

void main() {
	list<int> lt;
	lt.push_back(10);
	lt.push_back(10);
	lt.push_back(20);
	lt.push_back(30);
	lt.push_back(30);
	lt.push_back(30);
	lt.push_back(40);
	lt.push_back(50);
	lt.push_back(10);
	//lt의 모습 10 10	20 30 30 30 40 50 10
	list<int>::iterator iter;
	for (iter = lt.begin(); iter != lt.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;
	lt.unique();
	//lt의 모습 10 	20 30 40 50 10
	for (iter = lt.begin(); iter != lt.end(); iter++) {
		cout << *iter << " ";
	}
}

실행 결과

image

결과가 보여주는 것처럼 10이 중복되는게 확인 된다.

모든 원소가 중복되지 않게 하려면 원소를 정렬하고 unique()를 써야한다. 또한 unique()는 조건자 버전도 있는데 이항 조건자를 인자로 받는다. 이 이항 조건자는 연속된 2개의 원소를 인자로 받는다. 예시를 보자.

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

bool Predicate(int first, int second) {
	return second  <= first; //참이면 second를 제거함
}

void main() {
	list<int> lt;
	lt.push_back(10);
	lt.push_back(10);
	lt.push_back(20);
	lt.push_back(30);
	lt.push_back(30);
	lt.push_back(30);
	lt.push_back(40);
	lt.push_back(50);
	lt.push_back(10);
	//lt의 모습 10 10	20 30 30 30 40 50 10
	list<int>::iterator iter;
	for (iter = lt.begin(); iter != lt.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;
	lt.unique(Predicate);
	//lt의 모습 10 	20 30 40 50 
	for (iter = lt.begin(); iter != lt.end(); iter++) {
		cout << *iter << " ";
	}
}

실행결과

image

결과와 같이 중복되는 원소가 없음을 확인 가능하다.

sort()

원소를 정렬할 수 있는 건 시퀀스 컨테이너뿐이다. 연관 컨테이너는 특정 정렬기준으로 이미 정렬되어 있기 때문이다. 하지만 vector와 deque는 sort() 알고리즘으로 빠르게 정렬 가능하지만, list는 할 수 없다. 이유는 sort() 알고리즘은 임의 접근 반복자를 지원하는 컨테이너만 지원하기 때문이다.그래서 list는 자체적으로 sort() 멤버 함수를 제공한다. 예시를 보자.

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

void main() {
	list<int> lt;
	lt.push_back(20);
	lt.push_back(10);
	lt.push_back(50);
	lt.push_back(30);
	lt.push_back(40);
	//lt의 모습 20 10 50 30 40
	list<int>::iterator iter;
	for (iter = lt.begin(); iter != lt.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;
	lt.sort(); //오름차순(less) 정렬
	//lt의 모습 10 	20 30 40 50 
	for (iter = lt.begin(); iter != lt.end(); iter++) {
		cout << *iter << " ";
	}
}

실행 결과

image

sort()의 정렬 조건을 바꾸려면 조건자 버전 sort()를 사용하면 된다. sort()는 이항 조건자를 사용하며 이항 조건자가 참이면 두 원소를 바꾸지 않고 거짓이면 두 원소를 바꿔가면서 정렬한다. 예시를 보자.

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

class Greater {
public:
	bool operator()(int left, int right) const {
		return left > right;
	}
};

void main() {
	list<int> lt;
	lt.push_back(20);
	lt.push_back(10);
	lt.push_back(50);
	lt.push_back(30);
	lt.push_back(40);
	//lt의 모습 20 10 50 30 40
	list<int>::iterator iter;
	for (iter = lt.begin(); iter != lt.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;

	lt.sort(greater<int>()); //STL에서 제공하는 greater<int>()로 내림차순 정렬
	//lt의 모습 50 40 30 20 10
	for (iter = lt.begin(); iter != lt.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;

	lt.sort(less<int>());  //STL에서 제공하는 less<int>()로 오름차순 정렬
	//lt의 모습 10 	20 30 40 50 
	for (iter = lt.begin(); iter != lt.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;

	lt.sort(Greater()); //사용자 저의 조건자 Greater()로 내림차순 정렬
	//lt의 모습 50 40 30 20 10
	for (iter = lt.begin(); iter != lt.end(); iter++) {
		cout << *iter << " ";
	}
}

실행 결과

image

위에서 사용자 저의 조건자도 사용하고 STL내부에서 제공하는 조건자도 사용하였는데 STL내부에서 제공하는 조건자를 쓰는게 더 편해 보인다. 원래 greater,less 조건자는 funtional헤더에 들어있지만 일반적으로 list헤더에도 들어있어서 include를 생략하였다.

merge()

만약 2개의 list를 합병해야 한다면 merge()를 사용한다. 여기서 주의 할 점은 합병은 정렬된 두 list를 하나의 list로 합병하기 때문에 합병할 두 list는 정렬되어 있어야 한다. merge()는 splice()와 비교하여 알아두면 좋다.

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

void 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);
	//lt1의 모습 10 20 30 40 50

	lt2.push_back(25);
	lt2.push_back(35);
	lt2.push_back(60);
	//lt2의 모습 25 35 60

	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;
	cout << "==========================================" << endl;
	lt1.merge(lt2);
	//lt1의 모습 10 20 25 30 35 40 50 60

	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 << " ";
	}
}

실행 결과

image

lt2는 합병되어 사라진다. 위에서 합병이 가능한 이유는 lt1과 lt2 모두 오름차순으로 정렬 되어 있기 때문이다. 만약 내림차순으로 정렬되어 있는 두 list를 합병한다면 merge()에 조건자를 추가해서 어떤 기준으로 정렬 되어 있는지 알려줘야한다. 예시를 보자.

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

void main() {
	list<int> lt1;
	list<int> lt2;

	lt1.push_back(50);
	lt1.push_back(40);
	lt1.push_back(30);
	lt1.push_back(20);
	lt1.push_back(10);
	//lt1의 모습 50 40 30 20 10

	lt2.push_back(60);
	lt2.push_back(35);
	lt2.push_back(25);
	//lt2의 모습 60 35 25

	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;
	cout << "==========================================" << endl;
	lt1.merge(lt2,greater<int>()); //greater조건자를 넘겨줘서 알려줘야함
	//lt1의 모습 60 50 40 35 30 25 20 10

	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 << " ";
	}
}

실행 결과

image

위와 같이 두 list가 내림차순으로 정렬 되어 있으면 merge()에 조건자를 넘겨줘서 어떤 기준으로 정렬 되어 있는지 꼭 알려줘야 한다. 만일 두 list가 정렬 조건이 다른 상태로 합병하면 오류가 발생하고 아예 정렬조차 되어 있지 않아도 오류가 발생한다.


© 2022. by KSC

Powered by sora