YonMy » vector

std::vector로 배우는 레벨업 #2

01/18/2018 c++, programming No comments stl, template, vector

resize를 구현해 보자

    void resize(size_t newSize)
    {
        // 공간을 확보
        reserve(newSize);

        // 늘어난 사이즈만큼 생성자를 호출
        for (size_t i = _size; i < newSize; ++i)
        {
            auto p = _data + i;
            new(p) T();
        }

        // 줄어든 사이즈만큼 소멸자를 호출
        for (size_t i = newSize; i < _size; ++i)
        {
            auto p = _data + i;
            p->~T();
        }

        _size = newSize;
    }

void resize(size_t newSize)

{

// 공간을 확보

reserve(newSize);

// 늘어난 사이즈만큼 생성자를 호출

for (size_t i = _size; i < newSize; ++i)

{

auto p = _data + i;

new(p) T();

}

// 줄어든 사이즈만큼 소멸자를 호출

for (size_t i = newSize; i < _size; ++i)

{

auto p = _data + i;

p->~T();

}

_size = newSize;

}

아래 테스트 코드를 통해 동작을 확인해보자.

std::cout << "std::vector<Foo> :" << std::endl;
std::vector<Foo> stdVec;
stdVec.resize(3);
stdVec.resize(1);

std::cout << std::endl;
std::cout << "MyVector<Foo> :" << std::endl;

MyVector<Foo> myVec;
myVec.resize(3);
myVec.resize(1);

std::cout << "std::vector<Foo> :" << std::endl;

std::vector<Foo> stdVec;

stdVec.resize(3);

stdVec.resize(1);

std::cout << std::endl;

std::cout << "MyVector<Foo> :" << std::endl;

MyVector<Foo> myVec;

myVec.resize(3);

myVec.resize(1);

std::vector로 배우는 레벨업 #1

01/17/2018 c++, programming No comments stl, template, vector

선행학습: std::vector의 size와 capacity에 대해서 제대로 알고있자

std::vector의 push_back과 reserve를 한번 직접 구현해보자..

언뜻 생각해보면 template에 대해서 조금만 알고 있으면 다음과 같이 쉽게 구현 할 수 있을 거라는 생각이 들 것이다.

template<class T>
class MyVector
{
public:
    MyVector()
        : _data(nullptr)
        , _size(0)
        , _capacity(0)
    {
    }

    ~MyVector()
    {
        delete[] _data;
    }

    size_t size() const noexcept { return _size; }
    size_t capacity() const noexcept { return _capacity; }

    T& operator[](size_t idx)
    {
        return _data[idx];
    }

    void reserve(size_t newCapacity)
    {
        if (_capacity < newCapacity)
        {
            // 더 큰 공간을 할당 하고
            T* newData = new T[newCapacity];

            // 기존의 _data를 복사한다.
            for (size_t i = 0; i < _size; ++i)
            {
                newData[i] = _data[i];
            }

            // 기존의 _data는 메모리 해제
            delete[] _data;
            _data = newData;
            _capacity = newCapacity;
        }
    }

    void push_back(const T& value)
    {
        if (_capacity <= _size)
        {
            reserve(calculate_growth(_capacity + 1));
        }

        _data[_size++] = value; // 복사 및 사이즈 증가
    }

private:
    size_t calculate_growth(const size_t new_size) const
    {
        if (_capacity > std::numeric_limits<size_t>::max() - _capacity / 2)
        {
            return (new_size);	// geometric growth would overflow
        }

        const size_t geometric = _capacity + _capacity / 2;
        if (geometric < new_size)
        {
            return (new_size);	// geometric growth would be insufficient
        }

        return (geometric);	// geometric growth is sufficient
    }

private:
    T* _data;
    size_t _size;
    size_t _capacity;
};

template<class T>

class MyVector

{

public:

MyVector()

: _data(nullptr)

, _size(0)

, _capacity(0)

{

}

~MyVector()

{

delete[] _data;

}

size_t size() const noexcept { return _size; }

size_t capacity() const noexcept { return _capacity; }

T& operator[](size_t idx)

{

return _data[idx];

}

void reserve(size_t newCapacity)

{

if (_capacity < newCapacity)

{

// 더 큰 공간을 할당 하고

T* newData = new T[newCapacity];

// 기존의 _data를 복사한다.

for (size_t i = 0; i < _size; ++i)

{

newData[i] = _data[i];

}

// 기존의 _data는 메모리 해제

delete[] _data;

_data = newData;

_capacity = newCapacity;

}

void push_back(const T& value)

{

if (_capacity <= _size)

{

reserve(calculate_growth(_capacity + 1));

}

_data[_size++] = value; // 복사 및 사이즈 증가

}

private:

size_t calculate_growth(const size_t new_size) const

{

if (_capacity > std::numeric_limits<size_t>::max() - _capacity / 2)

{

return (new_size); // geometric growth would overflow

}

const size_t geometric = _capacity + _capacity / 2;

if (geometric < new_size)

{

return (new_size); // geometric growth would be insufficient

}

return (geometric); // geometric growth is sufficient

}

private:

T* _data;

size_t _size;

size_t _capacity;

};

한번 다음의 테스트 코드로 std::vector과 MyVector의 출력결과가 어떻게 다른지 확인해 보면….

Foo temp;

std::cout << "1-1. std::vector<Foo> :" << std::endl;
std::vector<Foo> stdVec;

std::cout << "1-2. std::vector<Foo>::reserve(2) :" << std::endl;
stdVec.reserve(2);

std::cout << "1-3. std::vector<Foo>::push_back(temp) :" << std::endl;
stdVec.push_back(temp);

std::cout << "2-1. MyVector<Foo> :" << std::endl;
MyVector<Foo> myVec;

std::cout << "2-2. MyVector<Foo>::reserve(2) :" << std::endl;
myVec.reserve(2);

std::cout << "2-3. MyVector<Foo>::push_back(temp) :" << std::endl;
myVec.push_back(temp);

Foo temp;

std::cout << "1-1. std::vector<Foo> :" << std::endl;

std::vector<Foo> stdVec;

std::cout << "1-2. std::vector<Foo>::reserve(2) :" << std::endl;

stdVec.reserve(2);

std::cout << "1-3. std::vector<Foo>::push_back(temp) :" << std::endl;

stdVec.push_back(temp);

std::cout << "2-1. MyVector<Foo> :" << std::endl;

MyVector<Foo> myVec;

std::cout << "2-2. MyVector<Foo>::reserve(2) :" << std::endl;

myVec.reserve(2);

std::cout << "2-3. MyVector<Foo>::push_back(temp) :" << std::endl;

myVec.push_back(temp);

  Foo()
1-1. std::vector<Foo> :
1-2. std::vector<Foo>::reserve(2) :
1-3. std::vector<Foo>::push_back(temp) :
  Foo(const Foo&) #c++ 버젼에 따라 Foo& operator=(const Foo&) 일 수도 있음
2-1. MyVector<Foo> :
2-2. MyVector<Foo>::reserve(2) :
  Foo()
  Foo()
2-3. MyVector<Foo>::push_back(temp) :
  Foo& operator=(const Foo&)

Foo()

1-1. std::vector<Foo> :

1-2. std::vector<Foo>::reserve(2) :

1-3. std::vector<Foo>::push_back(temp) :

Foo(const Foo&) #c++ 버젼에 따라 Foo& operator=(const Foo&) 일 수도 있음

2-1. MyVector<Foo> :

2-2. MyVector<Foo>::reserve(2) :

Foo()

2-3. MyVector<Foo>::push_back(temp) :

Foo& operator=(const Foo&)

push_back을 했을때 복사생성자가 호출되느냐 대입연산자가 호출되느냐는 c++ 버젼에 따라 차이가 있을 수 있으니, 동일하다고 치고,

stl버젼은 reserve를 했을때 생성자가 호출되지 않지만, MyVector는 생성자가 2번 호출되는 차이점을 볼 수 있다.

이 차이가 의미하는 것은 무엇일까?

눈치가 빠른분들은 이미 감을 잡으셨을 것이다.

그렇다. vector에서 reserve함수를 통하여 capacity의 크기를 늘린다는 것은 메모리공간만 할당하는 것이지, 실제 객체가 생성되는 것은 아니다.

혹시, 아직 c++에서 객체 생성의 의미를 정확히 모르고 있었다면, 이제는 정확히 이해 했을 것이다.

(잘 모르겠으면 ‘c++에서 malloc과 new의 차이점‘을 읽어보자)

그럼 한번 요구사항에 맞게 코드를 고쳐보자

    ~MyVector()
    {
        ::operator delete(_data);
    }

    void reserve(size_t newCapacity)
    {
        if (_capacity < newCapacity)
        {
            // 더 큰 공간을 할당 하고
            const size_t bytes = sizeof(T) * newCapacity;
            T* newData = static_cast<T*>(::operator new(bytes));

            // 기존의 _data를 복사한다.
            for (size_t i = 0; i < _size; ++i)
            {
                newData[i] = _data[i];
            }

            // 기존의 _data는 메모리 해제
            ::operator delete(_data);
            _data = newData;
            _capacity = newCapacity;
        }
    }

~MyVector()

{

::operator delete(_data);

}

void reserve(size_t newCapacity)

{

if (_capacity < newCapacity)

{

// 더 큰 공간을 할당 하고

const size_t bytes = sizeof(T) * newCapacity;

T* newData = static_cast<T*>(::operator new(bytes));

// 기존의 _data를 복사한다.

for (size_t i = 0; i < _size; ++i)

{

newData[i] = _data[i];

}

// 기존의 _data는 메모리 해제

::operator delete(_data);

_data = newData;

_capacity = newCapacity;

}

이제 std::vector와 동일한 결과가 나옴을 확인 할 수 있을 것이다.

std::vector의 size와 capacity에 대해서 제대로 알고있자

12/11/2016 c++, programming 1 comment stl, vector

std::vector를 제대로 알고, 제대로 쓰고 있는가를 파악할 때 내가 자주 하는 질문은

reserve와 resize에 대해 설명해 보세요.

의외로 많은 프로그래머가 제대로 대답하지 못한다.

저 질문을 대답하기 위해서는 size와 capacity에 대해서 잘 알고 있어야 하는데..

사실, std::vector을 사용하기에 앞서 어떻게 구현이 되어있을까? 라고 고민을 해보면 추측할 수 있는 문제가 아닌가 하는 안타까움이 들때가 많다.

이제 막 입문하는 사람은 그렇다 치고, 어느정도 사용하다보면, 당연히 가지게 되는 의문과 고민, 추측이 아닌가?

그것은 나만 기대하는 욕심인 것인가?

위 그림을 보면 대부분은 이해할 것이라고 생각한다.

capacity는 vector의 요소(element)들을 담을 수 있는 메모리가 할당되어 있는 공간의 용량이다.

size는 실제 유효한 요소(element)들의 갯수이다.

예를 들어, push_back함수를 통해 새로운 요소(element)를 맨뒤에 한개 추가할 때,

capacity > size보다 큰 상황이면 그냥 맨뒤의 공간에 요소를 복사해 넣고 ++size만 일어나며,

capacity == size 이면 capacity가 증가한 새로운 연속된 공간을 할당하고… 기존의 모든 요소들을 복사하여(기존 정보는 지우고..) capacity > size인 상황을 만들어 놓고, 맨뒤에 요소를 복사해 놓고, ++size를 하는 과정이 일어나는 것이다.

reserve는 이 capacity를 프로그래머가 원하는 크기로 할당을 해준다.

여기까지 size, capacity, reserve에 대해서 이해했으리라 믿고, Effective STL의 항목 14. reserve는 필요 없이 메모리가 재할당되는 것을 막아 준다.(Use reserve to avoid unnecessary reallocations)를 공부해 보길 바란다.

여기서는 resize에 대해서 조금 더 이야기를 해보려고 한다.

resize에 대해서 다음과 같이 설명하는 사람에게는 나는 70점을 줄 것이다.

지정한 수 만큼 요소를 만들어 준다. 내부에서 capacity가 작으면 재할당이 일어나며…

resize에서 한가지 더 중요한 것이 있는데, 증가되는 size만큼 복사생성자가 호출된다는 점이다.

(c++11까지는 복사생성자가 호출 됬었는데, 최신은 생성자가 호출된다.)

resize의 원형을 보자

void resize( size_type count, T value = T() ); // (until C++11)
void resize( size_type count ); // (1)	(since C++11)
void resize( size_type count, const value_type& value ); // (2)	(since C++11)

void resize( size_type count, T value = T() ); // (until C++11)

void resize( size_type count ); // (1) (since C++11)

void resize( size_type count, const value_type& value ); // (2) (since C++11)

C++ 11 이전 버젼이든 C++ 11 이후 버젼이든, 기본값을 따로 지정하지 않으면, default 생성자에 의해서 모든 요소가 초기화 된다는 사실은 동일하다.

과거에 이렇게 코딩한 사람을 본적이 있는데… 이는 resize의 스펙을 잘 모르고 한 바보같은….

std::vector<int> temp;
temp.resize(10);

// 불필요한 중복 초기화 작업
for (size_t i = 0; i < 10 ; ++i)
{
    temp[i] = 0;
}

std::vector<int> temp;

temp.resize(10);

// 불필요한 중복 초기화 작업

for (size_t i = 0; i < 10 ; ++i)

{

temp[i] = 0;

}

참고

http://en.cppreference.com/w/cpp/container/vector/size

http://en.cppreference.com/w/cpp/container/vector/capacity

http://en.cppreference.com/w/cpp/container/vector/reserve

http://en.cppreference.com/w/cpp/container/vector/resize

Effective STL, 2001, Scott Meyers

vector

std::vector로 배우는 레벨업 #2

std::vector로 배우는 레벨업 #1

std::vector의 size와 capacity에 대해서 제대로 알고있자

최신 글

카테고리

vector

std::vector로 배우는 레벨업 #2

std::vector로 배우는 레벨업 #1

std::vector의 size와 capacity에 대해서 제대로 알고있자

최신 글

카테고리

태그