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

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

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

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

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

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

Вы можете почти добиться желаемого эффекта от выделения 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)));
}

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

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

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

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

#include<vector>
    #include<iostream>
    #include<chrono>
    int main(){
         std::vector<float> vec(10000,1.0f);
         std::vector<std::vector<float>> small_vecs(5000, std::vector<float>(50,2.0f));
         const auto t_start = std::chrono::high_resolution_clock::now();
         for(size_t i = 0; i < small_vecs.size(); i++) {
             // uncomment next line for quadratic complexity
             //vec.reserve(vec.size()+small_vecs[i].size());
             for (size_t j=0; j< small_vecs[i].size(); ++j){
                 vec.push_back(small_vecs[i][j]);
             }
         }
         const auto t_end = std::chrono::high_resolution_clock::now();
         std::cout << "runtime:" <<
             std::chrono::duration_cast<std::chrono::milliseconds>(t_end - t_start).count()
             << "ms\n";
    }

бонус:

в прошлый раз, когда я тестировал его, back_iterator даже с резервом был патетически медленным (замедление измеряется в x , а не в %), поэтому, если вы заботитесь о производительности, убедитесь, что при использовании back_inserter ваш код сравнивается с ручным циклом.

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

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

Также у вас могло быть

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

or

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

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

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