[C++] STL - list 공부

지난 시간에 STL의 vector에 대해 알아보았다.

이번시간은 STL 시퀸스 컨테이너 중 이중연결리스트구조인 list에 대해 공부해보려한다.

---

1. list란?

list는 시퀸스 컨테이너 중 하나로 노드 기반 컨테이너이다.

구조는 doubly linked list 구조로 말그대로 이중 연결 리스트이다.

 

list는 vector, deque와 달리 노드 기반으로 서로 연결이 되어있어서 원소를 삽입하거나 삭제하고자할 때 모든 원소를 밀어내지 않기때문에 상수 시간복잡도를 갖아 속도가 빠르다.

또, 삽입과 삭제시 반복자가 가리키고있는 원소 자체를 삭제해야 원소가 사라지며, 동작자체에서 반복자를 무효화시키지 않는다.

 

이외에도 sort(), splice(), merge() 함수 등 list 정렬, 결합 혹은 사용시 유용한 멤버 함수들을 많이 제공한다.

 

list를 사용하기 위해선 <list> 헤더파일을 include 해주어야하며,

std::list<[데이터타입]> [변수이름] 형식으로 선언해 사용할 수 있다.

(using namespace std;로 std 생략하여 편하게 작성가능)

2. list - 생성자

list 생성자는 다음과 같이 사용 가능하다. 아래부터 데이터타입이 int라고 가정하고 작성하겠다.

• list<int>lst;
  • 빈 list 컨테이너 lst을 생성
• list<int>lst(3);
  • 3개의 원소를 갖는 lst을 생성(기본값 초기화)
• list<int> lst(3, 4);
  • 4로 초기화된 3개의 원소를 갖는 lst을 생성
• list<int> lst2(lst);
  • lst 컨테이너를 복사한 lst2를 생성
    
    
    

3. list - 멤버 함수, 멤버 형식

다음은 lst 멤버 함수와 멤버 형식이다. 이번 역시 대표적인 몇몇개를 정리해보았다.

 

- 멤버 함수

• lst.assign(2, 3);
  • lst에서 3이란 값으로 2개의 원소를 할당
• lst.front();
  • lst의 첫번째 원소를 참조
• lst.back();
  
  • lst의 마지막 원소를 참조
• lst.clear();
  • lst의 모든 원소를 제거하며 메모리는 그대로 내비둠
• lst.push_front(3);
  • lst 앞에 3 원소를 push
• lst.push_back(5);
  • lst 끝에 5란 원소를 push
• lst.pop_front();
  • lst 첫번째 원소를 pop
• lst.pop_back();
  • lst 마지막 원소를 pop
• lst.insert(iterator, 4); lst.insert(iterator, 4, 2);
  • lst의 iterator이 가리키는 위치에 4란 값 삽입
  • lst의 iterator이 가리키는 위치에 4개의 2란 값 삽입
• lst.erase(iterator)
  • iterator가 가리키고 있는 원소를 제거, 다음 원소 가리킴(반환)
• lst.clear();
  • lst의 모든 원소를 제거
• lst.begin();
  • lst의 첫번째 원소를 가리킴
  • iterator와 같이 사용
• lst.end();
  • lst의 끝을 가리킴
  • iterator와 같이 사용
• lst.size();
  • lst의 원소 갯수 참조
• lst.empty();
  • lst의 size가 0이면 참, 0보다 크면 거짓
• lst.swap(lst2);
  • lst1와 lst2의 원소와 할당된 메모리를 맞바꿈
• lst.merge(lst2), lst.merge(lst2,predicate);
  • lst2를 lst로 합병하여 정렬
  • lst2를 조건자를 통해 lst로 합병하여 정렬
• lst.remove(3), lst.remove_if(predicate);
  • 3 원소를 모두 제거
  • 단항 조건자가 참인 모든 원소를 제거
• lst.sort(), lst.sort(predicate);
  • lst의 모든 원소를 오름차순 정렬
  • lst의 모든 원소를 조건자 기준으로 정렬
• lst.splice(iterator, lst2);
  • iterator가 가르키는 곳에 lst2 모든 원소를 잘라 넣는다.
• lst.unique(), lst.unique(pred);
  • 입접한 원소의 값이 같다면 유일한 원소 순차열로 만듦
  • 인접한 원소가 이항 조건자 기준에 맞으면 유일한 원소 순차열로 만듦

 

- 멤버 형식

• allocator_type
  • 메모리 관리자
• iterator
  • 반복자
• pointer
  • value_type *
• refernce
  • value_type &
• reverse_iterator
  • 역 반복자
• size_type
  • 인덱스, 원소 갯수 등
• value_type
  • 원소 형식
    
    
    

4. list - 연산자

list의 연산자이다.

• ==, != 
  • == : 두 list 컨테이너의 모든 원소가 같으면 참, 아니면 거짓
  • != : 두 list 컨테이너에서 하나라도 원소가 다르면 참, 아니면 거짓
• <, >, <=, >=
  
  • list 컨테이너간 크기 비교
    
    
    

5. list 구조 및 실습

위에서 설명한 list의 구조는 다음 그림과 같다.

실습을 진행해보았다. list 컨테이너를 이용해 원소를 추가, 삭제해보고 다양한 멤버 함수를 사용해보았다.

 

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

int main(void) {
	list<int> lst; //빈 list 컨테이너 lst 생성
	list<int>::iterator lstit; //연산자 선언
	lst.push_back(30); //lst 뒤에 30 push > 30
	lst.push_back(20); //lst 뒤에 20 push > 30, 20
	lst.push_back(40); //lst 뒤에 40 push > 30, 20, 40
	lst.push_front(10); //lst 앞에 10 push > 10, 30, 20, 40
	cout << "lst > push_front, push_back" << endl;
	for (lstit = lst.begin(); lstit != lst.end(); lstit++) { //lst begin부터 end까지 출력
		cout << *lstit << endl; 
	}
	cout << "lst > pop_front, pop_back" << endl;
	lst.pop_back(); //lst 맨뒤 원소 pop
	lst.pop_front(); //lst 첫번째 원소 pop
	for (lstit = lst.begin(); lstit != lst.end(); lstit++) {
		cout << *lstit << endl;
	}
	cout << "lst2 > lst복사하여 컨테이너 생성" << endl;
	list<int> lst2(lst); //lst복사하여 lst2 컨테이너 생성
	for (lstit = lst2.begin(); lstit != lst2.end(); lstit++) {
		cout << *lstit << endl;
	}
	cout << "lst2 > sort 정렬" << endl;
	lst2.sort(); //lst2 오름차순 정렬
	for (lstit = lst2.begin(); lstit != lst2.end(); lstit++) {
		cout << *lstit << endl;
	}
	cout << "lst2 > iterator가 가리키고있는 위치에 lst 값 잘라붙여넣기" << endl;
	lst2.splice(lstit, lst); //lterator 가리키는 위치에 lst 값 잘라붙여넣기
	for (lstit = lst2.begin(); lstit != lst2.end(); lstit++) {
		cout << *lstit << endl;
	}
	return 0;
}

실행결과는 다음과 같다.

---

여기까지 list 공부를 마친다. 이와같이 시퀸스 컨테이너 포스팅을 계속하여 진행하겠다.