벡터의 임의 접근은 시간 복잡도가 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 함수는 두 컨테이너 또는 배열을 비교하여 연속된 데이터가 존재하는 첫 번째 위치를 반환한다.
'이론 > 자료구조&알고리즘' 카테고리의 다른 글
| Recursion Basics (0) | 2023.02.09 |
|---|---|
| Bit Manipulation (0) | 2023.02.09 |
| Pointers & Dynamic Memory (0) | 2023.02.07 |
| 2D Arrays (0) | 2023.02.07 |
| Character Arrays/Strings (0) | 2023.02.03 |
