STL (Standard Template Library)
프로그래밍할 때 필요한 자료구조/알고리즘들을 템플릿으로 제공하는 라이브러리
컨테이너 : 데이터를 저장하는 하나의 객체 (자료구조)
'어떤 원리로 작동하길래 배열을 유동적으로 사용할 수 있는 것인가?'
1) 여유분을 두고 메모리를 할당한다.
-> Q1. 여유분은 얼만큼이 적당한가?
2) 여유분까지 꽉 차면 메모리를 증설한다.
-> Q2. 얼마나 증설해야할까?
-> Q3. 증설 시, 기존의 데이터를 어떻게 처리할까?
size() : 현재 저장된 데이터의 개수
capacity() : 현재 동적 배열의 최대 크기
reserve() : capacity를 임의의 크기로 지정. (면접 질문: reserve 사용 이유? -> capacity가 증가할 때마다 복사에 의한 오버헤드가 일어나기 때문에 미리 넉넉하게 할당)
resize() : size를 임의의 크기로 지정. capacity도 자동으로 늘어난다. resize로 지정한 경우 push_back이 아닌 배열로 접근해서 데이터를 조작해야 한다. 생성자에서 지정해도 동일하게 작동한다.
컴파일러마다 다르지만 size가 capacity를 초과하면 capacity를 1.5배씩 증설시키며 크기를 동적으로 확장시킨다.
capacity는 늘어날지언정 줄어들지는 않는다. clear를 사용해도 줄어들지 않는다.
vector<int>().swap(v);
하지만 이런식으로 임시 vector와 교환 해서 capacity가 0인 것으로 돌려받는 방법은 있다.
보통은 이렇게까지 할 이유는 없어서 잘 이용되지 않는다.
반복자 (Iterator)
내부적으로는 포인터를 들고 있다.
vector뿐 아니라 다른 컨테이너에도 공통적으로 있는 개념이다.
const_iterator, reverse_iterator 등이 있다.
원소의 중간 삽입 및 삭제 : vector는 반드시 메모리 블록에 연속되어 있어야 하기 때문에 중간 삽입/삭제는 매우 비효율 적으로 동작한다. (오버헤드가 크게 발생)
insert와 erase로 삽입 및 삭제를 할 수 있다.
insert와 erase는 삽입/삭제한 원소의 위치 반복자를 반환해준다.
erase의 경우 end 범위는 삭제에 포함되지 않는다.
erase로 삭제된 iterator는 더 이상 해당 컨테이너에 속하지 않는다. (모든 정보가 NULL로 기록된다)
원소의 처음/끝 삽입 및 삭제 : 처음 원소의 삽입 및 삭제는 위와 같은 이유이지만 끝 원소의 삽입 및 삭제는 괜찮다.
원소의 임의 접근 : 가능
custom vector 간단하게 구현
더보기
#include <iostream>
#include <vector>
using namespace std;
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 _ptr != right._ptr; }
T& operator*() { return *_ptr; }
public:
T* _ptr;
};
template<typename T>
class Vector
{
public:
Vector() : _data(nullptr), _size(0), _capacity(0) {}
~Vector()
{
if (_data != nullptr)
delete[] _data;
}
void push_back(const T& val)
{
if (_size == _capacity)
{
int newCapacity = static_cast<int>(_capacity * 1.5f);
if (newCapacity == _capacity) newCapacity++;
reserve(newCapacity);
}
_data[_size] = val;
_size++;
}
void reserve(const int capacity)
{
_capacity = capacity;
T* newData = new T[_capacity];
for (int i = 0; i < _size; i++)
newData[i] = _data[i];
if (_data != nullptr)
delete[] _data;
_data = newData;
}
T& operator[](const int pos)
{
return _data[pos];
}
int size() const { return _size; }
int capacity() const { 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;
};
// vector (동적 배열)
// - vecotr의 동작 원리
// - 중간 삽입/삭제
// - 처음/끝 삽입/삭제
// - 임의 접근
int main()
{
Vector<int> v;
v.reserve(100);
for (int i = 0; i < 100; i++)
{
v.push_back(i);
cout << v.size() << " " << v.capacity() << endl;
}
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << endl;
}
cout << "------------------" << endl;
for (Vector<int>::iterator it = v.begin(); it != v.end(); ++it)
{
cout << *it << endl;
}
return 0;
}
clear를 구현하는 경우 데이터를 지울 필요 없이 그냥 size만 0으로 재설정 하면 된다.
