728x90
향상된 이중 연결 리스트 클래스
∙ DoublyLinkedList 클래스에 추가할 기능
- 반복자(iterator) 지원
- 데이터 검색 기능
- 범용 데이터 저장을 위한 클래스 템플릿 작성
∙ DoublyLinkedList 클래스에 begin()과 end() 멤버 함수 추가
iterator begin() const
{
return iterator(header -> next);
}
iterator end() const
{
return iterator(trailer);
}
∙ DoublyLinkedList 클래스에 find() 멤버 함수 추가
iterator find(cost int val)
{
Node* curr = header -> next;
while (curr -> data != val && curr != trailer)
curr = curr -> next;
return iterator(curr);
}
∙ 범용 데이터 저장을 위한 클래스 템플릿 작성
- Node와 DoublyLinkedList 클래스 모두 typename T를 사용하는 클래스 템플릿으로 변경
- Node 와 DoublyLinkedList 클래스에서 데이터를 표현하는 int를 T로 바꾸고, Node를 Node <T>로 변경
template <typename T>
struct Node
{
T data;
Node* prev;
Node* next;
};
template <typename T>
class DoublyLinkedList
{
private:
int count;
Node<T>* header;
Node<T>* trailer;
};
std::list와 std::forward_list
∙ std::list
- 이중 연결 리스트를 구현한 컨테이너
- 어느 위치라도 원소의 삽입 또는 삭제를 상수 시간으로 처리
- 특정 위치에 곧바로 접근할 수 없음
> std::vector처럼 [] 연산자를 이용한 랜덤 액세스는 지원 안 함
> begin(), end() 등의 함수로 얻은 (양방향) 반복자와 ++, -- 연산자로 위치 이동
- <list>에 정의되어 있음
| 함수 이름 | 설명 |
| front(), back() | 리스트의 맨 앞 또는 맨 마지막 원소 참조 |
| begin(), end(), rbegin(), rend() | (양방향) 반복자 반환 |
| insert(), push_front(), push_back(), emplace() | 리스트에 원소 삽입 |
| clear(), pop_front, pop_back(), erase() | 리스트에서 원소 삭제 |
| splice() | 다른 리스트의 원소를 이동 |
| remove(), remove_all() | 특정 조건을 만족하는 원소를 삭제 |
| reverse() | 원소 순서를 역순으로 변경 |
| unique() | 연속적으로 나타나는 중복 원소를 삭제 |
| sort() | 정렬 |
∙ list 예제 코드
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> l1; //비어있는 리스트
l1.push_back(10); // 리스트에 10 추가
l1.push_back(20); // 리스트에 10 -> 20 추가
// 리스트 초기값
list<int> l2 {10, 20, 30, 40};
// 리스트 출력 하는 방법
for (auto a : l2)
cout << a << ", " ;
cout << endl;
// l2 맨 마지막 위치에 l1리스트를 붙혀라 (l1 리스트는 비어지는 형태가 된다)
l2.splice(l2.end(), l1); // 10, 20, 30, 40, 10, 20
// l2 출력
for (auto i : l2)
cout << i << ", ";
cout << endl;
// l1 출력
for (auto j : l1)
cout << j << ", ";
cout << endl;
// 정렬 (오름차순)
l2.sort(); // 10, 10, 20, 20, 30, 40
for (auto i : l2)
cout << i << ", ";
cout << endl;
// 중복 제거
l2.unique(); // 10, 20, 30, 40
for (auto i : l2)
cout << i << ", ";
cout << endl;
}
∙ std::forward_list
- 단순 연결 리스트를 구현한 컨테이너
- begin() 함수로 (순방향) 반복자를 얻을 수 있고, 오직 ++ 연산만 사용 가능
- std::list보다 빠르게 동작하고, 적은 메모리를 사용
- <forward_list>에 정의되어 있음
∙ std::list와 std::forward_list 차이점
| list | forward_list | 설명 |
| front(), back() | front() | forward_list는 front() 함수만 제공 |
| begin(), end() | before_begin(), begin(), end() | forward_list는 before_begin()함수를 추가로 제공하고, 순방향 반복자만 얻을 수 있음 |
| insert(), emplace(), erase() | insert_after(), emplace_front(), pop_front() | forward_list는 연결 리스트 맨 앞에서만 원소를 삽입하거나 삭제하는 함수를 제공 |
| push_front(), push_back(), emplace_front(), emplace_back(), pop_front(), pop_back() | push_front(), emplace_front(), pop_front() | forward_list는 연결 리스트 맨 앞에서만 원소를 삽입하거나 삭제할 수 있음 |
| size() | N/A | forward_list는 std::distance()함수를 활용하여 원소 개수를 알 수 있음 |
- forward_list 예제 코드
#include <iostream>
#include <forward_list>
using namespace std;
int main()
{
// forward_list 초기화
forward_list<int> l1 {10, 20, 30, 40};
l1.push_front(40); // 40, 10, 20, 30, 40
l1.push_front(30); // 30, 40, 10, 20, 30, 40
for (auto a : l1)
cout << a << ", ";
cout << endl;
// forward_list의 개수를 확인하는 방법
long cnt = distance(l1.begin(), l1.end());
cout << cnt << endl;
// 특정 갑을 삭제
l1.remove(40); // 30, 10, 20, 30
l1.remove_if([](int n) {return n > 20;}); // 10, 20
}
