이번 포스트에서는 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)를 가질 수 있다.

𝑸. 벡터에서 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

https://modoocode.com/223

틀린 내용이 있다면 댓글로 알려주시면 감사하겠습니다 😊