Standard Template Library
STL 는 Standard Template Library 라고 한다. 즉 프로그래밍 할때 필요한 자료구조 및 알고리즘등을 템플릿으로 제공하는 라이브러리이다. 일단 STL 라이브러리에 뭐가 있는지 알아보자. 첫번째는 Container 이다. Container 같은 경우 데이터를 저장하는 객체, 즉 하나의 Data Structure 이다.
Vector
일단 Container 의 종류의 하나인 vector 을 알아보자. 일단 알아볼가지가 몇개가 있다.
- vector 의 동작 원리 (size / capacity)
- 중간 삽입 / 삭제
- 처음 / 끝 삽입 / 삭제
- 임의 접근
동적 배열이라고 함은, 뭔가 동적으로 배열으로 커지고, element 를 추가했을때 배열의 사이즈가 동적으로 커지는 현상을 말한다. 반대로 배열을 사용할때의 문제를 기억해보자. 문제점은 바로 배열의 사이즈다. 뭔가 동적으로 커지고 줄어드는게 힘들기때문에 배열의 단점이다. 하지만 동적배열은 고무줄 처럼 커지고 작아진다.
#include <vector>
int main()
{
vector <int> v;
v.push_back(1);
v.push_back(2);
v.push_back(4);
v.push_back(5);
const int size = v.size();
for (int i = 0; i < size; i++)
{
cout << v[i] << endl;
}
return 0;
}
그렇다고 한다고 하면 vector 의 동작 원리는 뭐길래? 이렇게 고무줄 처럼 사이즈가 늘어나고 줄어들수 있을까? 일단은 두가지의 로직이 존재한다.
- (여유분을 두고) 메모리를 할당한다.
- 여유분까지 꽉 찼으면, 메모리를 증설 한다.
그렇다면 질문!?
- 여유분은 얼만큼이 적당할까?
- 증설을 얼만큼 해야할까?
- 기존의 데이터를 어떻게 처리할까?
첫번째 질문 같은 경우, 아까 봤던것 처럼 v.size() 를 봤을때 실제 용량이고, v.capacity() 는 여유분을 포함한 용량이다. 아래의 코드를 샐행했을때 vector 의 크기가 변화함에 따라서 capacity 가 1.5 또는 2 배 증가하는게 보인다. 그럼 왜 이게 이렇게 설정이 되어있을까? 만약에 배열이 꽉 차있다고 하면 두배로 증가 시킨다. 예를들어서 처음에 [1 2 3 4 5] 되어있다고 치자, 그러면 2 배 만큼을 증설을 시킬거고 그 다음에는 메모리는 malloc 을 통해서 덧붙여도 되지만, 애초에 2배된걸 memory 를 할당해서 메모리를 1.5 를 만든 다음, 복사를 하는 식이다. 즉 더 넒은 곳으로 이사를 하게 된다. 결국에는 지금 현재 메모리에 들고 있는 1.5 배 또는 2 배를 더 큰걸 옮겨주는 정책이 정해져있는것이다. 만약에 1만큼 증가하면 복사하는 비용이 더더욱 커져서 1.5 배나 2 배로 늘어난다.
그럼 예를들어서 capacity() 처음에 저장할수 있는 방법은 v.reserve(100) 이렇게 하면 처음에 100개로 capacity 가 설정이된다. 그런다면 100 개가 넘어가면 150 으로 변경이된다. 마찬가지로 v.resize() 같은경우는 사이즈를 세팅해주는거다.
#include <vector>
int main()
{
vector<int> v;
for (int i = 0; i < 100; i++)
{
v.push_back(100);
cout << v.size() << " " << v.capacity() << endl;
}
return 0;
}
만약에 vector 를 clear 했다고 한다고 하면 size 나 capacity 의 변화는 어떻게 될까를 한번 알아보자. 아래의 코드를 실행해보면 capacity 는 그대로 1000 개 이고, size 는 0 으로 확인 할 수 있다. 완벽히 capacity 값을 0 으로 만드는 방법은 v 를 깡통인거에 해주면 같이 size 와 capacity 가 0 이될거다.
#include <vector>
int main()
{
vector<int> v;
v.reserve(1000);
for (int i = 0; i < 100; i++)
{
v.push_back(100);
cout << v.size() << " " << v.capacity() << endl;
}
v.clear()
vector<int>() swap(v);
cout << v.size() << " " << v.capacity() << endl;
return 0;
}
그럼 데이터 꺼내기 같은경우는 v.front() 맨처음거를 꺼내오거나, v.back() 맨뒤에거를 꺼내오거나 v.push_back 이 있는것처럼 v.pop_back() 이 있다. 심지어 Initialize 도 가능하다. vector<int> v(1000, 0) 를 할수 있는데 1000 은 v.size() 고 0 은 초기값이다. 그리고 복사도 가능하다.(예: vector<int> v2 = v)
일단 위와 같이 vector 의 동작원리를 알아보았다. 그 다음에 알아봐야될거는 어떻게 vector 안에 있는 element 들을 indexing 할수 있는지를 알아야한다. 이거를 알려면 일단 Iterator(반복자) 의 내용에 대해서 알아야 한다. 일단 iterator 는 pointer 와 유사한 개념이고 Container 의 Element 를 가르키고 다음 또는 이전 원소로 넘어갈수 있다.
아래의 코드를 한번 봐보자. 일단 iterator 와 pointer 의 차이가 없다고 보인다. 하지만 iterator 의 메모리를 까보면 추가적인 정보를 들고 있다는걸 확인 할수 있다. 주사값은 물론이고 내가 어떤 Container 로 들고 있다라는 정보도 있다. iterator 의 찾아들어가면 *() operator 가 있는걸 볼수 있다. 이게 포인터의 값을 들고 오는걸 볼수 있다.
#include <vector>
int main()
{
vector<int> v(10);
for (vector<int>::size_type i = 0; i < v.size(); i++)
v[i] = i;
vector<int>::iterator it;
int* ptr;
it = v.begin();
ptr = &v[0];
cout << (*it) << endl;
cout << (*ptr) << endl;
return 0;
}
pointer 와 비슷하게 ++ -- operator 를 사용할수 있다. 포인터에서의 연산은 그다음 주소(데이터)로 넘어가거나 앞으로가거나였다. 아래의 코드에서 반복자의 처음과 끝을 볼수 있는데, 끝같은경우는 데이터의 마지막 값이 지나고, 쓰레기 값이 들어있다. 즉 유효하지 않은값까지 이다.
iterator 는 뭔가 복잡해 보인다. 그런데 사실 iterator 는 vector 뿐만아니라, 다른컨케이너도 공통적으로 있는 개념이다.
#include <vector>
int main()
{
vector<int> v(10);
for(vector<int>::size_type i = 0; i < v.size; i++)
v[i] = i;
vector<int>::iterator>> itBegin = v.begin();
vector<int>::iterator itEnd = v.end();
for (vector<int>::iterator it=v.begin(); i != v.end(); ++it)
{
cout << (*it) << endl;
}
int* ptrBegin = &v[0]; // v.begin()._Ptr
int* ptrEnd = ptrBegin + 10; // v.end()._Ptr
for (int*ptr=ptrBegin; ptr!=ptrEnd; ++ptr)
{
cout << (*it) << endl;
}
return 0;
}
그럼 iterator 에서 어떤 애들이 있을까? 일단 아래의 코드를 한번봐보자. 일단 const_iterator 가 존재한다. 그말은 값을 변경 하지 못한다는 뜻이다. 그리고 역방향도 있는데 reverse_iterator 라는걸로 vector 를 설정해주고, iterating 을 한다.
vector<int>::const_iterator it = v.begin();
*it = 100; // const 기 때문에 바꿀수 없다.
// 역방향
for (vector<int>reverse_iterator it = v.begin(); it != v.end() ++it)
{
cout << (*it) << endl;
}
다시 돌아가서 이제 vector 의 접근 / 삽입 / 삭제등을 어떻게 활용하는지 보고, 해당되는 performance 를 체크 해보자. 일단 vector 는 container 이기 때문에 하나의 메모리 블록에 연속하게 저장된다. 만약에 예를들어서 중간에 삽입을 한다고 하면, 사이즈가 증가 할때마다 큰곳으로 복사를 해주어야 하는데, 그때의 복사 비용이 커진다. 그리고 삭제 같은 경우, 블록을 하나 사라 진다고 하면, 그래서 중간 삽입 / 삭제가 비효율적이다라는걸 알수 있다. 이 이야기 처럼 처음 삽입 / 삭제도 비효율적이라고 볼수 있다. 하지만 끝 삽입 / 삭제같은 경우는 뒤에것만 지우기때문에 효율적이다. Random Access(임의 접근) 같은 경우도 사실 하나의 메모리 블록에 연속적이다는 특성으로 인해서 임의 접근이 쉽게 된다.
// Init: [0][1][2][3][4]
v.insert(v.begin() + 2, 5);
// After: [0][1][5][2][3][4]
v.erase(v.begin()+2);
// After: [0][1][2][3][4]
v.erase(v.begin()+2, v.begin()+4);
// After: [0][1][4] 4 는 삭제 되지 않음
실수중에 하나가, 예를 들어서 3 이라는 데이터가 있으면 일괄 삭제하는 케이스가 있다고 하자. 아래의 코드는 그 예제의 케이스다고 볼수 있다, 그리고 이 코드를 돌렸을때, 실패가 났을것이다. 삭제를 했을때, 이때의 iterator 는 container 의 소속이 아니게된다. 그 다음에 it 에서 유효하지 않기 때문에 그다음 loop 에서 실패가 난다. 그래서 v.erase(it) 하면 null 인 상태가 아니라, iterator 다시 받을수있다. 근데 사실이것만 하면 되는게 아니라, iterator 가 그냥 넘어갔다고 하면 3 뒤에 나오는 element 는 스킵을 한다는게 포인트다. 즉 넘어가게끔 else 넘어가게 해주어야한다. 그리고 내부에서 절대 절대 clear() 를 call 하면 안된다.
#include <vector>
int main()
{
vector<int> v(10);
for (vector<int>::size_type i=0; i < v.size(); i++)
v[i] = i;
for (vector<int>::iterator it = v.begin(); it != v.end())
{
int data = *it;
if (data == 3)
{
//v.erase(it);
it = v.erase(it);
}
else
{
++it;
}
}
return 0;
}
vector 를 간략하게 구현해보자.
template<typename T>
class Iterator
{
public:
Iterator() : _ptr(nullptr){}
Iterator(T *ptr): _ptr(ptr){}
Iterator& operator++()
{
_ptr++;
return *this;
}
Iterator operator+(const int count)
{
Iterator temp = *this;
temp._ptr += count;
return temp;
}
Iterator operator++(int)
{
Iterator temp = *this;
_ptr++;
return temp;
}
Iterator& operator--()
{
_ptr++;
return *this;
}
Iterator operator--(int)
{
Iterator temp = *this;
_ptr++;
return temp;
}
bool operator==(const Iterator& right)
{
return _ptr == right._ptr;
}
bool operator!=(const Iterator& right)
{
return _ptr != right._ptr;
}
T& operator*()
{
return *_ptr;
}
public:
T* _ptr;
};
template<typename T>
class Vector
{
public:
Vecotr() : _data(nullptr), _size(0), _capacity(0){}
~Vecotr()
{
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]; } // v[i] = i;
int size() { return _size; }
int capacity(){ return _capacity; }
private:
T* _data;
int _size;
int _capacity;
typedef Iterator<T> iterator;
Iterator begin() { return iterator(&data[0]);}
Iterator end() {return begin() + _size;}
};
int main()
{
Vector<int> v;
for (int i = 0; i < 100; i++)
{
v.push_back(100);
cout << v.size() << " " << v.capacity() << endl;
}
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << endl;
}
for (Vector<int>::iterator it = v.begin(); i != v.end() ++it)
{
cout << (*it) << endl;
}
return 0;
}
Lists
Vector 와 비슷한 container 의 형식인 List(LinkList) 가 있다. 하지만 List 는 Node 형식으로 되어있다. 즉, 트리 형식으로 만들수 있다는거다. 일단 아래의 코드를 보면, List 에서 대표적으로 유용하게 사용되는게 보인다. 일단 vector 를 비교하면, capacity 가 따로 없다 그 이유는 vector 와달리 Node 형식으로 동작을 한다. 그리고 다른걸 봐보면 push_front 나 pop_front 가 존재한다. 이것도 List 가 Vector 와 다른 형식으로 값을 Contain 하기 때문이다. 마지막으로 random access 가 지원되지 않고, 어떤 element 를 지우는것도 까다롭지 않게 구현이 되어있는걸 볼수 있다.
#include <list>
int main()
{
list<int> l1;
for (int i = 0; i < 100; i++)
l1.push_back(i);
li.push_front(10); // vector 와 다르게 동작
int size = l1.size(); //
// li.capacity() ? // 동적배열인 형식이 아닌 Node 형식으로 동작
int first = li.front();
int last = li.back();
// li[3] = 10; // 임의 접근 안됨
list<int>::iterator itBegin = li.begin();
list<int>::iterator itEnd = li.end();
for (list<int>::iterator it = li.begin(); it != li.end(); ++it)
{
cout << (*it) << endl;
}
li.insert(itBegin, 100);
li.erase(li.begin());
li.pop_front();
li.remove(10);
return 0;
}
위처럼 코드를 잠깐 살펴보았는데, 이제 List 가 어떤 동작 방식을 가지고 있는지 확인을 해보자. 만약 연결리스트의 개념을 알고 있으면, 메모리의 구조를 잘 이해하게 될거다. 일단 연결리스트에 종류가 있는데, 단일, 이중, 원형 LinkList 들로 이루어져있다. 즉 1 -> 2 -> 3 이런식으로 각 각 넘버는 Node 형태로 되어있고, 이 Node 들은 data 를 가지고 있고 그리고 Node 의 주소값을 가지고 있다. 여기서 포인트가 자기 자신의 Node 타입인 아이를 들고 있으면 무한정 Node 안에 Node 가 반복될것이다. 하지만 여기서 봐야될거는 Node 의 포인터 즉 주소값을 가지고 있는게 포인트이기때문에, 그다음의 주소값을 들고 있으면 리스트처럼 들어갈수 있다. 이중리스트 같은 경우는 아래의 Node2 를 보면 된다. Previous 의 주소값과 그다음 주소값을 나타내는게 보인다.
class Node
{
public:
Node* _next;
int _data;
}
class Node2
{
public:
Node2* _next;
Node2* _prev;
int _data;
}
일단 STL 에서는 이중 리스트로 되어있다. 이중리스트가 Node 형식으로 되어있으니까, 중간 삽입 또는 삭제 그리고 처음 / 끝 삽입 또는 삭제가 잘될거라는건 쉽게 믿을수 있다. 하지만 모든게 다 장점을 들고 있었더라면 List 를 많이 썼을거다. 하지만 List 의 단점이 있다. List 의 임의 접근이 쉽지 않다. 그니까 노드 들을 계속 타고 타고 가서 몇번째를 노드에 그 데이터를 가지고 갈수 있다. 그래서 List 에서 성능이 않좋기 때문에, 임의접근의 기능을 지원하지 않는다.
아래의 code segment 를 한번 봐보자. 일단 list 의 앞과 뒤의 주소를 ptrBegin 그리고 ptrEnd 로 저장을 해보자. 그런 다음 데이터의 저장된 Previous 와 Next 의 주소값을 확인하고 그 Node 자신의 데이터 값도 확인을 해보면 잘들어있는게 보인다. 그리고 Link List 에서 맨뒤의 값을 봐보면 Next 가 쓰레기 값으로 들어가있는걸 볼수있다. 이말은 Next 가 쓰레기 값이면 list 의 size 를 알수 있다. 그리고 Link List 이기때문에 궁금할수 있는건 맨마지막에서 빼면 앞으로 가는지, 그리고 뒤에서 맨앞으로 가면 어떻게 되는지 아래의 코드에서 확인 할수 있다. 그래서 LinkList 의 허용범위를 확인 할수 있다.
list<int> iterator itBegin = li.begin();
list<int> iterator itEnd = li.end();
// list<int>::iterator itTest1 = -- itBegin; // 앞에서 맨뒤로 가는건 허용X
list<int>::iterator itTest2 = --itEnd; // 앞으로 가는건 허용
// list<int>::iterator itTest3 = ++itEnd; // 뒤에서 맨 앞으로 가는건 허용X
int* ptrBegin = &(li.front());
int* ptrEnd = &(li.end());
list<int>::iterator it2 = li.begin() + 10;
또 여기에서 의문점이 임의접근이 안되는데 중간 삽입 / 삭제가 빠르다는건 약간의 역설이 들어간다. 이미 삭제된 대상이 정해져 있으면 쉽지만, 그 index 를 가지고 이동해서 삭제하는 어렵다라는걸 알수 있다. 즉 erase 는 빠르게 되지만, 숫가락으로 그 index 까지 찾아줘야하는건 우리의 몫인거다. 그래서 그 다음 아래 코드를 보면, 저렇게 iterator 로 remember 로 받아들인다음에 나중에 삭제할 index 를 찾을수 있는 방법도 있다.
li.erase(li.begin() + 50) // 허용 되지 않음
list<int>::iterator it = li.begin();
for (int i =0; i < 50; i++)
++it;
li.erase(it);
list<int> li;
list<int>::iterator itRemember;
for (int i = 0; i < 100; i++)
{
if(i == 50)
{
itRemember = li.insert(li.end(), i);
}
else
{
li.push_back(i);
}
}
li.erase(itRemember);
그렇다면 간락하게 구현을 한번 해보자.
#include <list>
#include <iostream>
using namespace std;
template<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<T>& operator++()
{
_node = _node->_next;
return *this;
}
//it++
Iterator<T> operator++(int)
{
Iterator<T> temp = *this;
_node = _node->_next;
return temp;
}
// --it
Iterator<T>& operator++()
{
_node = _node->_prev;
return *this;
}
// it--
Iterator<T> operator++(int)
{
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 = 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 Node<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->_prev = _prevNode;
delete node;
_size--;
return nextNode;
}
int size(){return _size;}
public:
typedef Iterator<T> iterator;
iterator begin() { return iterator(_header->_next); } // Header in the Last element would be the frist elem
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)
{
eraseIt = 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(), ++it)
{
cout << (*it) << end;s
}
return 0;
}
Deque
이제 vector 와 list 를 알아 보았다. 이 둘은 sequence container 라고 하는데, 데이터가 넣어지는대로 sequential 하게 넣어지기 때문이다. 우리가 이제 새로배울건 deque, double-ended queue 라고 한다. deque 같은 경우는 vector 와 list 의 사이로 생각하면 된다. 기존에 vector 에서는 배열의 크기를 늘리려면 새로운걸 크게 할당한다음에 복사하는 형태 였다. 하지만 deque 같은 경우는 그 배열 자체를 늘리는게 아닌 새로운 메모리 영역을 이어지게끔 즉 list 형식으로 만들어진다. 결론적으로 vector 와 마찬가지로 배열 기반으로 동작하지만, 메모리 할당하는 방식이 List 와 같다. 아래의 코드를 보면 vector 와 다르게 push_front 를 지원하는걸 볼수 있다.
#include <deque>
#include <vector>
int main()
{
vector<int> v(3,1);
deque<int> dq(3, 1);
v.push_back(2);
v.push_back(2);
dq.push_back(2);
dq.push_back(2);
dq.push_front(3);
dq.push_front(3);
return 0;
}
그렇다고 하면 vector 와 마찬가지로 처음 / 끝 에 대한 삽입 / 삭제가 효율성은 좋고 중간 삽입 삭제가 효율성이 않좋다는걸 확인 할수 있다. 임의 접근 같은 경우는 deque 는 아파트와 같다. deque 에서 F11 를 누르면 확인할 수 있는게, Offset 이라는 친구가 있어서 몇번째 층에 있는지를 확인할수 있고, 거기에 하나씩하나씩 element 를 더하는게 보인다. 즉 offset 과 얼만큼 떨어져있는지를 봐보면 임의 접근은 쉽게 된다는게 장점이다.
Map
Python 과 C# 코드를 보면 Dictionary 라는 타입이 존재 할거다. 바로 Key 와 Value 로 매칭되는식으로 연결되어있는 Hashtable 같은 자료구조이다. c++ 에서도 이런걸 지원하는데 바로 Map 이라는 친구이다. 이 친구는 연관 컨데이너라고도 부른다. 만약에 Python 을 사용해보았더라면, dict 의 indexing 하는 법과 data 를 꺼내오는 방법, 초기 생성등 알것이다. 일단 다시 돌아와서 vector 와 list 의 치명적인 단점으로 꼽자면, 뭔가 아이디에 매칭되는값을 찾으려고 할때 생각보다 코드가 많이 들어간다. 이걸 보완할수 있는게 바로 Map 이다. Map 에서는 균형 이진 트리 (AVL) 로 되어있으니까, 노드 기반을 되어있다. 아래의 첫번째 코드를 봐보면, 한노드에 대한 데이터 구조를 확인 할수 있다.
class Node
{
public:
Node* _left;
Node* _right;
// data
int _key;
int* _value;
}
그렇다면 Map에 대한 예제를 한번 봐보자. 아래와 같이 살펴보자. 일단 Map 에는 key 와 value 의 타입을 설정해줘야되고, key 와 value pair 이기때문에 pair 라는걸 사용해서 m 에 넣어주었다는걸 확인 할수 있다. 그다음에 어떤 아이디를 찾았다고 한다면 erase 를 통해서 삭제가 가능하다. 뭔가 찾을때는 find 라는 걸 사용하면 되는데 이때의 return 타입을 확인해보면 map 에 있는 iterator 라고 확인 할 수 있다. 만약에 find 를 해서 return 값이 map 을 돌다가 끝에 도착하지 않는다고 한다면 그 key 에 매칭되면 찾은거고, end() 에 왔으면 못찾은거다.
여기서 궁금할수 있는거는 insert 와 erase 를 똑같은 키에다가 데이터를 넣었다고 한다면 어떻게 될까라는 질문을 할수 있다. erase 같은경우는 count 를 내뱉는데, 찾아서 지울께 있다면 1 로 내뱉고, 지워졌는데 또 erase 를 하면 0 으로 return 하는데, 이말은 두번호출은 괜찮다는거다. 하지만 insert 같은 경우, 처음 호출하는 insert 만 적용이되고 두번째 호출된 insert 는 되지않는다. 즉 덮어 쓰이지 않는다. 순회하는 부분도 확인 할 수 있는데 key 와 value 값으로 map 은 이루어져있기 때문에, Map 에 있는 iterator 에 first 값은 key 값이고, second 값은 value 로 이루어져있다는 걸 확인 할수 있다.
#include <map>
template<typename T1, typename T2>
struct Pair
{
T1 t1;
T2 t2;
}
int main()
{
map<int, int> m;
pair<map<int, int>::iterator, bool> ok; // 확인 기능
ok = m.insert(make_pair(1, 100));
ok = m.insert(make_pair(1, 200));
for (int i = 0; i < 10000; i++)
{
m.insert(pair<int, int>(i, i * 100));
}
for (int i = 0; i < 5000; i++)
{
int randomValue = rand() % 5000;
m.erase(randomValue);
}
// find the data
map<int, int>::iterator findIt = m.find(1000);
if (findIt != m.end())
{
cout << "Found" << endl;
}
else
{
cout << "Not Found" << endl;
}
unsigned int count = 0;
count = m.erase(10);
count = m.erase(10);
// iteration on map
for(map<int, int>::iterator it = m.begin(); it != m.end(); ++it)
{
pair<int, int>&p = (*it);
int key = p.first; // it->first
int value = p.second; // it->second
}
return 0;
}
이 이후에 확인 해야될거는 map 안에 key / value pair 값이 있느냐 없느냐의 따라서 insert 를 해주는 코드이다. [] operator 사용할시의 유의점이 있는데, 대임을 하지 않더라도 (key/value) 형태의 데이터가 추가 된다. 이때는 강제로 0 으로 initialize 시켜준다.
if (findIt != m.end())
{
findIt->second = 200;
}
else
{
m.insert(make_pair(10000, 300));
}
// 없으면 추가, 있으면 수정
m[5] = 500;
m.clear()
for (int i = 0; i < 10; i++)
{
cout << m[i] << endl;
}
Set, Multimap, and Multiset
map 의 형제들을 초대하려고 한다. set, multimap, and multiset 이다. set 같은 경우 map 과 달리 단독적으로 key 만 사용하고 싶을때 사용하는 자료구조이다. 아래와 같이 코드를 보면서 set 을 확인 해볼수 있다.
#include <set>
int main()
{
set<int> s;
s.insert(10);
s.insert(20);
s.insert(30);
s.insert(40);
s.erase(40);
s.erase(30);
set<int>::iterator findIt = s.find(50);
if (findIt != s.end())
{
cout << "found" << endl;
}
for (set<int>::iterator it = s.begin(); it != s.end(); ++it)
{
cout << (*it) << endl;
}
// s[2] =10 // not allowed
}
multimap 과 multiset 같은경우는 동일한 key 값에 대해서 다른 value 가 있을때 사용할수 있는 자료구조인데, 아래의 코드 에서 확인을 해보자. 일단 multimap 같은 경우 경우 map 과 다르게 동일한 key 에 다른 Value 가 들어간거니, 뭔가 혼동을 줄이기위해서 직접 안에 들어가 데이터를 수정하는건 막혀있다. 여기서 질문 할수 있는건, 지울때 key 값을 넘겨줬을때, 그때는 어떤 value 가 들어있든 상관없이, 그 key 에 해당하는 pair 들을 다 삭제한다. 만약에 그럼 특정 value 에 지우고 싶다면 어떻게 할까? 그럴땐 아래와 같이 iterator 를 돌아서 제일 먼저 찾아지는 친구를 지우게끔 할수도 있다.
#include <map>
#include <set>
int main()
{
multimap<int, int> mm;
mm.insert(make_pair(1, 100));
mm.insett(make_pair(1, 200));
mm.insett(make_pair(2, 200));
mm.insett(make_pair(2, 500));
// mm[1] = 500 // not allowed
unsgined int count = mm.erase(1);
multimap<int, int>::iterator itFind == mm.find(1);
if (itFind != mm.end())
{
mm.erase(itFind);
}
pair<multimap<int, int>::iterator, multimap<int, int>::iterator> itPair;
itPair = mm.equal_range(1);
multimap<int, int>::iterator itBegin = mm.lower_bound(1); // 1 이나오는 첫 순간
multimap<int, int>::iterator itEnd = mm.upper_bound(1); // 1 이끝나는 마지막
for (multimap<int, int>::iterator it = itPair.first; it != itpair.second; ++it)
{
cout << it->first << " " << it->second << endl;
}
for (multimap<int, int>::iterator it = itBegin; it != itEnd; ++it)
{
cout << it->first << " " << it->second << endl;
}
multiset<int> ms;
ms.insert(100);
ms.insert(100);
ms.insert(100);
ms.insert(200);
ms.insert(200);
ms.insert(200);
multiset<int>::iterator findIt = ms.find(100);
pair<multiset<set>::iterator, multiset<int>::iterator> itPair2;
itPair2 = ms.equal_range(100);
for(multiset<int>::iterator it = itPair2.first; it != it != itPair2.second; ++it)
{
cout << (*it) << endl;
}
multiset<int>::iterator itBegin = ms.lower_bound(100);
multiset<int>::iterator itEnd = ms.upper_bound(100);
for(multiset<int>::iterator it = itBegin; it != itEnd; ++it)
{
cout << (*it) << endl;
}
return 0;
}
Algorithm
이제까지 data sturcutre 를 알아봤다. 사용에 따라서, data 를 어떻게 생성해주고, 선언하는걸 알아보았다. 하지만 여기서 끝나는건 아니다 데이터를 만들었으면 가공도 해야되기때문에 c++ 에서는 algorithm 이라는 라이브러리가 있다. 대표적으로 사용되는 걸 알아보자.
- find
- find_if
- count
- count_if
- all_of
- any_of
- none_of
- for_each
- remove
- remove_if
위에서 사용한 method 를 아래와 같이 question 과 구현을 해보았다. 다만 remove 와 remove_if 를 조심하자! 이 둘은 결국 vector 안에서 중간 삭제나 처음 삭제가 일어나는데, 이때 먼저 필요한 데이터만 뽑아와서 복사를 한다음에, 복사 할필요 없는 element 도 복사 하니까, 실제 filtering 이 잘 안되어있을수 있다. 그래서 실제 return 값은 filtering 이 끝나는 위치(iterator)를 return 한다.
#include <algorithm>
#include <vector>
int main()
{
int number = 50;
// Q1 : Find the element if the number matches
std::vector<int>::iterator itFind = std::find(v.begin(), v.end(), number);
if (itFind == v.end())
{
cout << "not found" << endl;
}
else
{
cout << "Found" << endl;
}
// Q2 : check if the element in vector is divisible by 11.
struct CanDivideBy11
{
bool operator()(int n)
{
return (n % 11 == 0);
}
};
std::vector<int>::iterator itFind = std::find_if(v.begin(), v.end(), CanDvideBy11());
if (itFind == v.end())
{
cout << "not found" << endl;
}
else
{
cout << "Found" << endl;
}
// Q3 :find how many odd number is in vector
struct isOdd
{
bool operator()(int n)
{
return (n % 2) != 0;
}
};
std::vector<int>::iterator ifFind = std::count_if(v.begin(), v.end(), isOdd())
if (itFind == v.end())
{
cout << "not found" << endl;
}
else
{
cout << "Found" << endl;
}
// 모든 데이터 홀수?
bool b1 = std::all_of(v.begin(), v.end(), isOdd());
// 홀수인 데이터가 하나라도 있어?
bool b2 = std::any_of(v.begin(), v.end(), isOdd());
// 모든 데이터가 홀수가 아니야?
bool b3 = std::none_of(v.begin(), v.end(), isOdd());
// Q4 multiply three on every elements in a vector
struct MultiplyByThree
{
bool operator()(int &n)
{
n = n * 3;
}
};
std::for_each(v.begin(), v.end(), MultiplyByThree);
// Q5 remove all data which is an odd number
v.clear();
v.push_back(1);
v.push_back(4);
v.push_back(5);
v.push_back(2);
v.push_back(3);
vector<int>::iterator it = std::remove_if(v.begin(), v.end(), IsOdd());
v.erase(it, v.end());
// v.erase(std::remove_if(v.begin(), v.end(), IsOdd()), v.end());
return 0;
}
