[C++] vector vs list

vector는 무작위 요소에 빠르게 접근하는 것에 최적화되어 있고

list는 컨테이너에 요소를 빠르게 삭제하고 삽입하는 것에 최적화되어 있다.

 

데이터의 삽입과 삭제가 끝에서만 이루어진다면, 요소의 순서가 바뀌지 않기 때문에 vector가 list보다 더 빠르다.

하지만 삽입과 삭제가 중간에서 이루어진다면 list가 빠르다.

그리고 데이터 입력이 커질수록 list가 vector보다 빠르다.

 

vector는 index를 지원하는데 비해 list는 그렇지 않다.

 

// version 4: use list instead of vector
list<Student_info> extract_fails(list<Student_info>& students)
{
 list<Student_info> fail;
 list<Student_info>::iterator iter = students.begin();
 while (iter != students.end()) {
 if (fgrade(*iter)) {
 fail.push_back(*iter);
 iter = students.erase(iter);
 } else
 ++iter;
 }
return fail;
}

 

list도 vector와 동일하게 iterator을 이용할 수 있다.

 

vector에서 삭제할 때는 삭제된 요소와 그 후속 요소를 참조하는 iterator가 모두 무효화된다.

삽입할 때는 해당 벡터를 참조하는 모든 iterator가 무효화된다.

하지만 list에서 삭제나 삽입이 일어날 때 경우에는, 요소를 삭제할 때 삭제된 그 요소를 참조하는 iterator만 무효화된다.

 

vector<Student_info> students;
sort(students.begin(),students.end(), compare);

list<Student_info> students;
students.sort(compare);

 

list는 랜덤 액세스를 지원하지 않기 때문에 vector와 달리 sort를 이용할 수 없다.

그래서 list 클래스가 제공하는 고유의 sort 함수를 이용한다.

compare은 vector이 사용하는 것과 동일하게 사용할 수 있다.