[42서울] ft_containers[2] - 벡터 구현

서론

https://jhnyang.tistory.com/230

[자료구조STL vector 1탄]벡터란? 배열 vs 벡터 비교/장단점/ 특징, 다양한 백터 선언 및 초기화 방법,

동적 배열구조 클래스. 배열이지만 크기를 자유자재로 수정할 수 있는 배열이라고 생각하면 된다.

 

동적으로 메모리를 늘려주기 때문에 편해서 배열보다 더 자주 쓰인다.

 

각각의 원소를 [] 연산자를 통해 쉽게 접근할수있고, 임의의 순서로 메모리에 접근가능하다.

 

단점은 중간에 많은 데이터를 삽입하려면, 그 이후의 데이터를 전부 재할당해야 해서 막대한 오버헤드가 발생한다.(따라서 데이터의 삽입이 많은 경우 리스트 등 다른 자료구조를 사용해야 한다)

 

들어가야 하는 구성요소

value_type - 저장되는 자료형

allocator_type - STL 안에서 new-delete 대신 메모리 동적할당에 사용되는 클래스. 더 세분화된 메모리 관리와 성능을 위해 사용한다.

https://woo-dev.tistory.com/51

[C++] <memory> std::allocator<T> 클래스

reference - default allocator에서는 value_type&

const_reference - default allocator 에서는 const value_type&

pointer - default allocator 에서는 value_type*

const_pointer - default allocator 에서는 const value_type*

iterator - value_type의 random access iterator

const_iterator - 위의 const 버전

reverse_iterator - reverse_iterator<iterator>

const_reverse_iterator - 위의 const 버전

difference_type - 반복자 사이의 거리를 식별할 때 사용하는 유형으로 ptrdiff_t 사용

size_type - 사이즈의 자료형으로 size_t 사용

 

(constructor) - 기본생성자, 채우기 생성자, 범위 생성자, 복사 생성자 4개 구현

(destructor) - 전체 요소를 삭제하고 allocator에서 할당 해제

operator= - 기존 컨테이너의 값을 깊은 복사 해서 새로 만듦

 

Iterators:

begin - iterator, const_iterator 두 개 구현해야 함

end - iterator, const_iterator 두 개 구현해야 함

rbegin - reverse_iterator, const_reverse_iterator 두 개 구현해야 함

rend - reverse_iterator, const_reverse_iterator 두 개 구현해야 함

 

Capacity:

size - 현재 벡터 안 요소의 개수

max_size - 벡터 안에 담을 수 있는 최대 개수

resize - 크기를 재지정함. 주어진 값이 더 작으면 뒤부터 삭제, 더 많으면 요소가 주어진 경우 추가 아니면 초기화

capacity - 현재 벡터에 할당된 크기

empty - 벡터가 비어있는지 여부

reserve - capacity의 최솟값을 지정함. 만약 현재 cap이 주어진 값보다 작다면 cap의 크기를 키움. 더 크다면 아무 일도 일어나지 않음

 

Element access: 전부 다 const 버전도 만들어줘야 함

operator[] - vector의 element를 접근하는 데 사용되며, 마치 배열처럼 인덱스를 이용하여 접근 가능.

at - vector의 element에 접근하는 데 사용되며, 인덱스를 이용하여 접근할 수 있습니다. out-of-range 에러를 방지하기 위해 range check를 포함.

front - vector의 첫 번째 element에 접근.

back - vector의 마지막 element에 접근.

data - vector의 첫번째 element의 raw pointer를 반환.

 

Modifiers:

assign - 기존의 vector를 새로운 값으로 덮어쓰기

push_back - 벡터의 끝에 새로운 값을 추가

pop_back - 벡터의 마지막 값을 제거

insert - 벡터의 중간에 값을 추가

erase - 벡터에서 특정 위치의 값을 제거

swap - 두 개의 vector 를 교환

clear - 벡터의 모든 값을 제거

 

Allocator:

get_allocator - 현재 vector에서 사용되는 메모리 할당자의 정보를 반환.

 

Non-member function overloads

relational operators - vector 객체 간의 관계(<,>,<=,>=,==,!=)를 비교하는 연산자.

swap - 두 vector 객체의 내용을 바꿈.

 

추가 구현 요소

random_access_iterator

• 과제에서 요구하는 대로 내가 만든 stl 안에서 사용되는 이터레이터는 구현을 해줘야 한다. 따라서 vector에서 사용되는 random_access_iterator와 reverse_iterator를 구현해야 한다
• random_access_iterator는 범위 내의 원소들에 무작위 접근을 제공하는 이터레이터를 뜻한다. 그 덕분에 두 요소의 거리계산 등도 가능해진다. 요소들을 일렬로 저장하는 자료구조인 시퀀스 컨테이너에서 주로(list 등 제외) 사용되며, vector, deque, string, array 등에서 사용한다.
• 이런 점 때문에 이터레이터 안에서는 가장 포인터와 흡사하게 동작한다. operator []도 있어서 배열을 사용하다가 벡터를 사용하면 직관적으로 동일하게 사용할 수 있게 된다.

reverse_iterator

• 각 컨테이너마다 다른 이터레이터를 사용하니까 따로 구현할수도있지만, 과제의 의의를 생각해보면 당연히 다른 이터레이터를 템플릿으로 받도록 구현해야한다고 생각한다.
• 다른 이터레이터를 템플릿으로 받아서 해당 이터레이터의 역순으로 동작하는 이터레이터이다. 컨테이너들의 rbegin(), rend()에 사용된다.

iterator_traits

• 내가 만든 컨테이너여도 stl이 제공한 알고리즘의 함수들을 사용할 수 있는 이유가 iterator_traits을 이용하여 내부의 타입들을 정의했기 때문에, 해당 함수를 내가 재정의하지 않아도 동일하게 사용이 가능하게 된다.
• 다양한 컨테이너와 각자의 이터레이터를 사용하는데, 알고리즘은 그 이터레이터들마다 동일하게 동작하도록 구현되어야 한다. 그래서 이터레이터들이 일관된 인터페이스를 제공할 수 있도록 안에 이터레이터의 내용들을 정의한 구조체가 iterator_traits이다.

enable_if, is_integral

explicit vector	(size_type n, const value_type& val = value_type(),
				 			 const allocator_type& alloc = allocator_type())

template <class InputIterator>
vector (InputIterator first, InputIterator last,
				const allocator_type& alloc = allocator_type(),
				typename ft::enable_if<!ft::is_integral<InputIterator>::value, InputIterator>::type* = 0)

• 이런 식으로 사용되는데, size_type은 당연히 정수형이고, value_type이 정수형인 경우에는 아래 호출자와 혼동되지 않고 반드시 위 함수를 호출하도록 만들 수 있다.
• 과제에서 말한 것처럼 SFINAE(Substitution Failure Is Not An Error) 원칙을 배울 수 있다. 이는 템플릿 함수/클래스에서 주어진 타입에 따라 함수를 제외한다는 뜻이다.

equal

template <typename T, typename Alloc>
bool operator==(const ft::vector<T, Alloc>& lhs, const ft::vector<T, Alloc>& rhs) 
{
	if (lhs.size() != rhs.size())
		return false;
	return ft::equal(lhs.begin(), lhs.end(), rhs.begin());
}

두 벡터가 사이즈가 같고 앞에서부터 모든 요소가 같다면 동일하기 때문에 true를 반환한다.

• 두 개의 요소가 앞에서부터 동일한지를 확인한다. operator== 에서 사용하게 되는데, 벡터의 사이즈를 비교하진 않기 때문에 그 부분은 추가로 입력해야 한다.

lexicographical_compare

• lexicographical_compare는 사전식 비교라는 뜻으로 어릴 때 김 씨가 앞번호고 황 씨가 뒷번호인 것과 비슷하게 두 개 컨테이너의 요소를 하나씩 비교해서 앞 인자가 더 작은 경우(혹은 compare 함수가 주어진 경우 해당 함수에 해당하면) true, 아니면 false를 비교한다.

 

테스트

#include <time.h>
#include <iostream>
#include "vector.hpp"
#include <vector>
#include <fstream>
#include <time.h>

static void printvector(ft::vector<std::string>& v, std::ofstream& ftFile) {
	for (size_t i = 0; i < v.size(); i++) {
		ftFile << v[i] << " ";
	}
	ftFile << std::endl;
}

static void ft_test(std::ofstream& ftFile) {
	clock_t g_start = clock();

	ft::vector<std::string> v1;
	v1.push_back("the");
	v1.push_back("frogurt");
	v1.push_back("is");
	v1.push_back("also");
	v1.push_back("cursed");

	ftFile << "v1: ";
	printvector(v1, ftFile);

	ft::vector<std::string> v2(v1.begin(), v1.end());
	ftFile << "v2: ";
	printvector(v2, ftFile);

	ft::vector<std::string> v3(v2);
	ftFile << "v3: ";
	printvector(v3, ftFile);


	ftFile << "v3[1]: " << v3.at(1) << std::endl;
	ftFile << "v3[2]: " << v3[2] << std::endl;
	ftFile << "v3 front: " << v3.front() << std::endl;
	ftFile << "v3 back: " << v3.back() << std::endl;

	ft::vector<std::string>::iterator it = v3.begin();
	for (; it < v3.end(); it++) {
		ftFile << "it: " << *it << " ";
	}
	ftFile << std::endl;

	ft::vector<std::string>::reverse_iterator rvrIt = v3.rbegin();

	for (; rvrIt < v3.rend(); rvrIt++) {
		ftFile << "rvrIt: " << *rvrIt << " ";
	}
	ftFile << std::endl;

	ftFile << "v3 empty: " << (v3.empty() ? "true" : "false") << std::endl;
	ftFile << "v3 size: " << v3.size() << std::endl;
	ftFile << "v3 max_size: " << v3.max_size() << std::endl;
	int i = -1;
	while (++i < 10)
	{
		v1.push_back("1");
		ftFile << "v3 capacity: " << v1.capacity() << std::endl;
		ftFile << "v3 size: " << v1.size() << std::endl;
	}


	ftFile << "v3 clear\n";
	v3.clear();
	ftFile << "v3 size: " << v3.size() << std::endl;
	ftFile << "v3 insert (from v2)\n";
	v3.insert(v3.begin(), v2.begin(), v2.end());
	ftFile << "v3 size: " << v3.size() << std::endl;
	ftFile << "v3: ";
	printvector(v3, ftFile);

	ftFile << "erase first\n";
	v3.erase(v3.begin() + 1);
	ftFile << "v3: ";
	printvector(v3, ftFile);

	v3.push_back("foo");
	v3.push_back("bar");
	v3.push_back("kek");
	ftFile << "v3: ";
	printvector(v3, ftFile);

	v3.pop_back();
	ftFile << "v3: ";
	printvector(v3, ftFile);

	v3.resize(4);
	ftFile << "v3: ";
	printvector(v3, ftFile);

	v3.assign(2, "newWord");
	ftFile << "v3: ";
	printvector(v3, ftFile);

	v3.swap(v2);
	ftFile << "v3: ";
	printvector(v3, ftFile);

	ftFile << "v3 == v2: " << (v3 == v2 ? "true" : "false") << std::endl;
	ftFile << "v3 < v2: " << (v3 < v2 ? "true" : "false") << std::endl;
	ftFile << "v3 >= v2: " << (v3 >= v2 ? "true" : "false") << std::endl;

	ft::vector<int> v4;
	for (int i = 0; i < 300000; i++) {
		v4.push_back(i);
	}

	clock_t g_end = clock();
	ftFile << "ft_vector_Execution time (ms): " << (double)(g_end - g_start) / CLOCKS_PER_SEC * 1000 << "ms" << std::endl;
}

static void printVector(const std::vector<std::string>& v, std::ofstream& stlFile) {
	for (size_t i = 0; i < v.size(); i++) {
		stlFile << v[i] << " ";
	}
	stlFile << std::endl;
}

static void stl_test(std::ofstream& stlFile) {
	clock_t g_start = clock();

	std::vector<std::string> v1;
	v1.push_back("the");
	v1.push_back("frogurt");
	v1.push_back("is");
	v1.push_back("also");
	v1.push_back("cursed");


	stlFile << "v1: ";
	printVector(v1, stlFile);

	std::vector<std::string> v2(v1.begin(), v1.end());
	stlFile << "v2: ";
	printVector(v2, stlFile);

	std::vector<std::string> v3(v2);
	stlFile << "v3: ";
	printVector(v3, stlFile);

	stlFile << "v3[1]: " << v3.at(1) << std::endl;
	stlFile << "v3[2]: " << v3[2] << std::endl;
	stlFile << "v3 front: " << v3.front() << std::endl;
	stlFile << "v3 back: " << v3.back() << std::endl;

	std::vector<std::string>::iterator it = v3.begin();
	for (; it < v3.end(); it++) {
		stlFile << "it: " << *it << " ";
	}
	stlFile << std::endl;

	std::vector<std::string>::reverse_iterator rvrIt = v3.rbegin();
	for (; rvrIt < v3.rend(); rvrIt++) {
		stlFile << "rvrIt: " << *rvrIt << " ";
	}
	stlFile << std::endl;

	stlFile << "v3 empty: " << (v3.empty() ? "true" : "false") << std::endl;
	stlFile << "v3 size: " << v3.size() << std::endl;
	stlFile << "v3 max_size: " << v3.max_size() << std::endl;
	int i = -1;
	while (++i < 10)
	{
		v1.push_back("1");
		stlFile << "v3 capacity: " << v1.capacity() << std::endl;
		stlFile << "v3 size: " << v1.size() << std::endl;
	}

	stlFile << "v3 clear\n";
	v3.clear();
	stlFile << "v3 size: " << v3.size() << std::endl;
	stlFile << "v3 insert (from v2)\n";
	v3.insert(v3.begin(), v2.begin(), v2.end());
	stlFile << "v3 size: " << v3.size() << std::endl;
	stlFile << "v3: ";
	printVector(v3, stlFile);

	stlFile << "erase first\n";
	v3.erase(v3.begin() + 1);
	stlFile << "v3: ";
	printVector(v3, stlFile);

	v3.push_back("foo");
	v3.push_back("bar");
	v3.push_back("kek");
	stlFile << "v3: ";
	printVector(v3, stlFile);

	v3.pop_back();
	stlFile << "v3: ";
	printVector(v3, stlFile);

	v3.resize(4);
	stlFile << "v3: ";
	printVector(v3, stlFile);

	v3.assign(2, "newWord");
	stlFile << "v3: ";
	printVector(v3, stlFile);

	v3.swap(v2);
	stlFile << "v3: ";
	printVector(v3, stlFile);

	stlFile << "v3 == v2: " << (v3 == v2 ? "true" : "false") << std::endl;
	stlFile << "v3 < v2: " << (v3 < v2 ? "true" : "false") << std::endl;
	stlFile << "v3 >= v2: " << (v3 >= v2 ? "true" : "false") << std::endl;

	std::vector<int> v4;
	for (int i = 0; i < 300000; i++) {
		v4.push_back(i);
	}

	clock_t g_end = clock();
	stlFile << "stl_vector_Execution time (ms): " << (double)(g_end - g_start) / CLOCKS_PER_SEC * 1000 << "ms" << std::endl;
}

int main()
{
    std::ofstream stlFile("./stlFile.txt");
	if (stlFile.fail())
	{
		std::cerr << "Error!" << std::endl;
	}
    std::ofstream ftFile("./ftFile.txt");
	if (ftFile.fail())
	{
		std::cerr << "Error!" << std::endl;
	}

    ftFile << "\n***** VECTOR TEST *****\n" << std::endl;
	ft_test(ftFile);
	ftFile.close();

    stlFile << "\n***** VECTOR TEST *****\n" << std::endl;
	stl_test(stlFile);
	stlFile.close();

	system("diff ftFile.txt stlFile.txt");
}

벡터를 만든 김에 스택에서 사용하는 컨테이너를 변경하고 테스트를 해봤다. 둘 다 멀쩡하게 돌아가는 걸 보면 크게 이상 없이 짠 것으로 보인다.