Can STL algorithms and back_inserter preallocate space?

  • A+
Category:Languages

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.

 


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.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: