0

So I have a class wrapping a vector which has the invariant that vec.capacity() > vec.size() so I can always (temporarily) emplace_back one more element without reallocation. My first idea was to call vec.reserve(vec.size() + 1) for every insertion, but this is inefficient as seen in this stackoverflow thread, and insert is called very often. (So is pop_back, therefore the maximal number of elements is way lower than the amounts of insert calls.)

My current implementation simplified looks something like this:

#include <vector>

template<typename T>
class VecWrapper {
private:
    std::vector<T> vec;

public:
    [[nodiscard]] auto insert(T new_element)
    {
        vec.emplace_back(std::move(new_element));
        if (vec.capacity() == vec.size()) {
            vec.emplace_back(vec.back());
            vec.pop_back();
        }
    }
};

Is there a less awkward way to trigger a capacity expansion of the vector according to the implementation defined strategy? Note that T is not necessarily default constructible.

Nicol Bolas
  • 449,505
  • 63
  • 781
  • 982
Emma X
  • 257
  • 3
  • 10
  • "*My first idea was to call vec.reserve(vec.size() + 1) for every insertion*" Couldn't you just reserve more than one element? Like maybe size * 2 or * 1.5 or something? – Nicol Bolas Oct 13 '20 at 15:18
  • I'm not sure I understand the point of this question. If you didn't do the check, you would get just as many reallocations as if you do this check, and the reallocations would reallocate the same amount of memory. And the reallocations still take place in `insert` The only difference is a *very* slight change in exactly when reallocations occur; `size` and `reserve` will simply never be equal. So... why is that important? – Nicol Bolas Oct 13 '20 at 15:20
  • So, the idea is to reserve the memory before it's needed rather than when it's needed? – Pete Becker Oct 13 '20 at 15:43
  • @NicolBolas Reserving like size*2 is exactly what I want, but instead of using my own magic number, I'd very much prefer the expansion strategy of the respective compiler. I want to establish the invariant to be able (for other reasons) to temporarily insert one more element without invalidating iterators. – Emma X Oct 13 '20 at 16:02
  • @PeteBecker Yes, like reserve one insert earlier than the standard vector would. – Emma X Oct 13 '20 at 16:02

0 Answers0