6

Given a std::vector, whose size and capacity can be arbitrary, what's the best practice to change its size to 0 and capacity to at least N(a given number)?

My direct idea is:

void f(vector<int> &t, int N)
{
    t.clear();
    t.reserve(N);
}

but I noticed that

A reallocation is not guaranteed to happen, and the vector capacity is not guaranteed to change(when std::vector::clear is called).

So I'm wondering how to avoid reallocating when the origin capacity is larger than the given N?

Deduplicator
  • 44,692
  • 7
  • 66
  • 118
los
  • 61
  • 5
  • Where is that quote from? – StoryTeller - Unslander Monica Jul 05 '18 at 08:43
  • 1
    the part you quoted is in reference to `std::vector::clear()`. Your call to `std::vector::reserve()` however should guarantee a change to vector capacity and reallocate (if `N>t.size()`) – Zinki Jul 05 '18 at 08:43
  • 1
    There is no way to guaranty to **reduce** the capacity (even `vector::shrink_to_fit`). – Jarod42 Jul 05 '18 at 08:44
  • 1
    @Zinki [`std::vector::reserve`](https://en.cppreference.com/w/cpp/container/vector/reserve) will do nothing if the new capacity is smaller. – songyuanyao Jul 05 '18 at 08:44
  • The quote is from "http://www.cplusplus.com/reference/vector/vector/clear/", so when the origin capacity>=N, I'm afraid std::vector::clear will make unnecessary reallocation – los Jul 05 '18 at 08:49
  • 5
    cplusplus.com is crap – M.M Jul 05 '18 at 08:51
  • @Jarod42 sorry, the link is http://www.cplusplus.com/reference/vector/vector/clear/ . so this approach may cause reallocation even if capacity>=N, that's bad to me. – los Jul 05 '18 at 08:55
  • @M.M `shrink_to_fit` is the opposite of what los appears to ask for. – eerorika Jul 05 '18 at 09:05

3 Answers3

4

what's the best practice to change its size to 0 and capacity to N(a given number)? My direct idea is: ...

Your direct idea is correct, and the simplest option. Although to be pedantic, reserve changes capacity to greater or equal to the given number; not guaranteed to be equal (but all implementations I've tested do allocate exactly the given amount if the previous capacity was less).

So I'm wondering how to avoid reallocating when the origin capacity is larger than the given N?

By using a standard library implementation that has chosen to not deallocate the memory on a call to clear (i.e. any standard conforming implementation, as indicated by the answer here).

Another approach to guarantee (although, it appears that this is not necessary as the above should be guaranteed, despite the weak wording on cplusplus.com) no reallocation (in the case N > t.capacity()): Since the vector contains simple integers, and you appear to know how many elements there will be (as you know to reserve), you could simply call t.resize(N) (to remove extra elements in case size was greater) without clearing the vector, and then proceed to overwrite the existing elements, rather than push new ones.

Of course, this means that you won't be able to observe the number of elements that have been overwritten, so this approach is not applicable for all use cases. It's fine if you simply want to fill the vector with a simple loop.

You might possibly want to reserve before resizing if the new size might be greater than the old, and you desire to not over-allocate. This is because most implementations allocate exact amount on reserve (as I mentioned) but use multiplication strategy on resize (neither of these behaviours are guaranteed as far as I know, but the implementations I've used have been consistent with this behaviour).

eerorika
  • 232,697
  • 12
  • 197
  • 326
  • You mean [a standard-conforming `std::vector::clear()`](https://en.cppreference.com/w/cpp/container/vector/clear) instead of a broken one? – Deduplicator Jul 05 '18 at 09:39
  • @Deduplicator ooh, did this in C++11? – eerorika Jul 05 '18 at 09:41
  • No C++03 here, but [digging into the referenced SO question](http://stackoverflow.com/a/18467916), no, C++11 just removed the unneeded requirement for T to be move-assignable. – Deduplicator Jul 05 '18 at 09:48
  • vector is only a example, actually the element is expensive to construct, so I'll take the first option. Thanks! – los Jul 05 '18 at 11:45
  • @los If the elements are expensive to construct, then the latter approach will be faster (assuming assignment isn't even more expensive) since it reuses the existing elements. The classes that you wouldn't want to do that with are things that cannot be reused and must be destroyed to keep the logic of the program intact. – eerorika Jul 05 '18 at 14:29
3

The best way is probably your current code.

Unfortunately, the standard allows an implementation to have containers whose capacity can only grow. In that case, your code will only guarantee that capacity is at least N. A reallocation will occur if initial capacity is less that N, and nothing will happen if capacity is greater that N. This points are guaranteed by the standard because draft 4659 for C++17 says at [vector.capacity] (emphasize mine):

void reserve(size_type n);
...
3 Effects: A directive that informs a vector of a planned change in size, so that it can manage the storage allocation accordingly. After reserve(), capacity() is greater or equal to the argument of reserve if reallocation happens; and equal to the previous value of capacity() otherwise. Reallocation happens at this point if and only if the current capacity is less than the argument of reserve().

and

void shrink_to_fit();
...
8 Effects: shrink_to_fit is a non-binding request to reduce capacity() to size(). [ Note: The request is non-binding to allow latitude for implementation-specific optimizations. —end note ] It does not increase capacity(), but may reduce capacity() by causing reallocation.

You have no way to guarantee that the capacity will be exactly N. Instead your code guarantees that if the initial capacity is greater than N in will be unchanged and no reallocation will happen.

Edit: this behaviour is stable at least since C++11 (draft n3337)

Serge Ballesta
  • 143,923
  • 11
  • 122
  • 252
0

Note: This answer answers the questions:

the best way to make a std::vector capacity=N and size=0?

and

what's the best practice to change its size to 0 and capacity to N(a given number)?

The change to ">= N" and adding requirement of avoiding a reallocation was added after this answer was posted.

The Standard does not offer any guaranteed way to achieve this. But your best chance is:

 t.clear();
 t.shrink_to_fit();
 t.reserve(N);

The second call is recommended to reduce the capacity to match the current size (which would be 0 at that point).

An alternative that may or may not work, again at the implementation's discretion, is:

t.swap( std::vector<int>{} );
t.reserve(N);
M.M
  • 138,810
  • 21
  • 208
  • 365
  • Surely in the case that `shrink_to_fit` actually does reduce capacity, the latter `reserve` *must* reallocate. How does that help to avoid the reallocation? – eerorika Jul 05 '18 at 09:27
  • @user2079303 Edited to clarify, the question has been substantially changed since this answer was posted – M.M Jul 05 '18 at 21:00