[자료구조] 동적 배열 - Vector

선수지식 (자료구조 overview)

https://microelectronics.tistory.com/85

[자료구조] 선형 자료구조와 비선형 자료구조

 

size 와 capacity

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	vector<int> v;

	for (int i = 0; i < 100; i++) {
		v.push_back(i);
		cout << "value : " << v[i] << " size : " << v.size() << " capacity : " << v.capacity() << endl;
	}

	v.clear();
	cout << "size : " << v.size() << " capacity : " << v.capacity() << endl;
}

 

결과

value : 0 size : 1 capacity : 1
value : 1 size : 2 capacity : 2
value : 2 size : 3 capacity : 3
value : 3 size : 4 capacity : 4
value : 4 size : 5 capacity : 6
value : 5 size : 6 capacity : 6
value : 6 size : 7 capacity : 9
value : 7 size : 8 capacity : 9
value : 8 size : 9 capacity : 9
value : 9 size : 10 capacity : 13
..
value : 12 size : 13 capacity : 13
value : 13 size : 14 capacity : 19
...
value : 18 size : 19 capacity : 19
value : 19 size : 20 capacity : 28
...
value : 27 size : 28 capacity : 28
value : 28 size : 29 capacity : 42
...
value : 41 size : 42 capacity : 42
value : 42 size : 43 capacity : 63
...
value : 62 size : 63 capacity : 63
value : 63 size : 64 capacity : 94
...
value : 93 size : 94 capacity : 94
value : 94 size : 95 capacity : 141
...
value : 99 size : 100 capacity : 141
size : 0 capacity : 141

size 는 현채 요소가 차 있는 정도, capacity 는 가용한 전체 요소 개수.

size 와 capacity 가 가득차 있는 상태에서 요소가 추가될 경우, capacity 는 1.5배 정도로 늘어나는 것이 확인된다.

 

Vector class 구현

template<typename T>
class Vector
{
public:
	Vector()
	{

	}

	~Vector()
	{
		if (_data)
			delete[] _data;
	}

	void push_back(const T& value)
	{
		if (_size == _capacity)
		{
			int newCapacity = static_cast<int>(_capacity) * 1.5;
			// if _capacity is 0 or 1, 1.5 mult value would be same as before.
			if (newCapacity == _capacity)
				newCapacity++;
			reserve(newCapacity);
		}

		// store data
		_data[_size] = value;
		_size++;
	}

	void reserve(int capacity)
	{
		if (_capacity >= capacity)
			return;

		_capacity = capacity;
		T* newData = new T[_capacity];

		// copy data
		for (int i = 0; i < _size; i++) {
			newData[i] = _data[i];
		}

		if (_data)
			delete[] _data;

		_data = newData;
	}

	T& operator[](const int pos) { return _data[pos]; }

	int size() { return _size; }
	int capacity() { return _capacity; }

	void clear() 
	{
		if (_data) {
			delete[] _data;
			_data = new T[_capacity];
		}
		_size = 0;
	}
private:
	T* _data = nullptr;
	int _size = 0;
	int _capacity = 0;
};

 

main 함수 내에서 Vector<int> v; 로 선언 시 동일한 결과 나오는 것 확인 된다.