Can STL algorithms and back_inserter preallocate space?

Question

If I have something like:

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

Would STL be able to preallocate space in newVector before processing and adding the new elements? I know it is not a requirement of the algorithm, but would a "good" implementation be able to optimize that? Or, for this kind of case, should I prefer adding newVector.reserve(longVector.size()); before? I am not necessarily asking whether each stdlib implementation out there does or not (although if someone knows specific examples that would be great), but more whether it is possible at all (and expected), given the interface and requirements of the algorithms.

The question applies to multiple STL algorithms, transform, copy, move, fill_n, ... And not just to back_inserter, but also front_inserter and inserter I suppose.

EDIT: For clarity, what I mean is whether a stdlib can provide specific implementations of, for example, transform, for the case when the output iterator is a back_inserter of a vector, in which case it would access the vector object and reserve enough space to store the distance between the given pair of iterators before actually running the transformation.

Answer 1

It would require a lot of special-casing in the library, for very little benefit.

The whole point of separating algorithms from collections is that neither needs to know about the other, and users can add their own algorithms that work with standard collections, or new collections that work with existing algorithms.

Since the only benefit would be to reward programmers who are too lazy to call reserve(), I feel it's unlikely that any implementer would implement such a thing. Especially since it would probably require std::​distance() on the input iterators in order to work, further constraining its use.

Note also that such an implementation would need to keep a reference to the owning vector in its iterators, and would be unable to use the most common representation of std::​vector<T>::​iterator, namely T*. That's a cost that all users would have to bear, whether or not using this new feature.

Technically possible? Perhaps, in some cases. Permitted? I think so. Good value-for-effort? No.

Answer 2

You can almost achieve the desired effect of 1 memory allocation using boost::transform_iterator instead of std::transform with std::back_inserter .

The problem though is that because boost::transform_iterator cannot return a reference to an element it is tagged as std::input_iterator_tag. Input iterators are single-pass iterators, unlike other iterator categories, and when passed to std::vector range constructor it uses push_back to fill the vector.

You can force-restore the original iterator category and achieve the desired effect of 1 memory allocation with a caveat that such an iterator violates the standard requirement that a bidirectional or random-access iterator must return references to elements:

#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)));
}

Answer 3

Good news is that range library does reserve for random access iterator containers so if you want you can use it.

Now back to the problem:

reserve in a loop is problematic

It is hard to explain without reading code, but if STL algorithm was called in a loop and it was doing the reserve it could trigger quadratic complexity. Problem is that some STL containers reserve exact amount of memory requested(it is understandable for small sizes, but for large ones IMAO this is wrong behavior), so for example if current capacity is 1000 and you call reserve(1005), reserve(1010), reserve(1010) it will cause 3 reallocations(meaning you copied ~1000 elements each time to get place for 5 extra). Here is the code, it is a bit long, but I hope you get the idea:

#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";
    }

bonus:

last time I benchmarked it back_iterator even with reserve was pathetically slow(slowdown measured in x , not %), so if you care about performance make sure that when you use back_inserter your code it is benchmarked against manual loop.

Answer 4

I don't see it is possible. There is sharp separation from containers and algorithms which work on iterator categories.

Like clear() and erase(), reserve() modifies the container. Introducing reserve(), makes the algorithms container aware, which goes against the clean design of that sharp separation.

Also you could have had

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; });

and std::deque & std::list don't support reserve(), yet the code is the same.

One last point: vector does not have a push_front() so front_inserter() should not need to be supported.