[C++] STL list(리스트), 시퀀스 컨테이너

리스트는 대충 위그림 처럼 생겼다. 각 요소들은 앞 뒤 노드를 가지고 있어서 이중 연결 리스트로 구현된다. 리스트는 랜덤 액세스가 불가능하다. 즉, 중간에 3번째에 자료에 접근하려면 처음부터 두번째, 세번째 이런식으로 거쳐가야한다.

반면에 장점은 어떠한 위치의 자료를 삭제, 삽입 하더라도 그 속도가 빠르다는 것이다. 배열 구조와는 달리 연결된 링크만 끊어내고 다시 이어붙이는 작업만 하면 되기 때문이다.

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

int main()
{
  list<char> alpha_list;

  for(char c = 'a'; c <= 'z'; c++)
  {
     alpha_list.push_back(c);
  }

  while( !alpha_list.empty() ){
     cout << alpha_list.front() << " ";
     alpha_list.pop_front();
  }
  cout << endl;

  return 0;
}

결과값)

a b c d e f g h i j k l m p q r t u v w x y z

시퀀스 컨테이너들의 멤버 함수들은 대부분 비슷한 형태이다. 그래서 실제로 벡터나 데큐를 사용하는데 문제가 없으면

리스트도 크게 다를게 없어 어려움이 많지는 않을 것이다.

​

iterator 를 활용

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

int main()
{
  list<char> alpha_list;

  for(char c = 'a'; c <= 'z'; c++)
  {
     alpha_list.push_back(c);
  }

  list<char>::iterator it;
  for(it = alpha_list.begin(); it != alpha_list.end(); it++) {
     if(*it == 'n') it = alpha_list.erase(it);
     if(*it == 'o') it = alpha_list.erase(it);
     if(*it == 's') it = alpha_list.erase(it);
  }
  for(it = alpha_list.begin(); it != alpha_list.end(); it++) {
     cout << *it << " ";
  }
  cout << endl;

  return 0;
}

결과값)
a b c d e f g h i j k l m p q r t u v w x y z

리스트는 벡터, 데큐와 달리 여러 리스트만의 효율적인 멤버 함수를 제공한다. insert나 erase는 배열 기반보다 효율적으로 동작한다. 또한, 값의 비교로 원소를 제거하는 remove, remove_if를 제공하고, 각종 sorting 함수들까지도 지원한다.

list.assign(n, x) list.assign(begin_iter, end_iter)	목록에서 요소를 삭제하고 대상 목록에 요소의 새 집합을 복사.
list.back()	목록의 마지막 요소에 대한 참조를 반환.
it = list.begin()	목록에서 첫 번째 요소의 주소를 지정하는 반복자를 반환.
list.clear()	목록의 모든 요소를 지운다.
list.emplace(iter_index, x)	생성된 요소 x를 목록의 지정된 위치에 삽입.
list.emplace_back(x)	생성된 요소 x를 목록 끝부분에 추가.
list.emplace_front(x)	생성된 요소 x를 목록 시작 부분에 추가.
list.empty()	목록이 비어 있는지 여부를 테스트.
it = list.end()	목록에서 마지막 요소 다음에 나오는 위치의 주소를 지정하는 반복자를 반환.
it = list.erase(iter) it = list.erase(iter_begin, iter_end)	목록의 지정된 위치에서 요소 또는 요소 범위를 제거.
list.front()	목록의 첫 번째 요소에 대한 참조를 반환.
list.insert(iter, x) list.insert(iter, iter_begin, iter_end)	요소 하나 또는 여러 개나 요소의 범위를 목록의 지정된 위치에 삽입.
size = list.max_size()	목록의 최대 길이를 반환.
list.merge(list2) list.merge(list2, traits)	list2를 list로 합병정렬 한다. traits는 특정 조건 지정이 가능.
list.pop_back()	목록의 끝에 있는 요소를 삭제.
list.pop_front()	목록의 시작 부분에 있는 요소를 삭제.
list.push_back(x)	목록의 끝에 요소를 추가.
list.push_front(x)	목록의 시작 부분에 요소를 추가.
list.remove(x)	목록에서 지정된 값과 일치하는 요소를 지운다.
list.remove_if(predicate)	지정된 조건자를 충족하는 요소를 목록에서 지운다.
list.resize(n)	목록의 새 크기를 지정.
list.reverse()	목록에 요소가 나타나는 순서를 반대로 바꾼다.
list.size()	목록에 있는 요소 수를 반환.
list.sort() list.sort(predicate)	오름차순 또는 기타 순서 관계를 기준으로 목록의 요소를 정렬.
list.splice(iter, list2) list.splice(iter, list2, iter2) list.splice(iter, list2, iter2_begin, iter2_end)	iter에 list2의 모든 원소를 붙인다. iter에 list2의 iter2 위치의 원소를 잘라 붙인다. iter에 list2의 요소 범위를 잘라 붙인다.
list.swap(list2)	두 목록의 요소를 교환.
list.unique() list.unique(predicate)	목록에서 인접하는 중복 요소 또는 기타 이진 조건자를 충족하는 인접 요소를 제거.

#include<iostream>
#include<list>
using namespace std;
bool predicate(char c)
{
    return (c != 'k' && c != 'o' && c != 'r' && c != 'e' && c != 'a');
}

bool predicate2(char c)
{
   return (c == 'k' || c == 'o' || c == 'r' || c == 'e' || c == 'a');
}

int main()
{
  list<char> alpha_list;

  for(char c = 'a'; c <= 'z'; c++)
  {
     alpha_list.push_back(c);
  }
  
  list<char>::iterator it;
  alpha_list.remove_if(predicate);

  cout << "남은 리스트 내용" << endl;
  for(it = alpha_list.begin(); it != alpha_list.end(); it++) {
     cout << *it << " ";
  }
  cout << endl;

  list<char> alpha_list2;
  cout << "리스트 추가" << endl;
  for(char c = 'a'; c <= 'z'; c++)
  {
     alpha_list2.push_back(c);
  }

  list<char>::iterator it2;
  alpha_list2.remove_if(predicate2);
  
  cout << "남은 리스트 내용" << endl;
  for(it2 = alpha_list2.begin(); it2 != alpha_list2.end(); it2++) {
     cout << *it2 << " ";
  }
  cout << endl;

  alpha_list.merge(alpha_list2);

  cout << "리스트1 내용" << endl;
  for(it = alpha_list.begin(); it != alpha_list.end(); it++) {
     cout << *it << " ";
  }
  cout << endl;

  return 0;
}

결과값)
남은 리스트1 내용
a e k o r 
리스트2 추가
남은 리스트2 내용
b c d f g h i j l m n p q s t u v w x y z 
리스트1 내용
a b c d e f g h i j k l m n o p q r s t u v w x y z

C++, STL list(리스트), 시퀀스 컨테이너 : 네이버 블로그 (naver.com)