[ C++ / STL ] Vector 구현해 보기

Vector

 

• 가장 많이 쓰이는 STL 컨테이너이다.

• 랜덤 억세스가 가능하다.

 

소 스  코 드

//////////////////////////////////////////////////////////////////////////////////////////
// Kwon O Sung
// Vector 
//////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <string>
#include <algorithm>
#include <fstream>

typedef __int64 INT;

template<typename T>
class VECTOR {
private:
	T * data;		// 내부 데이터
	INT capacity;	// 총 크기 
	INT size;		// 현재 데이터 사이즈

public:
	// 기본 생성자
	VECTOR(const int n = 1) : capacity{ n }, size{ 0 }, data{ new T[n] } {
	}

	// 소 멸 자
	~VECTOR() {
		if (nullptr != data) delete[] data;
	}

	// 복사 생성자
	VECTOR(const VECTOR& other) {
		if (other.capacity == capacity) {
			size = other.size;
		}
		else {
			if (nullptr != data) delete[] data;
			capacity = other.capacity;
			size = other.size;
			data = new T[capacity];
		}

		std::memcpy(data, other.data, sizeof(T)* size);
	}

	// 이동 생성자
	VECTOR(VECTOR && other) noexcept : capacity{ other.capacity }, size{ other.size }, data{ other.data } {
		other.size = 0;
		other.capacity = 1;
		other.data = new T[other.capacity];
	}

	// 복사 할당 연산자
	VECTOR& operator=(const VECTOR& other) {
		if (this == &other) return *this;
		if (nullptr != data) delete[] data;

		capacity = other.capacity;
		size = other.size;
		data = new T[capacity];

		for (INT i = 0; i < size; ++i) data[i] = other.data[i];
		return *this;
	}

	// 이동 할당 연산자
	VECTOR& operator =(VECTOR &&other) noexcept {
		if (this == &other) return *this;
		if (nullptr != data) delete[] data;
		capacity = other.capacity;
		size = other.size;
		data = other.data;

		other.size = 0;
		other.capacity = 1;
		other.data = new T[other.capacity];
		return *this;
	}

public:
	
	// Emplace_Back : 뒤에 넣기(이동)		
	void Push_Back(const T&);								// Push_Back : 뒤에 넣기(복사)
	// template<typename ... TYPE>
	// void Emplace_Back(TYPE... arg);
	void Clear();											// Clear
	void Reserve(const INT&);								// Reserve : 용량 할당 [ Reserve 한 후에 크기가 증가할 때는 Capacity * ( 2 / 3 ), 내림 ]
	void Resize(const INT&);								// Resize : 용량 할당 후 사이즈 만큼 채운다.
	bool Empty() const;										// Empty : 비어있는지 확인
	INT Size() const;										// Get 크기 함수
	INT Capacity() const;									// Get 용량 함수
	void Swap(VECTOR<T>& other);

	void Sort();											// 오름차순
	void Erase(const INT&, const INT&);						// 인덱스로 범위 지우기
	void Erase(const INT&);									// 인덱스로 하나 지우기


	// 다른 곳에도 사용하는 함수들
	T* begin() const;										// 시작 주소
	T* end() const;											// 끝 주소

	T& front() const;										// 맨 앞
	T& back() const;										// 맨 뒤


	// Operator
	T operator[](const INT&) const;							// 읽기 
	T& operator[] (INT);									// 쓰기
	
	friend std::ostream & operator << (std::ostream&, const VECTOR &); // Ostream : 출력
};

//////////////////////////////////////////////////////////////////////////////////////////
// 메인 문 
int main(int argc, char* argv[]) {
	std::ofstream os;
	
	os.open("Log.txt");
	
	if (os) {
		os << " VECTOR TEST LOG SAVE \n" ;
	}

	VECTOR<int> i1;
	VECTOR<std::string> s1;

	os << " 템플릿을 통한 제네릭한 클래스 생성 확인 [ Push_Back ] \n";

	for (int i = 50; i > 0; --i) i1.Push_Back(i + 1);

	s1.Push_Back(" VECTOR ");
	s1.Push_Back(" TEST ");
	s1.Push_Back(" LOG ");
	s1.Push_Back(" SAVE ");

	os << "\n Int Vector  : ";
	for (const auto& a : i1) os << a << ' ';
	os << "\n String Vector : ";
	for (const auto& a : s1) os << a << ' ';

	os << "\n\n Int Vector 용량 : " << i1.Capacity() << ", " << i1.Size() << '\n';
	os << " String Vector 용량 : " << s1.Capacity() << ", " << s1.Size() << '\n';

	// 오름차순으로 정렬
	s1.Sort();
	i1.Sort();
	os << "\n 오름차순으로 정렬 \n Int Vector  : ";
	for (const auto& a : i1) os << a << ' ';
	os << "\n String Vector : ";
	for (const auto& a : s1) os << a << ' ';

	VECTOR<int> i2;
	VECTOR<std::string> s2;

	i2.Push_Back(3);
	s2.Push_Back(" Hello World !");

	i1.Swap(i2);
	s1.Swap(s2);

	os << "\n\n Swap 함수 \n Int Vector i1 : ";
	for (const auto& a : i1) os << a << ' ';
	os << "\n Int Vector i2 : ";
	for (const auto& a : i2) os << a << ' ';

	os << "\n String Vector s1 : ";
	for (const auto& a : s1) os << a << ' ';
	os << "\n String Vector s2 : ";
	for (const auto& a : s2) os << a << ' ';

	os << "\n Erase 0 ~ 3 : ";
	i2.Erase(0, 3);
	s2.Erase(0, 3);
	os << "\n String Vector i2 : ";
	for (const auto& a : i2) os << a << ' ';
	os << "\n String Vector s2 : ";
	for (const auto& a : s2) os << a << ' ';

	os << "\n Erase 0 : ";
	i2.Erase(0);
	s2.Erase(0);
	os << "\n String Vector i2 : ";
	for (const auto& a : i2) os << a << ' ';
	os << "\n String Vector s2 : ";
	for (const auto& a : s2) os << a << ' ';

	os << "\n\n Int Vector 용량 : " << i2.Capacity() << ", " << i2.Size() << '\n';
	os << " String Vector 용량 : " << s2.Capacity() << ", " << s2.Size() << '\n';

	os.close();

	return 0;
}

/////////////////////////////////////////////////////////////////////////////////////////////
// Class
// Push_Back : 뒤에 넣기(복사)
template<typename T>
void VECTOR<T>::Push_Back(const T & other)
{
	if (capacity <= size) {
		T *temp{ nullptr };
		if (9 > capacity) {
			++capacity;
			temp = new T[capacity];
		}
		else { // * (( / 2 ) * 3)
			
			capacity = static_cast<int>((static_cast<float>(capacity) * 1.5f));
			temp = new T[capacity];
		}

		for (INT i = 0; i < size; ++i) temp[i] = data[i];
		// 많은 수가 들어갈 경우 속도를 생각하여 memcpy를 사용하였지만 String 같은 불규칙적인 크기를 가지고 있는 배열을 가지고 있을 경우 
		// 크기에 문제에 따라 잘못된 Heap 접근으로 인하여 Heap에 관련한 오류가 나올 수 있다.
		//std::memcpy(temp, data, sizeof(T)* size);
		temp[size] = other;
		++size;

		if (nullptr != data) delete[] data;
	
		data = temp;
	}
	else {
		data[size] = other;
		++size;
	}
}

template<typename T>
void VECTOR<T>::Clear()
{
	if (nullptr != data) delete[] data;
	capacity = 1;
	size = 0;
	data = new T[capacity];
}

template<typename T>
void VECTOR<T>::Reserve(const INT& num)
{
	if (num <= capacity) return;
	capacity = num;
	T *temp{ new T[capacity] };

	if (size != 0) {
		for (INT i = 0; i < size; ++i) temp[i] = data[i];
		if (nullptr != data) delete[] data;
	}
	
	data = temp;
}

template<typename T>
void VECTOR<T>::Resize(const INT & num)
{
	if (num <= capacity) {
		for (INT i = size; i < num; ++i) data[i] = NULL;
		size = num;
	}
	else {
		Reserve(num);
		for (INT i = size; i < num; ++i) data[i] = NULL;
		size = num;
	}
}



template<typename T>
bool VECTOR<T>::Empty() const
{
	return (size < 1);
}

template<typename T>
void VECTOR<T>::Swap(VECTOR<T>& other)
{
	VECTOR<T> temp(other);

	other = std::move(*this);
	*this = std::move(temp);
}

template<typename T>
void VECTOR<T>::Sort()
{
	std::sort(begin(), end(), [](const T& left, const T& right) {return left < right; });
}

template<typename T>
void VECTOR<T>::Erase(const INT & start, const INT & end)
{
	if (end > size || start < 0) return;

	T *temp = new T[capacity];
	
	INT index{ 0 };
	for (INT i = 0; i < start; ++i) {
		temp[index] = data[i];
		++index;
	}
	for (INT i = end; i < size; ++i) {
		temp[index] = data[i];
		++index;
	}
	size = index;
	
	if (nullptr != data) delete[] data;

	data = temp;
}

template<typename T>
void VECTOR<T>::Erase(const INT & index)
{

	if (index > size || index < 0) return;

	T *temp = new T[capacity];

	INT count{ 0 };
	for (INT i = 0; i < index; ++i) {
		temp[count] = data[i];
		++count;
	}
	for (INT i = index + 1; i < size; ++i) {
		temp[count] = data[i];
		++count;
	}
	size = count;

	if (nullptr != data) delete[] data;

	data = temp;
}


// OPEATOR

// [] Operator : v[1] 
template<typename T>
T VECTOR<T>::operator[](const INT & index)const
{
	if (size < index) exit(1);
	else return *(data + index);
}

template<typename T>
T & VECTOR<T>::operator[](INT index)
{
	return *(data + index);
}

template<typename T>
std::ostream & operator << (std::ostream& os, const VECTOR<T> & rhs)
{
	os << "Capacity : " << rhs.capacity << " | Size : " << rhs.size << '\n';
	for (INT i = 0; i < rhs.size; ++i) os << rhs.size << " ";
	return os;
}

///////////////////////////////////////////////////////////////////////////
// Get 함수들
template<typename T>
INT VECTOR<T>::Size() const
{
	return size;
}

template<typename T>
INT VECTOR<T>::Capacity() const
{
	return capacity;
}


template<typename T>
T * VECTOR<T>::begin() const
{
	return data;
}

template<typename T>
T * VECTOR<T>::end() const
{
	return data + size;
}

template<typename T>
T & VECTOR<T>::front() const
{
	return data[0];
}

template<typename T>
T & VECTOR<T>::back() const
{
	return data[size - 1];
}

 

더 구현 해야할 사항

 

• emplace_back [ 가변 인자 ]