Is Shrink_To_Fit the Proper Way of Reducing the Capacity a 'Std::Vector' to Its Size

Is shrink_to_fit the proper way of reducing the capacity a `std::vector` to its size?

Do the arguments in the quotation hold?

Measure and you will know. Are you constrained in memory? Can you figure out the correct size up front? It will be more efficient to reserve than it will be to shrink after the fact. In general I am inclined to agree on the premise that most uses are probably fine with the slack.

If yes, what's the proper way of shrinking an STL container's capacity to its size (at least for std::vector).

The comment does not only apply to shrink_to_fit, but to any other way of shrinking. Given that you cannot realloc in place, it involves acquiring a different chunk of memory and copying over there regardless of what mechanism you use for shrinking.

And if there's a better way to shrink a container, what's the reason for the existence of shrink_to_fit after-all?

The request is non-binding, but the alternatives don't have better guarantees. The question is whether shrinking makes sense: if it does, then it makes sense to provide a shrink_to_fit operation that can take advantage of the fact that the objects are being moved to a new location. I.e., if the type T has a noexcept(true) move constructor, it will allocate the new memory and move the elements.

While you can achieve the same externally, this interface simplifies the operation. The equivalent to shrink_to_fit in C++03 would have been:

std::vector<T>(current).swap(current);

But the problem with this approach is that when the copy is done to the temporary it does not know that current is going to be replaced, there is nothing that tells the library that it can move the held objects. Note that using std::move(current) would not achieve the desired effect as it would move the whole buffer, maintaining the same capacity().

Implementing this externally would be a bit more cumbersome:

{
   std::vector<T> copy;
   if (noexcept(T(std::move(declval<T>())))) {
      copy.assign(std::make_move_iterator(current.begin()),
                  std::make_move_iterator(current.end()));
   } else {
      copy.assign(current.begin(), current.end());
   }
   copy.swap(current);
}

Assuming that I got the if condition right... which is probably not what you want to write every time that you want this operation.

Right way to reserve or shrink a vector to a known future capacity need

Use something like this:

template <typename VECTOR>
void setCapacity(VECTOR &vector, std::size_t capacity) {
    if (capacity < vector.size()) capacity = vector.size();
    if (vector.capacity() > capacity) {
        VECTOR v;
        v.reserve(capacity);
        std::size_t size = vector.size();
        for (std::size_t i = 0; i < size; i++) {
            v.emplace_back(std::move(vector[i]));
        }
        vector.swap(v);
    } else {
        vector.reserve(capacity);
    }
}

It sets vector capacity to capacity (if possible), while retaining elements. And it only does one allocation.

implementation of shrink_to_fit for string and vector are different?

Modern implementations of std::string generally provide "short string optimization", which means that strings under a certain length don't require a separate allocation, but are stored inside the std::string object itself (typically in the space that would be used for some of the pointers). So, this means that you cannot get less capacity than - in your case - 15 (which rings right, as that's 16 with the NUL terminator, and that's two 64 bit pointers), as it's stored straight in the string object, when there's no longer anything else to deallocate.

Besides, you are comparing apples to oranges; nothing stops std::vector from implementing a similar optimization for smaller types¹, but you are comparing a std::vector<int> (whose elements are generally 4 bytes, so only 4 would fit in the aforementioned 16 bytes) with a std::string (whose elements are 1-byte char). A more proper comparison would be against std::vector<char>.

---

1. actually, as pointed out in the comments, the current standard places requirements incompatible with such an optimization; still, the main point stands: when comparing two containers, you should do so making sure that the "boundary conditions" are the same, so you can spot the actual implementation differences (std::string does SSO, std::vector<char> doesn't) without being distracted by differences that arise from the fact that you are comparing them against different problems.

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

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).

Shrink std::vector 's size to fit its actual data to save memory usage? vec.swap() doesn't work in MSVC?

Check the capacity() of the vector. You will most probably find that the vector in fact reduced its memory usage. What you are seeing is probably malloc() implementation not releasing memory back to the OS.

Will `resize` have any risk to reduce the vector capacity?

No, the vector's capacity will not be reduced by reserve or resize.

std::vector::reserve:

If new_cap is [not greater than capacity] ... no iterators or references are invalidated.

std::vector::resize

Vector capacity is never reduced when resizing to smaller size because that would invalidate all iterators, rather than only the ones that would be invalidated by the equivalent sequence of pop_back() calls.

Relevant part of the standard

reduce the capacity of an stl vector

std::vector<T>(v).swap(v);

Swapping the contents with another vector swaps the capacity.

  std::vector<T>(v).swap(v); ==> is equivalent to 

 std::vector<T> tmp(v);    // copy elements into a temporary vector
         v.swap(tmp);              // swap internal vector data

Swap() would only change the internal data structure.

shrinking a vector

The usual trick is to swap with an empty vector:

vector<vertex>(vertexvector.begin(), vertexvector.end()).swap(vertexvector);

---

Related Topics