지난 시간에 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를 생성
- 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 컨테이너간 크기 비교
- 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 공부를 마친다. 이와같이 시퀸스 컨테이너 포스팅을 계속하여 진행하겠다.
'Programming > Language' 카테고리의 다른 글
| [C++] STL - set 공부 (0) | 2020.05.14 |
|---|---|
| [C++] STL - stack 공부 (0) | 2020.05.11 |
| [C++] STL - vector 공부 (0) | 2020.05.06 |
| [C++] STL(Standard Template Library) 시작 (0) | 2020.05.05 |
| [C++] 템플릿(Template) 공부 (0) | 2020.05.04 |
