Static array

가장 기본적인 자료구조, 배열에 대해 공부해보자.

공부는 가상의 가방을 구현한다고 가정하고 진행 할 것이다.

단, 정적 배열은 너무 익숙한 방법이라 설명이 많지 않을 예정입니다...

 

 

class bag {
    public:
        static const size_t CAPACITY = 20;
        ...
    private:
        int data[CAPACITY]; // member variable: data container
        size_t used; // member variable: counting data qty
};

기본적으로 정보를 저장할 data 배열이 있을 것이고, 배열의 기본 사이즈는 CAPACITY = 20으로 할당해준다.

가방의 사용량은 used로 측정할 것이다.

 

 

이제 가방에 필요한 기능을 구현 해볼건데, 먼저 가방에 아이템을 집어 넣는 기능부터 구현 해보자.

typedef int value_type;

void bag::insert(const value_type& new_entry) {
    assert(size() < CAPACITY);
    data[used++] = new_entry;
}

정적 배열은 그냥 평범하게 사용한 방법대로 사용하면 된다.

 

 

다음은 가방에 특정 값을 제거하는 기능을 구현 해보자.

bool bag::erase_one(const value_type& target) {
    size_t index = 0;
    // 다 보지 못했고, 타겟이 안나오면
    while ((index < used) && (data[index] != target))
        ++index;
    // 끝까지 갔는데 못 찾은 경우
    if (index == used)
        return false;
    // 타겟을 찾은 경우
    /**
     * bag 클래스는 아이템의 순서가 중요하지 않기 때문에
     * 그냥 마지막에 있는 아이템을 타겟의 인덱스에 넣고,
     * used만 줄여주면 된다 (마지막(used)에 있는 값은 쓰레기 값처럼 생각하면 된다)
    */
    --used;
    data[index] = data[used];
    return true;
}

이 가방의 특징은 들어가 있는 데이터의 순서는 중요하지 않다는 점이다.

따라서 가방 중간에 특정 값을 제거하는 경우, 그 값이 있는 인덱스부터 마지막 인덱스까지 값을 하나씩 당겨오는 것이 아니라,

그 값이 있는 인덱스에 마지막 인덱스의 값으로 덮어 씌우고 used 값만 하나 줄여주는 것이다.

 

 

마지막으로 가방 끼리 합치는 기능을 구현해보자.

void bag::operator+=(const bag& addend) {
    assert(size() + addend.size() <= CAPACITY);

    copy(addend.data, addend.data + addend.used, data + used);
    used += addend.used;
}

기존의 가방(왼쪽 피연산자) 뒤에 더할 가방(오른쪽 피연산자)을 copy 함수를 이용하여 붙여준다.

참고로 copy함수의 사용법은 다음과 같다.

 

copy(front_ptr, end_ptr, des_ptr);

front_ptr: 복사할 대상의 첫 번째 위치를 가리키는 포인터

end_ptr: 복사할 대상의 마지막 인덱스의 다음 위치의 포인터

des_ptr: 복사할 위치의 시작 위치

 

 

진짜 자료구조의 시작은 동적 배열부터 시작할 예정이다.

다음 포스트부터 동적 배열, 링크 배열 등등을 알아보자!