개발하는 리프터 꽃게맨입니다.
[C++/STL] vector 컨테이너 설계 코드 본문
template <typename T>
class Iterator
{
public:
Iterator(T* item)
: _item(item)
{}
public:
T* operator++()
{
return ++_item;
}
T* operator--()
{
return --_item;
}
T* operator+(int idx)
{
return _item + idx;
}
T* operator-(int idx)
{
return _item - idx;
}
int& operator*()
{
return *_item;
}
int& operator->()
{
return *_item;
}
bool operator==(const Iterator& other) const
{
return _item == other._item;
}
bool operator!=(const Iterator& other) const
{
return _item != other._item;
}
bool operator>(const Iterator& other) const
{
return _item > other._item;
}
bool operator<(const Iterator& other) const
{
return _item < other._item;
}
bool operator>=(const Iterator& other) const
{
return _item >= other._item;
}
bool operator<=(const Iterator& other) const
{
return _item <= other._item;
}
private:
T* _item;
};
template <typename T>
class Vector
{
public:
using Iterator = Iterator<T>;
public:
Vector() //기본 생성자
{
_allocator = new T[_capacity];
}
Vector(size_t size, T defaultItem = T()) //생성자 오버로딩, 사이즈 + 디폴트 값으로 초기화
{
_size = size;
_capacity = _size;
_allocator = new T[_capacity];
for (int i = 0; i < _size; i++)
_allocator[i] = defaultItem;
}
Vector(initializer_list<T> list) //생성자 오버로딩, 리스트로 초기화
{
_size = list.size();
_capacity = list.size();
_allocator = new T[_capacity];
copy(list.begin(), list.end(), _allocator);
}
Vector(Vector& other) //생성자 오버로딩, 복사 생성자
{
_size = other.size();
_capacity = other.size();
_allocator = new T[_capacity];
copy(other._allocator, other._allocator + _size, _allocator);
}
~Vector() //소멸자
{
delete[] _allocator;
}
public: //연산자 오버로딩 + bool 함수
int& operator[](size_t idx) //idx 연산자
{
assert(idx >= 0 && idx < _size);
return _allocator[idx];
}
Vector& operator=(const Vector& other)
{
assert(_allocator != nullptr);
if (this != &other)
{
delete[] _allocator;
_size = other._size;
_capacity = other._capacity;
_allocator = new T[_capacity];
copy(other._allocator, other._allocator + _size, _allocator);
}
return *this;
}
bool empty() const { return _size == 0; }
public: //public 함수
void push_back(int item) //삽입, push_back 함수
{
if (full())
reallocator();
_allocator[_size] = item;
_size++;
}
void pop_back() //팝, pop_back 함수
{
assert(!empty());
_size--;
}
int back() const//맨 뒤 요소를 리턴하는 함수
{
assert(!empty());
return _allocator[_size - 1];
}
void reserve(size_t capacity) //용량을 늘리는 함수
{
if (capacity > _capacity)
{
_capacity = capacity;
T* newallocator = new T[_capacity];
for (int i = 0; i < _size; i++)
newallocator[i] = _allocator[i];
delete[] _allocator;
_allocator = newallocator;
}
else
{
//굳이 메모리를 이주해야할 필요가 없음
_capacity = capacity;
if (_capacity < _size) //만약 _capacity가 _size보다 작다면, _size를 _capacity만큼 줄여줘야함
_size = _capacity;
}
}
void resize(size_t size, int defaultItem = 0) //사이즈를 재조절하는 함수
{
if (size > _capacity)
{
//재할당필요
T* newallocator = new T[size];
for (int i = 0; i < _size; i++)
newallocator[i] = _allocator[i];
for (int i = _size; i < size; i++)
newallocator[i] = defaultItem;
_size = size;
_capacity = size;
delete[] _allocator;
_allocator = newallocator;
}
else
{
if (_size < size)
{
for (int i = _size; i < size; i++)
_allocator[i] = defaultItem;
}
_size = size;
}
}
Iterator begin() const
{
return Iterator(_allocator);
}
Iterator end() const
{
return Iterator(_allocator + _size);
}
//원하는 주소에 삽입
Iterator insert(Iterator it, int item)
{
//오류 체크
assert(it >= begin() && it < end());
int offset = 0;
//만약 배열이 꽉 찼으면 reallocate
if (full())
{
//주소가 바뀌기 때문에 it를 다시 계산해줘야함
for (Iterator i = begin(); i != it; ++i) offset++;
reallocator();
it = begin() + offset;
}
//들어갈 공간 만들어주기
for (Iterator i = end(); i != it; --i)
*i = *(i - 1);
*it = item;
_size++;
return it;
}
//원하는 주소 삭제
Iterator erase(Iterator it)
{
assert(it >= begin() && it < end());
Iterator dest = it;
for (Iterator i = it + 1; i != end(); ++i, ++dest)
*(dest) = *(i);
_size--;
return dest;
}
//원하는 주소 범위 삭제
Iterator erase(Iterator from, Iterator to)
{
assert(from >= begin() && from < end());
assert(to >= begin() && to <= end());
assert(from <= to);
size_t rangeSize = 0;
//from ~ to 까지 포인트 거리 측정
for (Iterator i = from; i != to; ++i)
rangeSize++;
Iterator dest = from;
for (Iterator i = to; i != end(); ++i, ++dest)
*dest = *i;
_size -= rangeSize;
return from;
}
void clear()
{
delete[] _allocator;
_size = 0;
_allocator = new T[_capacity];
}
void assign(initializer_list<T> list)
{
//size가 0이면 clear 처리
if (list.size() == 0)
{
clear();
return;
}
if (_capacity < list.size())
{
_size = list.size();
_capacity = list.size();
delete[] _allocator;
_allocator = new T[_capacity];
::copy(list.begin(), list.end(), _allocator);
}
else
{
_size = list.size();
::copy(list.begin(), list.end(), _allocator);
}
}
void assign(Iterator first, Iterator last)
{
size_t newSize = 0;
// from ~ to 까지 포인트 거리 측정
for (Iterator i = first; i != last; ++i)
newSize++;
// size 0 일경우 clear 처리
if (newSize == 0)
{
clear();
return;
}
if (_capacity < newSize)
{
_size = newSize;
_capacity = newSize;
delete[] _allocator;
_allocator = new T[_capacity];
Iterator idx = begin();
//왜인지 std::copy 가 안되서 직접 만들어 줬습니다.
for (Iterator i = first; i != last; ++i, ++idx)
*idx = *i;
}
else
{
_size = newSize;
Iterator idx = begin();
for (Iterator i = first; i != last; ++i, ++idx)
*idx = *i;
}
}
void assign(size_t size, T defaultItem = T())
{
if (size == 0)
{
clear();
return;
}
if (_capacity < size)
{
_size = size;
_capacity = size;
delete[] _allocator;
_allocator = new T[_capacity];
for (int i = 0; i < size; i++)
_allocator[i] = defaultItem;
}
else
{
_size = size;
Iterator idx = begin();
for (int i = 0; i < size; i++)
_allocator[i] = defaultItem;
}
}
void swap(Vector<T>& other)
{
if (this != &other)
{
int tempSize = _size;
int tempCap = _capacity;
T* tempAll = _allocator;
_size = other._size;
_capacity = other._capacity;
_allocator = other._allocator;
other._size = tempSize;
other._capacity = tempCap;
other._allocator = tempAll;
}
}
int size() const { return _size; } //getter
int capacity() const { return _capacity; } //getter
private: //내부 함수
void reallocator() //메모리 재할당 함수
{
_capacity = _capacity << 1;
T* newallocator = new T[_capacity];
for (int i = 0; i < _size; i++)
newallocator[i] = _allocator[i];
delete[] _allocator;
_allocator = newallocator;
}
bool full() const { return _size == _capacity; }
private:
T* _allocator;
int _size = 0;
int _capacity = 2;
};
STL 컨테이너인 vector 컨테이너를 C++ 코드로 구현해봤습니다.
제가 코드 짜는 실력이 형편없어서 그렇게 좋은 코드는 아니라고 봅니다.
그래도 80% 정도는 STL vector를 흉내낼 수 있습니다.
iterator, push_back, back, [], reserve, resize, assign, erase, insert, begin, end, pop_back, clear 등
개발에 흔히 사용하는 기능들은 다 구현했습니다.
아직 테스트를 많이 거치지 않아서 오류가 날 수 있습니다.
그래도 꽤나 기존 vector 와 유사하게 사용할 수 있는 코드입니다.
'자료구조 > 자료구조 설계' 카테고리의 다른 글
게임을 위한 자료구조 - 빠른 순회, 빠른 삽입, 빠른 삭제, 빠른 탐색 (3) | 2024.09.28 |
---|---|
게임을 위한 자료구조) 빠른 순회, 빠른 탐색, 빠른 삭제, 빠른 삽입 설계도 (1) | 2024.09.27 |
Reservable Queue (0) | 2024.08.05 |