(C++)List

리스트는 vector, deque와 같은 시퀀스 컨테이너지만 각 원소가 서로 상대적인 순서를 유지하는게 아닌 노드단위로 연결되있단 점이 가장 큰 차이이다.

List의 노드 연결구조

 

 

 

시퀀스 데이터들을 다룰때 주의해서 쓴다면 큰 효과를 발휘할 수 있는 컨테이너라고 생각된다.

 

vector, deque와 차이점

 

원소접근

list는 []이나 at()같은 임의 접근자를 사용하지 못한다. 배열이 아닌 노드로 연결되어 있기 때문에 반복자 탐색을 통해 원소에 접근해야 한다.  그래서 총 N개의 원소를 가질때 O(N)만큼의 시간이 걸린다.

 

삽입,삭제

삽입하거나 지울때는 연결만 해주거나 끊어주면 되기 때문에 vector, deque와 다르게 상수시간대 밖에 걸리지 않는다.  vector, deque에서 삽입하거나 지울때면 다른 원소들을 움직여야 하는데 그러한 점을 보면 큰 장점이 된다.

또한 vector와 deque에서는 반복자 순회도중 삽입과 삭제가 일어나면 해당 반복자는 해제가 되는데 List는 해제가 되지 않는다.

 

해당 원소 모두 삭제

오직 List만이 remove함수를 지원하는데, 이 함수는 해당 원소를 모두 삭제해준다. 만약 vector나 deque에서 한다면 복잡해질 연산이 List이기에 쉽게 가능해진다. remove_if()에 조건함수 객체를 매개로 해서 특정 조건에 맞는 원소들을 삭제해 줄수도 있다.

 

다른 List 원소 잘라 붙이기

List는 Splice()라는 함수도 지원하는데 다른 List의 원소들을 잘라서 해당 List에 붙여 넣어 주는 역활을 한다.

 

인근 중복원소 제거

unique() 함수는 해당 원소의 근처에 중복되는 원소들을 제거해준다. 만약 List에서 중복원소를 모두 제거할 생각이면 먼저 sorting을 수행한 후 해당 함수를 부르면 된다.

 

정렬

vector,deque는 알고리즘라이브러리의 sort()알고리즘을 사용한다. 하지만 해당 sort()알고리즘은 임의 접근이 가능한 컨테이너만 지원하기에 List는 해당 객체 내에 따로 sort()알고리즘을 가지고 있다. 

 

List의 장점을 보기위해 vector, deque와 비교하여 Insert 시간을 측정해 보았다.

각 컨테이너랑 십만개의 원소가 들어있고 첫번째, 중간, 마지막 자리에 각각 1000개의 원소를 Insert했다.

 

#include<vector>
#include<deque>
#include<list>
#include<time.h>
int main()
{
	vector<int> vec;
	deque<int> deq;
	list<int> lit;
	for (int i=0; i< 100000; i++)
	{
		vec.push_back(i);
		deq.push_back(i);
		lit.push_back(i);
	}
	vector<int>::iterator vecit = vec.begin();
	deque<int>::iterator deqit = deq.begin();
	list<int>::iterator litit = lit.begin();

	for (int i=0;i< 1000;i++)
	{
		litit++;
	}
	clock_t start, end;
	cout << "vector start!" << endl;
	start = clock();
	
	for (int i = 0; i < 100000; i++)
	{
		vec.insert(vec.begin()+(vec.end()-vec.begin()), i);
	}
	end = clock();
	cout << "vector end! : "<<double(end-start)<< endl;

	start = NULL;
	end = NULL;
	cout << "deque start!" << endl;
	start = clock();
	for (int i = 0; i < 100000; i++)
	{
		deq.insert(deq.begin()+(deq.end() -deq.begin()), i);
	}
	end = clock();
	cout << "deque end! : " << double(end - start) << endl;

	start = NULL;
	end = NULL;
	cout << "list start!" << endl;
	start = clock();
	for (int i = 0; i < 10000; i++)
	{
		lit.insert(litit, i);
	}
	end = clock();
	cout << "list end! : " << double(end - start) << endl;

}

 

처음 자리에 insert

 

 

중간 자리에 insert

마지막 자리에 insert

역시나 List는 항상 일정한 시간대를 유지했다. 신기했던건 어느 위치에 삽입하냐에 따라 vector와 deque의 수행시간이 달랐는데, 첫번째 자리에 insert할때는 vector가 가장 느렸다. 모든 원소를 뒤로 미뤄야 하기 때문인것 같다.

마지막 자리에 insert 할때는 deque가 더 느렸다.

 

또한 신기한것이 중간 자리에 insert할때인데, 한번은 처음 +1000번째 자리에서 측정했는데 deque가 말도 안되게 비효율적으로 나왔고 정말 begin과end 사이에 insert할때는 그나마 정상수치로 나왔다.  

 

뭔가 완전 처음이나 끝 또는 완전 중간이 아닌 어중간한 위치에서의 insert는 많은 비용이 소모되는것 같다.

나중에 꼭 다시 한번 파봐야 겠다.