C++ 자료구조 STL 개념 : list

vector, list, set, map, pair, algorithm 헤더, cmath헤더, cctype헤더

 

저번 포스트에서 C++ STL가 무엇이고, 어떤 것들로 이루어지는 것인지 알아보았다.

오늘은 그중 시퀀스 컨테이너에 속하는 deque 에 대해서 알아보자.

 

시퀀스 컨테이너 : 데이터를 선형적으로 저장하고 삽입된 요소의 순서가 그대로 유지된다.

1. vector

2. deque

3. list

 

list

특징

• 더블 링크드 리스트, 노드 기반 컨테이너 구조이다.
• 장점
  포인터로 다음 값을 찾아주는 방식이므로 모든 삽입 삭제가 용이하다.
• 단점
  vector에서 가능했던 데이터의 위치로 값에 접근을 할 수 없다(순차접근만 가능)

용법

1. 선언/초기화 방법

#include <list>

list<type> lt;         // 비어 있는 list 컨테이너 lt를 생성
list<type> lt(10);     // default(0)값으로 초기화 된 원소 10개를 가진 list를 생성
list<type> lt(3, 2);   // 2값으로 초기화된 원소3개를 가진 list를 생성
list<type> lt2(lt1);   // list lt1을 lt2로 복사


연산자 사용가능
==, !=, < , > , <= , >=

 

2. 처음,중간,끝 삽입/삭제

lt.assign(3, 4);     // 4로 초기화된 3개의 원소를 할당
lt.front();          // 맨 앞 원소를 반환, 참조
lt.back();           // 맨 뒤 원소를 반환, 참조

lt.push_back(k);     // 맨 뒤 원소 삽입
lt.push_front(k);    // 맨 앞 원소 삽입

lt.pop_back();       // 맨 뒤 원소 제거
lt.pop_front();      // 맨 앞 원소 제거

iter = lt.insert(iter, k);   // iter가 가리키는 위치에 원소 k 삽입, 삽입한 원소를 가리키는 iterator를 반환
iter = lt.erase(iter);       // iter가 가리키는 원소를 삭제, 삭제한 원소의 다음 원소를 가리키는 iterator를 반환

lt.remove(k);      // k와 같은 원소를 모두 제거
lt.remove_if(Predicate); // 단 조건자 predicate가 참이면 해당하는 원소를 제거

 

3. 리스트 크기

lt.size();

 

4. iterator

list컨테이너는 at, []가 없다. 즉, 반복자가 ++, — 하는 방식으로만 원소 접근 가능

list<int>::iterator iter;
iter = lt.begin();     // 맨 앞 원소를 가리키는 iterator를 반환
iter = lt.end();       // 맨 마지막의 다음 원소를 가리키는 iterator 반환?

iter = lt.rbegin();     // 뒤에서부터 원소를 순차적으로 접근할 때 편리,begin()과 동일
iter = lt.rend();       // 뒤에서부터 원소를 순차적으로 접근할 때 편리, end()와 동일

 

5. 정렬방법

lt.reverse();    // 원소들의 순차열을 뒤집는다
lt.sort();       // 모든 원소를 default(오름차순)으로 정렬한다
lt.sort(greater<string>());   // 내림차순 정

lt2.swap(lt1);   // lt2와 lt1을 swap한다(바꾼다)

 

6. 이어붙이기

// lt2에서 iter2가 가리키는 곳에 lt1의 모든 원소를 잘라 붙인다
lt2.splice(iter2, lt1); 

// lt2의 iter2가 가리키는 곳에 lt1의 iter1이 가리키는 원소를 잘라 붙인다
lt2.splice(iter2, lt1, iter1);   

// lt2의 iter2가 가리키는 곳에 lt1의 [iter1_1, iter1_2)까지의 원소를 잘라 붙인다
lt2.splice(iter2, lt1, iter1_1, iter1_2);   

[start, end)
start 보다는 크거나 같고,
end 보다는 작은 원소를 뜻한다.

// lt1을 lt2 내부로 합병 정렬한다. 기준은 default 오름차순
// 두번째 파라미터로 이항 조건자가 오면, 그 기준으로 정렬
// 제대로 동작하기 위해서는 병합할 두 리스트가 이미 정렬이 되어 있어야 한다.
lt2.merge(lt1);

 

7. 멤버함수

lt.unigue();   // 인접한(양 옆의)원소가 같으면 유일하게 만든다(하나만 빼고 삭제)

 

 

 

레퍼런스

[C++] list container 정리 및 사용법 (tistory.com)