[C++] fixed_vector 크기 고정 벡터

필요해서 직접 만든 STL 호환 '크기 고정 벡터'입니다.

 

'동적 배열'을 사용하지 않고 굳이 fixed_vector라는 고정길이 벡터를 만든 이유는

 

기존 '동적 배열'은 매우 뛰어난 자료구조이지만 몇 가지 문제점이 있습니다.

1) 힙 메모리를 사용하기 때문에 스택 메모리에 비해 조금 느리다.

2) 재할당 발생 시 O(n)의 시간복잡도가 소모된다. (초기화시 큰 reserve 를 할당하면 해결 가능)

3) 잦은 재할당 발생시 메모리 파편화 현상이 문제가 될 수 있다.

 

그렇기 때문에 굳이 동적 배열이 필요하지 않은 경우에는 일반 '배열'을 사용하는 것이 더 유리할 경우가 있습니다.

 

그냥 배열을 쓰지 않고 fixed_vector를 만든 이유는

필요시 편리한 기능이나 오류 체크 같은 것을 하기 위함이고

최적화가 뛰어난 std::alogorithm의 명령어를 이용하기 위해서입니다.

 

포스팅아래에 GitHub 링크 및 헤더 파일 코드가 있습니다.

둘 다 동일한 코드이며, 헤더 파일로 사용하시면 됩니다.

직접 사용하다가 오류가 발견되면 업데이트될 수 있고

GitHub 쪽이 최신 코드입니다.

 

참고: 멀티스레드 환경을 고려하지 않고 만들어졌습니다.

 

개요

STL 컨테이너, vector와 사용법이 거의 동일합니다.

단, '동적 배열'이 아닌 '고정 길이 배열'입니다.

그렇기에 포인터로 관리하는 것이 아닌, 내부에서 일반 배열로 관리됩니다.

 

기존 std::vector와 거의 동일하게 사용할 수 있으며

초기화 방식은 array와 비슷합니다.

 

array의 size()가 항상 최대 size로 잡히는 것과 달리

해당 fixed_vector는 가지고 있는 요소만큼만 size가 잡히며

최대 용량은 capacity로 관리합니다.

 

 

다른 STL 컨테이너와 섞어서 사용해도 작동합니다.

하지만 아직 기능이 완벽하지 않을 수 있습니다.

 

버그는 사용하면서 차차 고쳐나갈 생각입니다.

 

iterator와 const_iterator를 가지고 있기에

STL 알고리즘과 호환도 가능합니다.

 

스마트 포인터를 인자로 몇 번 사용해 봤는데, 이상 없이 잘 작동했습니다.

 

추가적인 버그나 오류를 발견하면 주기적으로 업데이트할 계획입니다.

 

 

https://github.com/powercrabman/Cpp_fixed_vector.header/tree/main

GitHub - powercrabman/Cpp_fixed_vector.header

 

#pragma once

/* fixed vector */

#include <initializer_list>
#include <type_traits>
#include <cassert>
using namespace std;

template <typename Ty, size_t FIXED_SIZE>
class fv_iterator {
public:
	using iterator_category = std::random_access_iterator_tag;
	using value_type = Ty;
	using reference = Ty&;
	using pointer = Ty*;
	using difference_type = std::ptrdiff_t;

public:
	fv_iterator(pointer p = nullptr) : _ptr(p) {}
	~fv_iterator() = default;
	fv_iterator(const fv_iterator&) = default;
	fv_iterator& operator=(const fv_iterator&) = default;

	bool operator==(const fv_iterator& other) const { return other._ptr == _ptr; }
	bool operator!=(const fv_iterator& other) const { return other._ptr != _ptr; }
	bool operator<(const fv_iterator& other) const { return _ptr < other._ptr; }
	bool operator>(const fv_iterator& other) const { return _ptr > other._ptr; }
	bool operator<=(const fv_iterator& other) const { return _ptr <= other._ptr; }
	bool operator>=(const fv_iterator& other) const { return _ptr >= other._ptr; }
	reference operator*() const { return *_ptr; }
	pointer operator->() const { return _ptr; }
	fv_iterator& operator++() {
		++_ptr;
		return *this;
	}
	fv_iterator operator++(int) {
		fv_iterator temp = *this;
		++(*this);
		return temp;
	}
	fv_iterator& operator--() {
		--_ptr;
		return *this;
	}
	fv_iterator operator--(int) {
		fv_iterator temp = *this;
		--(*this);
		return temp;
	}
	fv_iterator& operator+=(difference_type n) {
		_ptr += n;
		return *this;
	}
	fv_iterator& operator-=(difference_type n) {
		_ptr -= n;
		return *this;
	}

	fv_iterator operator+(int n) {
		return _ptr + n;
	}

	fv_iterator operator-(int n) {
		return _ptr - n;
	}

	reference operator[](difference_type n) const {
		return *(*this + n);
	}

	difference_type operator-(const fv_iterator& rhs) const {
		return _ptr - rhs._ptr;
	}

private:
	pointer _ptr;
};


template <typename Ty, size_t FIXED_SIZE>
class fixed_vector final
{
public:
	using value_type = Ty;
	using reference = Ty&;
	using const_reference = const Ty&;
	using pointer = Ty*;
	using const_pointer = const Ty*;
	using difference_type = std::ptrdiff_t;
	using size_type = std::size_t;

	using iterator = fv_iterator<Ty, FIXED_SIZE>;
	using const_iterator = fv_iterator<const Ty, FIXED_SIZE>;
	using alloc_ptr = Ty*;

public:
	/*Constructor*/
	fixed_vector() = default;
	fixed_vector(std::initializer_list<Ty>&& initializer);
	fixed_vector(size_t size, Ty defaultItem = Ty());

	template<size_t OTHER_SIZE>
	fixed_vector(const fixed_vector<Ty, OTHER_SIZE>& other);

	template<size_t OTHER_SIZE>
	fixed_vector(fixed_vector<Ty, OTHER_SIZE>&& other) noexcept;

	/*Destructor*/
	~fixed_vector() {} ;

	/*Copy & Move*/
	template<size_t OTHER_SIZE>
	fixed_vector& operator=(const fixed_vector<Ty, OTHER_SIZE>& other);

	fixed_vector& operator=(const std::initializer_list<Ty>& initializer);


	template<size_t OTHER_SIZE>
	fixed_vector& operator=(fixed_vector<Ty, OTHER_SIZE>&& other);

	Ty& operator[](size_t idx) { assert(idx < _size);  return _alloc[idx]; }
	Ty& at(size_t idx) { assert(idx < _size);  return _alloc[idx]; }

	const Ty& operator[](size_t idx) const { assert(idx < _size);  return _alloc[idx]; }
	const Ty& at(size_t idx) const { assert(idx < _size);  return _alloc[idx]; }


	bool full() const { return _size == _capacity; }
	bool empty() const { return _size == 0; }

public:
	void push_back(const Ty& item);
	void pop_back() { assert(_size != 0); --_size; }

	Ty back() const { assert(_size != 0);  return _alloc[_size - 1]; }
	Ty front() const { assert(_size != 0); return _alloc[0]; }

	void resize(size_t nSize, Ty defaultItem = Ty())
	{
		assert(nSize <= FIXED_SIZE);

		if (nSize > _size)
		{
			for (size_t i = _size; i < nSize; ++i)
				push_back(defaultItem);
		}
		else if (nSize < _size)
		{
			_size = nSize;
		}
	}

	void swap(fixed_vector& other) { ::swap(_alloc, other._alloc); ::swap(_size, other._size); }
	
	void clear() {
		_size = 0;
	}

	iterator insert(iterator pos, const Ty& item) {
		assert(_size < _capacity);
		auto index = pos - begin();
		assert(index >= 0 && index <= _size);

		for (size_t i = _size; i > index; --i)
			_alloc[i] = _alloc[i - 1];

		_alloc[index] = item;
		++_size;

		return begin() + index;
	}
	iterator erase(iterator pos) {
		auto index = pos - begin();
		assert(index >= 0 && index < _size);

		for (size_t i = index; i < _size - 1; ++i)
			_alloc[i] = _alloc[i + 1];

		--_size;

		return begin() + index;
	}

	iterator erase(iterator first, iterator last) {
		auto index = first - begin();
		assert(index >= 0 && index < _size);

		auto eraseCount = last - first;
		for (size_t i = index; i < _size - eraseCount; ++i)
			_alloc[i] = _alloc[i + eraseCount];

		_size -= eraseCount;

		return begin() + index;
	}

	void assign(size_t nSize, const Ty& item) {
		assert(nSize <= _capacity);

		clear();

		for (size_t i = 0; i < nSize; ++i)
			push_back(item);
	}
	void assign(::initializer_list<Ty> initializer) {
		assert(initializer.size() <= _capacity);

		clear();

		for (const Ty& item : initializer)
			push_back(item);
		
	}
	template <typename Iter>
	void assign(Iter first, Iter last)
	{
		size_t nSize = std::distance(first, last);
		assert(nSize >= 0);
		assert(nSize <= _capacity);

		clear();

		for (size_t i = 0; i < nSize; ++i)
		{
			push_back(*first);
			++first;
		}
	}

	iterator begin() { return iterator(_alloc); }
	iterator end() { return iterator(_alloc + _size); }

	const_iterator begin() const { return const_iterator(_alloc); }
	const_iterator end() const { return const_iterator(_alloc + _size); }

	const_iterator cbegin() const { return const_iterator(_alloc); }
	const_iterator cend() const { return const_iterator(_alloc + _size); }


	size_t size() const { return _size; }
	size_t max_size() const { return FIXED_SIZE; }
	size_t capacity() const { return _capacity; }


private:

	Ty				_alloc[FIXED_SIZE];
	size_t			_size = 0;
	size_t			_capacity = FIXED_SIZE;
};

inline bool cmpRef(const void* left, const void* right)
{
	return left == right;
}


template<typename Ty, size_t FIXED_SIZE>
inline fixed_vector<Ty, FIXED_SIZE>::fixed_vector(std::initializer_list<Ty>&& initializer)
	: _size(initializer.size())
{
	assert(FIXED_SIZE >= initializer.size());

	size_t i = 0;
	for (const Ty& item : initializer)
	{
		_alloc[i] = item;
		++i;
	}
}

template<typename Ty, size_t FIXED_SIZE>
inline fixed_vector<Ty, FIXED_SIZE>::fixed_vector(size_t size, Ty defaultItem)
	: _size(size)
{
	assert(FIXED_SIZE >= size);

	for (size_t i = 0; i < _size; i++)
		_alloc[i] = defaultItem;
}

template<typename Ty, size_t FIXED_SIZE>
inline fixed_vector<Ty, FIXED_SIZE>& fixed_vector<Ty, FIXED_SIZE>::operator=(const std::initializer_list<Ty>& initializer)
{
	assert(FIXED_SIZE >= initializer.size());

	clear();
	_size = initializer.size();

	size_t i = 0;
	for (const Ty& item : initializer)
	{
		_alloc[i] = item;
		++i;
	}

	return *this;
}

template<typename Ty, size_t FIXED_SIZE>
template<size_t OTHER_SIZE>
inline fixed_vector<Ty, FIXED_SIZE>& fixed_vector<Ty, FIXED_SIZE>::operator=(const fixed_vector<Ty, OTHER_SIZE>& other)
{
	assert(FIXED_SIZE >= other.size());

	if (!cmpRef(this, &other))
	{
		clear();
		_size = other.size();

		for (size_t i = 0; i < _size; i++)
			_alloc[i] = other[i];
	}

	return *this;
}

template<typename Ty, size_t FIXED_SIZE>
template<size_t OTHER_SIZE>
inline fixed_vector<Ty, FIXED_SIZE>& fixed_vector<Ty, FIXED_SIZE>::operator=(fixed_vector<Ty, OTHER_SIZE>&& other)
{
	assert(FIXED_SIZE >= other.size());

	if (!cmpRef(this, &other))
	{
		clear();
		_size = other.size();

		for (size_t i = 0; i < _size; i++)
			_alloc[i] = other[i];

		other.clear();
	}

	return *this;
}

template<typename Ty, size_t FIXED_SIZE>
template<size_t OTHER_SIZE>
inline fixed_vector<Ty, FIXED_SIZE>::fixed_vector(const fixed_vector<Ty, OTHER_SIZE>& other)
	: _size(other.size())
{
	assert(FIXED_SIZE >= other.size());

	for (size_t i = 0; i < _size; i++)
		_alloc[i] = other[i];
}

template<typename Ty, size_t FIXED_SIZE>
template<size_t OTHER_SIZE>
inline fixed_vector<Ty, FIXED_SIZE>::fixed_vector(fixed_vector<Ty, OTHER_SIZE>&& other) noexcept
	: _size(other.size())
{
	assert(FIXED_SIZE >= other.size());

	for (size_t i = 0; i < _size; i++)
		_alloc[i] = other[i];

	other.clear();
}

template<typename Ty, size_t FIXED_SIZE>
inline void fixed_vector<Ty, FIXED_SIZE>::push_back(const Ty& item)
{
	assert(_size < _capacity);
	_alloc[_size] = item;
	++_size;
}