Data Structure in C++ - Array, STL Vector

본 포스팅 시리즈에서는 모든 프로그래머들이 반드시 알아야 할 가장 기본적인 자료구조를 다룰 예정이다. 

앞으로 다룰 내용은 프로그래머에게 기본 소양이며, 본인 스스로 직접 구현할 수 있어야 한다. 

 

| 첫 번째 순서는 배열이다. 

배열은 같은 data-type의 item들을 담을 수 있는 고정된 크기의 자료구조이다. 배열은 인덱싱을 기본적으로 지원하며, 이는 곧 Random 한 접근이 가능하다는 것을 의미한다. 배열은 일반적으로 많은 프로그래밍 언어에서 기본 데이터 구조로 존재한다. 하지만 Python이나 Ruby 같은 언어의 데이터 구조와 같은 리스트와 배열을 혼동해서는 안된다. 

 

아래는 C++에서 가장 기본적인 배열이 나타나는 형태이다.

// 단순 선언
int array[] = {1, 2, 3, 4, 5};
// 포인터 형태 (힙 영역에 저장된다)
int * array = new int[5];

대부분의 프로그래머들은 Problem Solving을 하거나 다른 경로를 통해 vector를 많이 사용한다. vector는 배열과 유사한 자료구조이며, vector를 사용함으로써 프로그래머는 사이즈에 대한 걱정 없이 item을 추가할 수 있다. 그렇다면 vector와 유사한, 일정 사이즈를 오버했을 때 스스로 사이즈를 조절하는 DynamicArray를 구현해보자.

단, 코딩 스타일은 Google에서 제시하는 C/C++ Coding Style을 최대한 적용하여 구현하였다. 

 

using namespace std;

class DynamicArray
{
private:
	int size_;
    int max_;
    int *arrayholder_;
public:
	DynamicArray()
    {
    	this->size_ = 0;
        this->max_ = 5;
        this->arrayholder_ = new int[5];
    }
    ~DynamicArray()
    {
    	delete[] this->arrayholder_;
    }
    
    int size()
    {
    	return this->size_;
    }
    
    int& operator[](int i)
    {
    	assert(i < this->size_);
    	return this->arrayholder_[i];
    }
    void add(int value)
    {
    	if(this->size_ + 1 > this->max_)
        {
        	this->max_ *= 2;
            int* tmp_ = new int[this->max_];
            for(int i=0; i<this->size_; i++)
            {
            	tmp_[i] = this->arrayholder_[i];
            }
            
            delete[] this->arrayholder_;
            this->arrayholder_ = tmp_;
            this->arrayholder_[this->size_] = value;
            this->size_ += 1;
        }
        else
        {
        	this->arrayholder_[this->size_] = value;
        	this->size_ += 1;
        }
    }  
};

구현한 내용을 살펴본다면, 초기에 배열의 크기를 5로 초기화 해주었다. 또한, add함수에서 item을 추가했을 때 사이즈가 초과한다면 사이즈를 2배로 늘려주었다. 이게 실제 vector<T>가 동작하는 원리이다. 일반적으로 기본 사이즈는 약 30이다. 

 

한 가지 더 알아야 할 점은, 생성자와 소멸자를 모두 사용하였다는 것이다. 이는 배열 확장을 위해 메모리에 대한 포인터가 있기 때문이며, 이 할당된 메모리는 오버플로를 방지하기 위해 해제되어야 한다. 이렇게 구현할 때의 장점은 사용자가 ugly pointer에 대해 알 필요가 없다는 것이다. operator []를 오버 로드하면 기본 배열과 같은 인덱스 액세스가 가능해진다.

 

assert함수는 디버깅모드에서 개발자가 오류가 생기면 치명적일 것이라는 곳에 심어 놓은 에러 검출용 코드이다. 안의 내용이 false(0)가 되면 에러가 발생한다. 

 

---

STL Vector

Vectors are sequence containers representing arrays that can change in size.

 

벡터는 배열과 아주 유사하지만 고정된 사이즈를 가지는 배열과 달리 사이즈 변경이 자유로운 특징을 가지고 있다.
사이즈 변경이 보통 사용하던 list와 달리 vector는 배열의 특성을 가지면서도 빈번한 사이즈 변경에 자유롭기 때문에 많은 곳에서 사용되고 있다.

그렇다면 Vector에서 가장 많이 사용하는 기능들을 예와 함께 살펴보자.
편의를 위해 using namespace std 가 선언되어 있다고 가정한다.

 

| Vector의 선언

vector<int> my_integer_vector; 
vector<char> my_charcter_vector;
vector<string> my_string_vector;
vector<vector<int>> my_2D_integer_vector;

| 사이즈를 지정한 Vector의 선언

vector<int> my_integer_vector(5);
vector<char> my_charcter_vector(10);
vector<vetor<int>> my_2D_integer_vector(10, vector<int> (20)) // 10 x 20 사이즈 2D vector.

| 사이즈 지정 및 초기화

vector<int> my_integer_vector(5, 100); // 모든 값이 100인 사이즈 5의 vector선언
vector<int> my_integer_vector2; //모든 값이 10인 사이즈 10의 vector
my_integer_vector.assign(10, 10);

 

| Vector 요소 접근 방법

vector<int> my_integer_vector = {1,2,3,4,5};
my_integer_vector[1] = 3; // access element index 1
my_integer_vector.at(3) = 3; // access element index 3

my_integer_vector.front() = 5; // access first element 
my_integer_vector.back() = 1; // access last element

int * p = my_integer_vector.data(); // A pointer to the first element in the array

| iterator 사용법

vector<int> my_vector;
for(vector<int>::iterator it = my_vector.begin(); it != my_vector.end(); it++) {
    cout << *it << endl;
}

| Vector유용한 함수

vector<int> my_vector;
my_vector.push_back(3); // add element at the end
my_vector.pop_back(); // delete last element;
my_vector.insert(my_vector.begin(), 200); // insert 200 at front of vector
my_vector.erase(my_vector.begin(), my_vector.begin() + 1); // erase 2 element front of vector
my_vector.empty(); // check vector is empty 

my_vector.clear(); // remove all elemente vector

vector<int> second_vector;
swap(my_vector, second_vector); // change all elemnte with second_vector;

 

 

reference : Data Structures in C++ — Part 1. Implementing common data structures in… | by Vijini Mallawaarachchi | Towards Data Science