이번 포스트에서는 STL 에 대해 살펴본 후, STL vector, list에 대해 알아본다.
그리고 각 컨테이너에서 사용되는 iterator를 우리만의 Vector, List, Iterator 클래스로 간단하게 구현해보고 시간복잡도까지 이해하는 것으로 마무리하고자 한다 〰️ 🌱
STL
표준 템플릿 라이브러리 STL 은 C++ Template 으로 작성된 많은 제네릭 클래스와 함수 라이브러리로서,
HP사가 1994년에 처음 세상에 내놓은 이후 일반화 프로그래밍 혹은 제네릭 프로그래밍이라는 새로운 프로그래밍 패러다임을 가져왔다.
ISO/ANSI C++ 표준위에서는 논란 끝에 STL 을 C++ 의 표준으로 채택하여 현재 C++ 표준 라이브러리에 포함하고 있다.
STL 에 구현된 제네릭 함수나 클래스를 이용하면 보다 쉽게 C++ 프로그램을 구축할 수 있다.
STL 에 포함된 Generic 클래스와 함수들은 다음과 같이 3종류로 분류된다.
- 컨테이너 - 템플릿 클래스
- iterator - 컨테이너 원소에 대한 포인터
- 알고리즘 - 템플릿 함수
컨테이너
- 데이터를 저장하고 검색하기 위해 담아두는 자료구조를 구현한 템플릿 클래스로서,
- vector, deque, list, set, map, stack, queue 등이 있으며 이들을 컨테이너라고 부른다.
iterator
- iterator 는 반복자라고 불리는 것으로, 컨테이너의 원소들을 하나씩 순회 접근하기 위해 만들어진 컨테이너 원소에 대한 포인터이다.
- iterator 는 원소를 읽을 때 사용하는 iterator, 원소를 기록할 때 사용하는 iterator, 둘 다 가능한 iterator 등 다양한 iterator 가 있다.
- 개발자는 자신이 필요한 것을 사용하면 된다.
알고리즘
- 컨테이너의 원소에 대한 copy, find/search, remove, sort 등의 기능을 구현한 템플릿 함수로서 통칭하여 알고리즘이라고 부른다.
- 이들 함수는 컨테이너 클래스의 멤버 함수가 아니다.
- STL algorithm 은 전역 함수로서, STL 컨테이너 클래스의 멤버 함수가 아니며 템플릿으로 작성되어 있다.
- STL algorithm 함수는 Iterator와 함께 작동한다.
stl 을 사용하여 프로그램을 작성하려면, 이 세 가지 중 하나만 사용하게 되는 경우는 드물다.
예를 들어 list 컨테이너에 저장된 값을 검색하거나 삭제하기 위해 iterator를 사용하며, list에 저장된 값을 정렬하기 위해 sort() 등 알고리즘 함수를 사용한다. 사실상 STL의 세 가지 요소가 거의 함께 사용되므로, 독자들은 이 3가지를 모두 알아야 한다.
STL 컨테이너의 종류
STL 컨테이너 클래스는 컨테이너에 저장되는 원소를 다루는 방식에 따라 3가지로 분류된다.
- Sequence Container (순차 컨테이너)
- vector, dequem list 등으로서 연속적인 메모리 공간에 순서대로 값을 저장하고 읽는 컨테이너이다.
- 인덱스를 사용하여 컨테이너 내의 특정 위치에 있는 값을 읽거나 변경할 수 있다.
- Container Adapter (컨테이너 어댑터)
- 다른 컨테이너를 상속받아 기능 중 일부만 공개하여 기능을 제한하거나 변형한 컨테이너로 stack, queue 등이 있다.
- Associative Container (연관 컨테이너)
- Key 로 Value 를 저장하고 Key 로 검색하여 Value 를 알아내는 컨테이너로서
- set, map 등이 있다.
🔖 STL 컨테이너는 스스로 크기를 조절하여 원소의 개수로 인한 사용자의 부담을 덜어주고, STL iterator는 컨테이너 종류에 무관하게 컨테이너의 원소들을 검색할 수 있도록 설계되었다. STL 알고리즘 역시 컨테이너 종류에 상관없이 작동하도록 설계되었다.
| 컨테이너 클래스 | 설명 | 헤더 파일 |
|---|---|---|
| vector | 가변 크기의 배열을 일반화한 클래스 | <vector> |
| deque | 앞뒤 모두 입력 가능한 큐 클래스 | <deque> |
| list | 빠른 삽입/삭제 가능한 리스트 클래스 | <list> |
| set | 정렬된 순서로 값을 저장하는 집합 클래스. 값은 유일 | <set> |
| map | (key,value)쌍을 저장하는 맵 클래스 | <map> |
| stack | 스택을 일반화한 클래스 | <stack> |
| queue | 큐를 일반화한 클래스 | <queue> |
STL iterator 의 종류
| iterator의 종류 | iterator에 ++연산 후 방향 | read/write |
|---|---|---|
| iterator | 다음 원소로 전진 | read/write |
| const_iterator | 다음 원소로 전진 | read |
| reverse_iterator | 지난 원소로 후진 | read/write |
| const_reverse_iterator | 지난 원소로 후진 | read |
STL 알고리즘 함수들
copy(), merge, random, rotate,
equal, min, remove, search,
find, move, replace, sort,
max, partition, reverse, swap
iterator 사용
iterator 는 컨테이너 안에 있는 원소들을 하나씩 순차적으로 접근하기 위한 원소에 대한 포인터이다.
iterator 를 생성하려면 컨테이너 템플릿에 구체적인 타입을 지정하여, 원소의 타입이 드러나도록 하여야 한다.
각 컨테이너는 추가, 삭제, 순회, 검색의 기능을 하는 함수가 있다.
vector 🏢
구현해보기
template<typename T>
class Vector
{
public:
Vector() : _data(nullptr), _size(0), _capacity(0)
{
}
~Vector()
{
if(_data)
delete[] _data;
}
void push_back(const T& val)
{
if(_size == _capacity)
{
// 증설 작업
int newCapacity = static_cast<int>(_capacity * 1.5);
if(newCapacity==_capacity)
newCapacity++;
reserve(newCapacity);
}
_data[size] = val; // 데이터 저장
_size++; // 데이터 개수 증가
}
void reserve(int capacity)
{
_capacity = capacity;
T* newData = new T[_capacity];
// 데이터 복사
for(int i=0; i<_size; i++)
newData[i] = _data[i];
// 기존에 있던 데이터를 삭제해준다
if(_data)
delete[] _data;
// 교체
_data = newData;
}
// 레퍼런스로 반환하는 이유는, 데이터를 직접 건드릴 수 있도록!
T& operator[](const int pos) {return _data[pos];}
int size() {return _size;}
int capacity() {return _capacity;}
public:
typedef Iterator<T> iterator;
iterator begin() { return iterator(&_data[0]); }
iterator end() { return begin() + _size; }
private:
T* _data;
int _size;
int _capacity;
};
int main()
{
Vector<int> v;
v.push_back(100);
cout << v.size() << endl;
cout << v[0]; << endl;
}
iterator
어떠한 컨테이너를 사용하더라도 동일한 인터페이스를 제공한다. 다른 자료구조로 사용하기 편하다는 점.
iterator는 컨테이너 안에 있는 원소들을 하나씩 순차적으로 접근하기 위한, 원소에 대한 포인터다.
다음/이전 원소로 이동이 가능하며 시작부터 끝까지 순회가 가능하다.
즉 추가 삭제 순회 검색이 가능하다.
-
포인터는 말 그대로 주인님이 딱히 없는데, 이터레이터는 누구에게 소속된 것이라는 차이가 있다.
-
이터레이터 자체는 클래스이지만, 그 클래스 타입을 마치 우리가 포인터처럼 사용하게끔 이런 온갖 문법들을 다 지원한다.
-
*operator overloading 을 지원하게끔 뭔가를 랩핑해가지고 만들어준다 -
포인터 연산처럼 연산이 가능하다.
-
end() 로 확인해서 보면, 유효하지 않은 쓰레기 값을 들고 있다.
주의할 점: 삭제
벡터에서 사용하는 iterator 를 구현해보며 더 이해해보자
template<typename T>
class Iterator
{
public:
Iterator(): _ptr(nullptr)
{
}
Iterator(T*ptr): _ptr(ptr)
{
}
// 전위형
Iterator& operator++()
{
_ptr++;
return *this;
}
// 후위형
Iterator& operator++(int)
{
Iterator temp = *this;
_ptr++;
return temp;
}
// 전위형
Iterator& operator--()
{
_ptr--;
return *this;
}
// 후위형
Iterator& operator--(int)
{
Iterator temp = *this;
_ptr--;
return temp;
}
Iterator operator+(const int count)
{
Iterator temp = *this;
temp._ptr += count;
return temp;
}
Iterator operator-(const int count)
{
Iterator temp = *this;
temp._ptr -= count;
return temp;
}
bool operator==(const Iterator& right)
{
return _ptr == right._ptr;
}
bool operator!=(const Iterator& right)
{
return !(*this == right);
}
T& operator*()
{
return *_ptr;
}
public:
T* _ptr;
}vector 의 시간복잡도
- size (resize)
O(N) - capacity (reserve)
O(1)- 벡터의 크기와 관계없이 일정한 시간이 소요되며, 기존 요소들은 영향을 받지 않는다.
- 삽입/삭제
- 시작
O(N) - 중간
O(N) - 끝
O(1)
- 시작
- push_back
- 최선:
O(1), 최악:O(N) push_back()은 상수 시간 복잡도O(1)를 갖는다. 이는 벡터의 용량(capacity)이 충분하다면 삽입 연산이 빠르게 수행되는 것을 의미한다. 하지만 용량이 부족한 경우에는 요소를 추가하기 위해 메모리를 다시 할당해야 하므로 선형 시간 복잡도O(n)가 될 수도 있다. 즉,push_back()의 평균 시간 복잡도는O(1)이지만 최악의 경우에는O(n)이 될 수 있다.
- 최선:
- pop_back
O(1) - push_front
- 없는 함수. 오래 걸릴 수 있어서 애초에 stl 에 포함되지 않는다.
- front
O(1) - back
O(1) - 임의 접근 v[i]
O(1) - size
O(1) - v.remove(10)
- std::vector 에는 remove() 함수가 내장되어 있지 않다. remove() 알고리즘은 선형 시간 복잡도
O(n)를 갖는다. 이 알고리즘은 특정 값과 일치하는 요소를 찾아서 제외하고, 나머지 요소들을 앞으로 이동시키는 작업을 수행한다. 따라서 remove() 알고리즘을 사용하면 해당 요소의 개수에 비례하여 시간이 소요된다.
대신erase()함수를 사용하여 제외된 요소들을 벡터에서 삭제할 수 있다.erase()함수는 삭제된 요소들을 한 번에 한 칸씩 앞으로 이동시키는 작업을 수행하므로 최악의 경우에는 선형 시간 복잡도O(n)를 가질 수 있다.
- std::vector 에는 remove() 함수가 내장되어 있지 않다. remove() 알고리즘은 선형 시간 복잡도
𝑸. 벡터에서 size 와 capacity 의 차이는?
𝐀. capacity 는 할당된 공간, size 는 실제 데이터 크기
𝑸.
reserve를 먼저 하는 이유?
𝐀. 이사 비용을 아낄 수 있고 메모리 파편화도 아낄 수 있다
list ⛓️
연결리스트이며, node 기반의 자료구조이다. STL의 리스트처럼 양방향 연결리스트, 그리고 연결리스트에서 사용하는 이터레이터를 만들어보면서 더 이해해보자!
구현해보기
templaye <typename T>
class Node
{
public:
Node() : _next(nullptr), _prev(nullptr), _data(T())
{
}
Node(const T& value) : _next(nullptr), _prev(nullptr), _data(value)
{
}
public:
Node* _next;
Node* _prev;
T _data;
};
template<typename T>
class Iterator
{
public:
Iterator() : _node(nullptr) {}
Iterator(Node<T>* node) : _node(node) {}
// 연산자 오버로딩
// ++it 전위
Iterator& operator++()
{
_node = _node->_next;
return *this;
}
// it++ 후위
Iterator& operator++()
{
Iterator<T> temp = *this;
_node = _node->_next;
return temp;
}
// --it 전위
Iterator& operator--()
{
_node = _node->_prev;
return *this;
}
// it-- 후위
Iterator& operator--()
{
Iterator<T> temp = *this;
_node = _node->_prev;
return temp;
}
T& operator*()
{
return _node->_data;
}
bool operator==(const Iterator& right)
{
return _node == right._node;
}
bool operator!=(const Iterator& right)
{
return _node != right._node;
}
public:
Node<T>* _node;
};
template <typename T>
class List
{
public:
List() : _size(0)
{
// header 는 자기 자신을 가리킨다
_header = new Node<T>();
_header->_next = _header;
_header->_prev = _header;
}
~List()
{
while(_size > 0)
pop_back();
delete _header;
}
void push_back(const T& value)
{
AddNode(_header, value);
}
void pop_back()
{
RemoveNode(_header->_prev);
}
Node<T>* AddNode(Node<T>* before, const T& value)
{
Node<T>* node = new Nodee<T>(value);
Node<T>* prevNode = before->_prev;
prevNode->_next = node;
node->_prev = prevNode;
node->_next = before;
before->_prev = node;
_size++;
return node;
}
Node<T>* RemoveNode(Node<T>* node)
{
Node<T>* prevNode = node->_prev;
Node<T>* nextNode = node->_next;
prevNode->_next = nextNode;
nextNode->_next = prevNode;
delete node;
_size--;
return nextNode;
}
int size() { return _size; }
public:
typedef Iterator<T> iterator;
iterator begin() { return iterator(_header->_next); }
iterator end() { return iterator(_header); }
iterator insert(iterator it, const T& value)
{
Node<T>* node = AddNode(it._node, value);
return iterator(node);
}
iterator erase(iterator it)
{
Node<T>* node = RemoveNode(it._node);
return iterator(node);
}
public:
Node<T>* _header;
int _size;
};
int main()
{
List<int> li;
List<int>::iterator eraseIt;
for(int i=0; i<10; i++)
{
if(i==5)
{
earseIt = li.insert(li.end(), i);
}
else
{
li.push_back(i);
}
}
li.pop_back();
li.erase(eraseIt);
for(list<int>::iterator it = li.begin(); it!=li.end(); ++li)
{
cout << (*li) << endl;
}
return 0;
}
list 의 시간복잡도
- size (resize)
O(N) - capacity (reserve)
- 없는 개념이다.
- 삽입/삭제
- 시작
O(1) - 중간
O(1)이터레이터로 들고있을 때처럼 위치를 기억하고 있을 때 빠르다 - 끝
O(1)
- 시작
- push_front
O(1) - push_back
O(1) - front
O(1) - back
O(1) - erase
- remove
- 임의 접근
O(1)이터레이터로 들고있을 때처럼 위치를 기억하고 있을 때 빠르다
(C# 에서의 리스트는 벡터이다)
deque
double-ended queue
배열 형태로 만들어졌다는 것은 벡터와 유사하나, 복사 이사하지 않고 메모리를 따로 파서 더 저장하는 형태이다.
#include <deque>
int main()
{
deque<int> dq;
dq.push_back(1);
dq.push_front(2);
cout << dq[0] << endl;
}
🔗 Reference
틀린 내용이 있다면 댓글로 알려주시면 감사하겠습니다 😊
