Когда мы должны использовать резерв () вектора? - PullRequest
4 голосов
/ 05 января 2012

Я всегда использую resize (), потому что я не могу использовать резерва, поскольку он выдает ошибку: векторный индекс вне диапазона Когда я прочитал информацию о различиях resize () и reserve (), я увидел такие вещи, как reserve () устанавливает max. количество элементов может быть выделено, но resize () в настоящее время является тем, что мы имеем. В моем коде я знаю макс. Количество элементов, но Reserve () не дает мне ничего полезного. Итак, как я могу использовать Reserve ()?

Ответы [ 4 ]

9 голосов
/ 05 января 2012

Вектор имеет емкость (как возвращено capacity() и размер (как возвращено size(). В первом указано, сколько элементов может вектор ) удерживайте, второе, сколько он в настоящее время удерживает.

resize изменяет размер, reserve изменяет только capacity.

См. Также документацию resize и Резерв .

Что касается вариантов использования: Допустим, вы заранее знаете, сколько элементов вы хотите поместить в vector, но не хотите их инициализировать - это вариант использования для резерва. Допустим, ваш вектор был пуст; затем, непосредственно после reserve(), перед выполнением любых insert или push_back, вы, конечно, не можете напрямую обращаться к такому количеству элементов, для которого вы зарезервировали пространство - что вызвало бы упомянутую ошибку (индекс вне диапазона) - поскольку элементы, к которым вы пытаетесь получить доступ, еще не инициализированы; size - все еще 0. Таким образом, вектор все еще пуст; но если вы выбираете зарезервированную емкость таким образом, чтобы она была больше или равна максимальной величине, которую получит ваш вектор, вы избегаете дорогостоящих перераспределений; и в то же время вы также избежите (в некоторых случаях дорогостоящей) инициализации каждого элемента вектора, размер которого будет изменяться.

С resize, с другой стороны, вы говорите: заставить вектор содержать столько элементов, сколько я дал в качестве аргумента; инициализировать те, чьи индексы превышают старый размер, или удалить те, которые превышают заданный новый размер.

Обратите внимание, что reserve не будет никогда не повлиять на элементы, находящиеся в данный момент в векторе (кроме их места хранения, если необходимо перераспределение - но не их значения или их количество)! Это означает, что если размер вектора в настоящее время больше, чем тот, который вы передаете при вызове функции резерва для того же вектора, резерв просто ничего не сделает.

См. Также ответ на этот вопрос: Выбор между vector :: resize () и vector :: reserve ()

3 голосов
/ 05 января 2012

reserve () - это оптимизация производительности для использования std :: vector.

Типичная реализация std :: vector зарезервирует часть памяти при первом push_back(), например 4 элемента.Когда 5-й элемент выдвигается, вектор должен быть изменен: необходимо выделить новую память (обычно размер удваивается), содержимое вектора должно быть скопировано в новое местоположение, а старая память должна быть удалена.

Это становится дорогой операцией, когда вектор содержит много элементов.Например, когда вы нажимаете push_back () на 2 ^ 24 + 1-й элемент, 16Million элементов копируются только для добавления одного элемента.

Если вы заранее знаете количество элементов, вы можете reserve() количество элементов, которые выпланируют push_back().В этом случае дорогостоящие операции копирования не требуются, поскольку память уже зарезервирована для необходимого количества.

resize () в отличие от изменяет количество элементов вvector.

Если элементы не добавлены и вы используете resize(20), 20 элементов теперь будут доступны.Кроме того, объем выделенной памяти увеличится до значения, зависящего от реализации.Если добавлено 50 элементов и вы используете resize(20), последние 30 элементов будут удалены из вектора и больше не будут доступны.Это не обязательно изменяет выделенную память, но это также может зависеть от реализации.

2 голосов
/ 05 января 2012

resize (n) выделяет память для n объектов и инициализирует их по умолчанию.

reserve () выделяет память, но не инициализирует. Следовательно, резерв не изменит значение, возвращаемое функцией size (), но изменит результат емкости ().

0 голосов
/ 01 апреля 2015

Отредактировано после комментария underscore_d.

Описание того, как функции реализованы в VS2015

VS2015 CTP6

Это диалоговое окно ошибки существует только в режиме отладки, когда определено #if _ITERATOR_DEBUG_LEVEL == 2. В режиме RELEASE у нас нет проблем. Мы получаем текущее значение на return (*(this->_Myfirst() + _Pos), поэтому size значение не требуется:

    reference operator[](size_type _Pos)
    {   // subscript mutable sequence
    #if _ITERATOR_DEBUG_LEVEL == 2
    if (size() <= _Pos)
        {   // report error
        _DEBUG_ERROR("vector subscript out of range");
        _SCL_SECURE_OUT_OF_RANGE;
        }

    #elif _ITERATOR_DEBUG_LEVEL == 1
    _SCL_SECURE_VALIDATE_RANGE(_Pos < size());
    #endif /* _ITERATOR_DEBUG_LEVEL */

    return (*(this->_Myfirst() + _Pos));
    }

Если мы увидим в исходном коде вектора, то обнаружим, что разница между resize и reserve заключается только в изменении значения this->_Mylast() в функции resize().

reserve() звонки _Reallocate.

resize() вызывает _Reserve, который вызывает _Reallocate, а затем resize() также изменяет значение this->_Mylast(): this->_Mylast() += _Newsize - size();, которое используется в расчете size (см. Последнюю функцию)

    void resize(size_type _Newsize)
    {   // determine new length, padding as needed
    if (_Newsize < size())
        _Pop_back_n(size() - _Newsize);
    else if (size() < _Newsize)
        {   // pad as needed
        _Reserve(_Newsize - size());
        _TRY_BEGIN
        _Uninitialized_default_fill_n(this->_Mylast(), _Newsize - size(),
            this->_Getal());
        _CATCH_ALL
        _Tidy();
        _RERAISE;
        _CATCH_END
        this->_Mylast() += _Newsize - size();
        }
    }


    void reserve(size_type _Count)
    {   // determine new minimum length of allocated storage
    if (capacity() < _Count)
        {   // something to do, check and reallocate
        if (max_size() < _Count)
            _Xlen();
        _Reallocate(_Count);
        }
    }



    void _Reallocate(size_type _Count)
    {   // move to array of exactly _Count elements
    pointer _Ptr = this->_Getal().allocate(_Count);

    _TRY_BEGIN
    _Umove(this->_Myfirst(), this->_Mylast(), _Ptr);
    _CATCH_ALL
    this->_Getal().deallocate(_Ptr, _Count);
    _RERAISE;
    _CATCH_END

    size_type _Size = size();
    if (this->_Myfirst() != pointer())
        {   // destroy and deallocate old array
        _Destroy(this->_Myfirst(), this->_Mylast());
        this->_Getal().deallocate(this->_Myfirst(),
            this->_Myend() - this->_Myfirst());
        }

    this->_Orphan_all();
    this->_Myend() = _Ptr + _Count;
    this->_Mylast() = _Ptr + _Size;
    this->_Myfirst() = _Ptr;
    }

    void _Reserve(size_type _Count)
    {   // ensure room for _Count new elements, grow exponentially
    if (_Unused_capacity() < _Count)
        {   // need more room, try to get it
        if (max_size() - size() < _Count)
            _Xlen();
        _Reallocate(_Grow_to(size() + _Count));
        }
    }

    size_type size() const _NOEXCEPT
    {   // return length of sequence
    return (this->_Mylast() - this->_Myfirst());
    }

Проблемы

Но существуют некоторые проблемы с reserve:

  1. end() будет равно begin()

23.2.1 Общие требования к контейнерам

5

end() возвращает итератор, который является последним значением для контейнера.

    iterator end() _NOEXCEPT
    {   // return iterator for end of mutable sequence
    return (iterator(this->_Mylast(), &this->_Get_data()));
    }

т.е. _Mylast() будет равно _Myfirst()

  1. at () сгенерирует исключение out_of_range.

23.2.3 Контейнеры последовательности

17

Функция-член at () обеспечивает доступ с проверкой границ к элементам контейнера. at () выбрасывает out_of_range, если n> = a.size ().

  1. в отладчике VisualStudio мы можем видеть векторные значения, когда размер не равен 0

с resize:

enter image description here

с reserve и настройкой вручную #define _ITERATOR_DEBUG_LEVEL 0:

enter image description here

...