Могут ли алгоритмы STL и back_inserter предварительно распределять пространство? - PullRequest
Новая
       45

Могут ли алгоритмы STL и back_inserter предварительно распределять пространство?

0 голосов
/ 25 сентября 2018

Если у меня что-то вроде: 

vector<int> longVector = { ... };
vector<int> newVector;
transform(longVector.begin(), longVector.end(), back_inserter(newVector),
          [] (int i) { return i * i; });

Сможет ли STL предварительно выделить пространство в newVector перед обработкой и добавлением новых элементов?Я знаю, что это не требование алгоритма, но сможет ли «хорошая» реализация оптимизировать это?Или, для такого случая, я бы предпочел добавить newVector.reserve(longVector.size()); раньше?Я не обязательно спрашиваю, имеет ли каждая реализация stdlib или нет (хотя, если кто-то знает конкретные примеры, которые были бы хорошими), но больше, если это вообще возможно (и ожидается), учитывая интерфейс и требования алгоритмов.

Этот вопрос касается нескольких алгоритмов STL, transform, copy, move, fill_n, ... И не только к back_inserter, но также front_inserter и inserter Iпредположим.

РЕДАКТИРОВАТЬ: Для ясности я имею в виду, может ли stdlib обеспечить конкретные реализации, например, transform, для случая, когда выходной итератор является back_inserter из vector, в этом случае он получит доступ к векторному объекту и зарезервирует достаточно места для хранения distance между данной парой итераторов до фактического запуска преобразования.

Ответы [ 4 ]

0 голосов
/ 26 сентября 2018

Не вижу возможности.Существует резкое отделение от контейнеров и алгоритмов, которые работают с категориями итераторов.

Как и clear () и erase (), reserve () изменяет контейнер.Введя резерв (), вы узнаете о контейнере алгоритмов, что противоречит чистому дизайну этого резкого разделения.

Также вы могли иметь 

deque<int> longDeque = { ... };
deque<int> newDeque;
transform(longDeque.begin(), longDeque.end(), back_inserter(newDeque),
          [] (int i) { return i * i; });

или 

list<int> longList = { ... };
list<int> newList;
transform(longList.begin(), longList.end(), back_inserter(newList),
          [] (int i) { return i * i; });

и std :: deque & std :: list не поддерживают Reserve (), но код тот же.

И последнее замечание: вектор не имеет push_front (), поэтому front_inserter () долженне нуждается в поддержке.

0 голосов
/ 25 сентября 2018

Это потребовало бы большого количества специальных регистров в библиотеке, что принесло бы очень мало пользы.

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

Поскольку единственным преимуществом будет вознаграждение программистов, которым лень звонить reserve(), я чувствуюмаловероятно, что какой-либо исполнитель реализовал бы такую ​​вещь.Тем более что для работы, вероятно, потребуется std::​distance() на входных итераторах, что еще больше ограничит его использование.

Обратите также внимание, что такая реализация должна будет сохранять ссылку на вектор-владелец в своих итераторах, ине сможет использовать наиболее распространенное представление std::​vector<T>::​iterator, а именно T*.Это цена, которую должны понести все пользователи, независимо от того, используют ли эту новую функцию или нет.

Технически возможно?Возможно, в некоторых случаях.Разрешенный?Я думаю так.Хорошее соотношение цены и качества?Нет.

0 голосов
/ 25 сентября 2018

Хорошая новость заключается в том, что библиотека диапазонов резервирует для контейнеров итераторов с произвольным доступом, поэтому при желании вы можете использовать ее.

Теперь вернемся к проблеме:

резерв в цикле проблематичен

Трудно объяснить без чтения code , но если алгоритм STL вызывался в цикле и выполнял резерв, он мог вызвать квадратичную сложность.Проблема заключается в том, что некоторые контейнеры STL резервируют точный объем запрошенной памяти (это понятно для небольших размеров, но для больших IMAO это неправильное поведение), например, если текущая емкость равна 1000 и вы вызываете резерв (1005), резерв (1010), резерв (1010) вызовет 3 перераспределения (то есть вы скопировали ~ 1000 элементов каждый раз, чтобы получить место для 5 дополнительных).Вот код, он немного длинный, но я надеюсь, вы поняли:резерв был патетически медленным (замедление измеряется в x, а не в%), поэтому, если вы заботитесь о производительности, убедитесь, что при использовании back_inserter ваш код сравнивается с ручным циклом.

0 голосов
/ 25 сентября 2018

Вы можете почти достичь желаемого эффекта 1 выделения памяти, используя boost::transform_iterator вместо std::transform с std::back_inserter.

Проблема, однако, заключается в том, что boost::transform_iterator не можетвернуть ссылку на элемент, помеченный как std::input_iterator_tag.Входные итераторы являются однопроходными итераторами, в отличие от других категорий итераторов, и при передаче в конструктор диапазона std::vector он использует push_back для заполнения вектора.

Вы можете принудительно восстановить исходную категорию итераторов и добиться желаемого эффекта 1 распределения памяти с оговоркой, что такой итератор нарушает стандартное требование о том, что двунаправленный итератор с произвольным доступом должен возвращать ссылки на элементы: 

#include <boost/iterator/transform_iterator.hpp>
#include <algorithm>
#include <vector>

template<class I>
struct original_category_iterator : I {
    using iterator_category = typename std::iterator_traits<typename I::base_type>::iterator_category;
    using I::I;
};

template<class I>
inline original_category_iterator<I> original_category(I i) {
    return {i};
}

int main() {
    std::vector<int> longVector = {1,2,3};
    auto f = [](auto i) { return i * i; };
    std::vector<int> newVector(original_category(boost::make_transform_iterator(longVector.begin(), f)),
                               original_category(boost::make_transform_iterator(longVector.end(), f)));
}
...