Vector Data Structure

벡터의 임의 접근은 시간 복잡도가 O(1)이다.

벡터의 크기를 확장할 때, 복사(이동)가 일어나므로 선형 시간이 소요된다. 만약 사용하려는 벡터의 사이즈를 어느정도 알고 있다면 크기를 미리 정해주는 것이 좋다.

 

벡터의 구현

• 멤버 변수 : 힙메모리의 위치를 가리키는 포인터, current size(size), max size(capacity)
• 함수 : front, back, size, capacity, push_back, pop_back
• 생성자, 소멸자

#pragma once

#include <iostream>

template<typename T>
class MyVector {
public:
	MyVector(const int& _maxCapacity = 10) {
		currentSize_ = 0;
		maxCapacity_ = _maxCapacity;
		data_ = new T[maxCapacity_];
	}

	~MyVector() {
		if (nullptr != data_) {
			delete[] data_;
			data_ = nullptr;
		}
	}

	void push_back(const T& _data);
	void pop_back();
	T& front() const;
	T& back() const;
	T& at(const int& _index) const;
	bool empty() const;
	int size() const;
	int capacity() const;

	T& operator[](const int& _index) const;

private:
	void realloc();

private:
	T* data_;

	int currentSize_;
	int maxCapacity_;
};

template<typename T>
inline void MyVector<T>::push_back(const T& _data)
{
	if (currentSize_ == maxCapacity_)
		realloc();

	data_[currentSize_++] = _data;
}

template<typename T>
inline void MyVector<T>::pop_back()
{
	if (currentSize_ > 0)
		--currentSize_;
}

template<typename T>
inline T& MyVector<T>::front() const
{
	if (currentSize_ > 0)
		return data_[0];

	throw std::out_of_range("vector out of range");
}

template<typename T>
inline T& MyVector<T>::back() const
{
	if (currentSize_ > 0)
		return data_[currentSize_ - 1];

	throw std::out_of_range("vector out of range");
}

template<typename T>
inline T& MyVector<T>::at(const int& _index) const
{
	if (_index < currentSize_)
		return data_[_index];

	throw std::out_of_range("vector out of range");
}

template<typename T>
inline bool MyVector<T>::empty() const
{
	return currentSize_ == 0;
}

template<typename T>
inline int MyVector<T>::size() const
{
	return currentSize_;
}

template<typename T>
inline int MyVector<T>::capacity() const
{
	return maxCapacity_;
}

template<typename T>
inline T& MyVector<T>::operator[](const int& _index) const
{
	return at(_index);
}

template<typename T>
inline void MyVector<T>::realloc()
{
	T* newData = new T[maxCapacity_ * 2];

	for (int i = 0; i < currentSize_; ++i)
		newData[i] = std::move(data_[i]);

	delete[] data_;
	data_ = newData;

	maxCapacity_ *= 2;
}

 

Ver.2

#include "GlobalDefine.h"

template<typename _Ty>
class MyVector {
public:
	MyVector() :
		currentSize_(0),
		maxCapacity_(0),
		data_(nullptr)
	{}

	explicit MyVector(const int& _maxCapacity, const _Ty& _ty = _Ty()) :
		currentSize_(0),
		maxCapacity_(_maxCapacity),
		data_(nullptr)
	{
		data_ = new _Ty[_maxCapacity];

		for (int i = 0; i < _maxCapacity; ++i)
			push_back(_ty);
	}

	explicit MyVector(const MyVector& _vec) :
		currentSize_(0),
		maxCapacity_(_vec.maxCapacity_),
		data_(nullptr)
	{
		this->operator=(_vec);
	}

	//explicit MyVector(MyVector&& _vec) noexcept :
	//	currentSize_(_vec.currentSize_),
	//	maxCapacity_(_vec.maxCapacity_),
	//	data_(_vec.data_)
	//{
	//	this->operator=(std::forward<_Ty>(_vec));
	//}

	~MyVector()
	{
		if (nullptr != data_) {
			delete[] data_;
			data_ = nullptr;
		}
	}

public:
	MyVector& operator=(const MyVector& _vec)
	{
		maxCapacity_ = _vec.maxCapacity_;
		data_ = new _Ty[_vec.maxCapacity_];

		for (int i = 0; i < _vec.maxCapacity_; ++i)
			push_back(_vec[i]);
	}

	//MyVector& operator=(MyVector&& _vec) noexcept
	//{
	//	/* 수정해야됨. 주소만 들고오는게 아니라 전체 요소를 move? */
	//	currentSize_ = _vec.currentSize_;
	//	maxCapacity_ = _vec.maxCapacity_;
	//	data_ = _vec.data_;

	//	_vec.currentSize_ = 0;
	//	_vec.maxCapacity_ = 0;
	//	_vec.data_ = nullptr;
	//}

	_Ty& operator[](const int& _idx) const
	{
		return this->at(_idx);
	}

public:
	void push_back(const _Ty& _data)
	{
		if (currentSize_ >= maxCapacity_) {
			if (maxCapacity_ < 2)
				++maxCapacity_;
			else
				maxCapacity_ += maxCapacity_ / 2;

			_Ty* newData = new _Ty[maxCapacity_];
			for (int i = 0; i < currentSize_; ++i) {
				newData[i] = data_[i];
			}
			if (data_)
				delete[] data_;

			data_ = newData;
		}
		data_[currentSize_] = _data;
		++currentSize_;
	}

	void emplace_back(const _Ty& _data)
	{
		push_back(_data);
	}

	void emplace_back(_Ty&& _data) noexcept
	{
		if (currentSize_ < maxCapacity_) {
			data_[currentSize_] = std::move(_data);
			++currentSize_;
		}
		else
			push_back(_data);
	}

	void pop_back()
	{
		if (!empty()) --currentSize_;
	}

	_Ty& front() const
	{
		if (currentSize_ <= 0) abort();
		return at(0);
	}

	_Ty& back() const
	{
		if (currentSize_ <= 0) abort();
		return at(currentSize_ - 1);
	}

	_Ty& at(const int& _index) const
	{
		if (_index > currentSize_) abort();
		return *(data_ + _index);
	}

	bool empty() const
	{
		return currentSize_ <= 0;
	}

	int size() const
	{
		return currentSize_;
	}

	int capacity() const
	{
		return maxCapacity_;
	}

private:
	_Ty* data_;

	int currentSize_;
	int maxCapacity_;
};

 

algorithm 헤더가 제공하는 find 함수는 선형 탐색이다.

search 함수는 두 컨테이너 또는 배열을 비교하여 연속된 데이터가 존재하는 첫 번째 위치를 반환한다.