C++(STL Container) list

list

-> 노드를 기반으로 하는 컨테이너 이다.

-> 더블 링크드 리스트로 구현되어 있다.

-> 앞, 뒤 노드의 삽입 및 삭제가 가능하다.

각 노드는 연속적인 메모리를 사용하는 것이 아니고,

비 연속적인 메모리에 여기저기 저장되지만 포인터로 각 노드를 연결하여

마치 연속된 메모리를 사용하는 것처럼 보인다.

-> 임의 접근이 불가능

-> 탐색하고자하는 원소가 나올 때까지 모든 노드를 순회해야함

-> 선형 시간 O(n)

삽입 삭제 시에는 단순 포인터의 해제 및 연결만 하기 때문에

메모리를 밀고 당길 필요가 없어 빠르다.(상수 시간 O(1))

메모리의 재할당 및 복사가 필요 없기 때문에 런타임 시에도 삽입 삭제가 용이하다.

 

list의 선언

list<int> listInt;

list의 원소 삽입

listInt.push_back(3);
listInt.push_back(4);
listInt.push_back(5);
listInt.push_front(1);
listInt.push_front(2);

list는 앞에서도 원소를 삽입할 수 있기에 push_front 함수를 지원한다.

 

여기서 원소를 출력해야하는데 list는 배열 기반 컨테이너가 아니므로 인덱스접근이 불가능하다.

list의 모든 원소를 순회하기 위해서는 반복자를 활용해야한다.

list<int>::iterator iter = listInt.begin();

for(; iter != listInt.end(); ++iter)
{
   cout << *iter << endl;
}

그런데 반복자가 아닌 list의 원소를 확인할 수 있는 방법이 있다.

그것은 '범위기반 for문' 과 'auto'이다.

 

auto

-> 자료형이다.

-> 대입 받는 데이터의 타입으로 자동 설정된다.

-> 단, 선언과 동시에 초기화를 진행해야만 한다.

auto a = 10    // int형
auto b = 3.14  // double형
auto c = 3.14f // float형


list<int>::iterator	iter = listInt.begin();
auto		        	iter = listInt.begin();

 

범위기반 for문

-> 배열 또는 컨테이너의 모든 원소를 순회할 때 사용한다.

-> 단, 범위 기반 for문을 사용 중 원소의 개수가 바뀌게 되면 오류가 발생한다.

-> 그러므로 단순 순회 용도로만 사용한다.

 

 

list의 원소 삭제

listInt.pop_back();
listInt.pop_front();

for(auto iNum : listInt)
{
  cout << iNum << endl;
}

 

list의 멤버함수

size(), empty(), clear(), front(), back(), begin(), end(), swap() 등

-> 메모리와 관련된 함수를 제외하고는 vector와 동일하다.

 

list의 반복자

-> 임의 접근이 불가능하기 때문에 임의 접근 반복자를 사용하지 않고,

-> 양 방향 접근 반복자를 사용한다.

list<int> listInt;

auto iter = listInt.begin();

++iter;

 

list의 중간 삽입

auto iter_begin = listInt.begin();
auto iter_end   = listInt.end();

++iter_begin;
++iter_begin;

listInt.insert(iter_begin, 999);

list는 vector와 달리 메모리를 밀고 당길 필요가 없다.

단순 빈 공간에 원소를 삽입 후 포인터 연결만 해제 및 재연결하면 되기 때문에

반복자(begin 과 end)의 위치가 변경되지 않아 무효화가 발생하지 않는다.

 

list의 중간 삭제

auto iter_begin = listInt.begin();
auto iter_end   = listInt.end();

++iter_begin;
++iter_begin;

iter_begin = listInt.erase(iter_begin);

 

list의 정렬

-> list는 멤버 함수로 sort를 지원한다.

template <typename T>
bool Less(T _Left, T _Right)
{
	return _Left < _Right;
}

void main()
{
   list<int> listInt;
   
   listInt.push_back(5);
   listInt.push_back(4);
   listInt.push_back(1);
   listInt.push_back(3);
   listInt.push_back(2);

   listInt.sort();
   listInt.sort(Less<int>);
   listInt.sort(less<int>());
   
   for(auto iNum : listInt)
   {
     cout << iNum << endl;
   }
}

list의 멤버 함수 sort는 아무런 조건도 명시하지 않을 경우 기본 오름차순 정렬이 발생한다.

하지만 functional 또는 템플릿 함수를 만들어서 사용해도 무방하다.

 

list의 멤버 함수안에 있는 sort와 reverse를 함께 사용하면 기본 오름차순에서 내림차순 정렬로 바꿀 수 있다.

listInt.sort();
listInt.reverse();