[C++ STL] List 구현과 Iterator
STL, List, Iterator에 대한 공부를 하며 작성한 메모입니다.
1. list 구현
STL에서 지원하는 iterator(반복자)를 지원하는 방식
List의 구현에는 여러 방식이 존재합니다.
구현에 사용된 방식은 멤버 변수 _head와 _tail이 임의의 값을 가지는 형태로 구현하였습니다.
template<typename T>
class Node
{
public:
Node() : prev(nullptr), next(nullptr), data(0)
{}
Node(const T& data) : prev(nullptr), next(nullptr), data(data)
{}
public:
Node* prev;
Node* next;
T data;
};
template<typename T>
class List
{
public:
class Iterator
{
public:
Iterator() : _node(nullptr) { }
Iterator(Node<T>* node) : _node(node) { }
public:
Iterator operator++(int) // 후위 연산 ( 컴파일러 )
{
Iterator temp = *this;
_node = _node->next;
return temp;
}
Iterator& operator++() // 전위 연산
{
_node = _node->next;
return *this;
}
T& operator*()
{
return _node->data;
}
bool operator==(const Iterator& other)
{
return _node == other._node;
}
bool operator!=(const Iterator& other) const
{
return _node != other._node;
}
public:
Node<T>* _node;
};
public:
List() : _size(0)
{
_head = new Node<T>();
_tail = new Node<T>();
_head->next = _tail;
_tail->prev = _head;
}
void push_back(const T& value)
{
Node<T>* temp = new Node<T>(value);
Node<T>* prevNode = _tail->prev;
temp->prev = prevNode;
temp->next = _tail;
temp->data = value;
_tail->prev = temp;
prevNode->next = temp;
_size++;
}
void push_front(T value)
{
Node<T>* temp = new Node<T>(value);
Node<T>* nextNode = _head->next;
temp->next = nextNode;
temp->prev = _head;
temp->data = value;
nextNode->prev = temp;
_size++;
}
void pop_back()
{
if (_size == 0)
{
std::cout << "Empty List - > pop_back() \n";
return;
}
Node<T>* deleteNode = _tail->prev;
Node<T>* prevNode = deleteNode->prev;
prevNode->next = _tail;
_tail->prev = prevNode;
delete(deleteNode);
}
void pop_front()
{
if (_size == 0)
{
std::cout << "Empty List - > pop_back() \n";
return;
}
Node<T>* deleteNode = _head->next;
Node<T>* nextNode = deleteNode->next;
nextNode->prev = _head;
_head->next = nextNode;
delete(deleteNode);
}
Iterator begin()
{
return Iterator(_head->next);
}
Iterator end()
{
return Iterator(_tail);
}
Iterator erease(Iterator it)
{
Node<T>* deleteNode = it._node;
Node<T>* nextNode = deleteNode->next;
Node<T>* prevNode = deleteNode->prev;
prevNode->next = nextNode;
nextNode->prev = prevNode;
delete(deleteNode);
_size--;
return Iterator(nextNode);
}
Iterator insert(Iterator it, int value)
{
Node<T>* newNode = new Node<T>;
newNode->data = value;
Node<T>* nextNode = it._node;
Node<T>* prevNode = nextNode->prev;
prevNode->next = newNode;
_size++;
}
template<typename Predicate>
void remove_if(Predicate pred)
{
auto it = begin();
while (it != end())
{
if (pred(*it))
{
it = erase(it);
}
else
{
++it;
}
}
}
private:
Node<int>* _head;
Node<int>* _tail;
int _size;
};
공부를 하면서 알게 된 사실은 알게 모르게 사용한 이터레이터의 구현 방식이다.
list<int> li;
li.push_back(1);
auto it = li.begin();
auto 키워드를 사용하여 iterator(반복자)를 사용하면 컴파일러에게 해당 타입의 추론을 지시할 수 있습니다.
실제로는 List_iterator가 외부에 정의되어 있지만 using 키워드를 통해 클래스의 멤버 클래스처럼 사용할 수 있게 래핑된 방식
(using 키워드를 통해 list 클래스 내부에서는 특정 타입(std::List_iterator)에 대한 별칭을 사용하겠다는 타입 정의)
즉 iterator(반복자)는 각 컨테이너에 맞게 저장된 원소를 순회하고 접근하는 일반화된 방법을 제공합니다.
2. List의 iterator(반복자)의 사용 및 주의 사항
List는 원소의 저장 위치(순서)가 정해지며 노드 기반 컨테이너입니다.
at(), [] 연산자를 제공하지 않으며 임의 접근 반복자가 아닌 양방향 반복자를 제공합니다.
- (at()은 범위 점검을 하며 동작, [] 연산자는 범위 점검 없이 동작 )
그 전에, List에서 삽입과 삭제의 시간 복잡도는 상수 시간 복잡도를 제공한다.
그런데, 이것은 노드 기반 컨테이너에서 개별 원소의 위치를 이미 알고 있다는 조건에 한해서다.
vector 컨테이너의 경우
중간에 요소를 삽입할 시 뒤의 요소들이 한 칸씩 밀려야 하기 때문에 (n) 시간 복잡도를 가질 수 있지만
초기 상태:
[1, 2, 3, 4, 5] // 3, 4, 5 는 인덱스 [2, 3, 4] 에 위치함
'X'를 삽입:
[1, 2, X, 3, 4, 5] // 3, 4, 5 는 'X'의 삽입으로 인해 인덱스 [3, 4, 5] 로 밀렸음
- 이 때문에 같은 시퀀스 컨테이너인 vector, deque 의 반복자는 메모리 재할당이 일어날 수 있으니, 원소의 삽입과 삭제가 발생하면 반복자가 무효화된다.
List 컨테이너의 경우
- head -> [1] -> [2] -> [3] -> [4] -> [5] -> tail // 삽입해야 할 위치를 가지고 있지 않은 경우 (n)의 시간 복잡도
- head -> [1] -> [2] -> [3] (Iterator) -> [4] -> [5] -> tail // 순회를 통해 이미 위치를 알고 있을 경우 (1)의 시간 복잡도
또한 head와 tail의 경우 이미 위치를 가지고 있기 때문에
맨 앞과 맨 뒤의 삽입은 상수 시간 복잡도(1)를 가질 수 있다.
List에서 제공하는 iterator를 사용할 때 주의할 사항이 있다.
iterator를 통해 List를 순회하는 중에 erase를 사용할 경우, iterator(반복자)는 무효화되지 않는다.
해당 함수 다음 원소의 iterator를 반환한다.
즉 리스트에서 iterator를 통해 순회할 때 조건문 안에서 값을 수정하는 방법은 권장되지 않는다.
list<int> li;
li.push_back(1);
li.push_back(2);
li.push_back(3);
li.push_back(4);
for (auto it = li.begin(); it != li.end(); it++)
{
if (*it == 2)
{
li.erase(it);
}
}
해당 코드는 Debug 모드에서는 프로그램이 뻑이 나지만,
Release 모드에서는 조건문에서 3을 건너뛰고 4로 순회를 이어간다.
권장하는 방법은
for (auto it = li.begin(); it != li.end(); ) {
if (*it == 2) {
it = li.erase(it); // 'it'를 삭제된 원소의 다음 원소로 업데이트
} else {
++it; // 'it'를 다음 원소로 이동
}
}
이런 식으로 조건문의 밖에서 iterator를 업데이트하여야 한다.
댓글