Std::Vector Resize Downward

does std::vector::resize() downward take O(1) time if the element type is a primitive?

There seems to be no guarantee in the standard for this complexity. However, as you point out, there seems to be no reason for greater-than-constant complexity either in that case. Complexity is only guaranteed to be O(n).

I'd be surprised to find a compiler that implemented it as linear for primitive types, but the best way to be sure with your compiler setup would be to make a simple test.

Resizing std::vector without destroying elements

std::vector is not a solution in this case. You don't want to resize/clear/(de)allocate all over again? Don't.

1. fillVector() fills 'vector' with number of elements known in each iteration.
2. Vector is internally represented as continuous block of memory of type T*.
3. You don't want to (de)allocate memory each time.

Ok. Use simple struct:

struct upTo4ElemVectorOfInts
{
  int data[4];
  size_t elems_num;
};

And modify fillVector() to save additional info:

void fillVector(upTo4ElemVectorOfInts& vec)
{
  //fill vec.data with values
  vec.elems_num = filled_num; //save how many values was filled in this iteration
}

Use it in the very same way:

upTo4ElemVectorOfInts myVector;

for (int i = 0; i < 100; ++i)
{
  fillVector(myVector);
  //use of myVector:
  //- myVector.data contains data (it's equivalent of std::vector<>::data())
  //- myVector.elems_num will tell you how many numbers you should care about
  //nothing needs to be resized/cleared
}

Additional Note:

If you want more general solution (to operate on any type or size), you can, of course, use templates:

template <class T, size_t Size>
struct upToSizeElemVectorOfTs
{
  T data[Size];
  size_t elems_num;
};

and adjust fillVector() to accept template instead of known type.

This solution is probably the fastest one. You can think: "Hey, and if I want to fill up to 100 elements? 1000? 10000? What then? 10000-elem array will consume a lot of storage!".
It would consume anyway. Vector is resizing itself automatically and this reallocs are out of your control and thus can be very inefficient. If your array is reasonably small and you can predict max required size, always use fixed-size storage created on local stack. It's faster, more efficient and simpler. Of course this won't work for arrays of 1.000.000 elements (you would get Stack Overflow in this case).

Does std::vector::resize() ever reallocate when new size is smaller than current size?

No, resizeing to a smaller size will never reallocate.

In case the container shrinks, all iterators, pointers and references to elements that have not been removed remain valid after the resize and refer to the same elements they were referring to before the call.

(From here)

Given that, we can be sure that a reallocation cannot have happened.

Vector Resizing in C++ (Scaling Down )

The resize() will resize the vector and make the last elements invalid, but not as you assume. You can clearly see by checking how many elements the vector has in it that there are 10. However, this does not mean that the allocated memory would be thrown away or that the removed elements would be invalid in some sense, especially them being integers.

THe vector may reallocate memory, if it so chooses. Then the last elements would be impossible to access.

Basically you are invoking undefined behaviour by accessing a vector over its limits. Anything can happen. In this case the implementation chose not to reallocate the memory (which is smart, since the difference is so small), so you can point to elements out of bounds.

If the elements were objects, they would've been deleted and you would have even more undefined behaviour by dereferencing a deleted object.

Does resize() to a smaller size discard the reservation made by earlier reserve()?

vector<T>::resize(0) should not cause a reallocation or deletion of allocated memory, and for this reason in most cases is preferable to vector<T>::clear().

For more detail see answers to this question: std::vector resize downward

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.

Does resizing a vector invalidate iterators?

Edited with more careful wording

yes, resizing a vector might invalidate all iterators pointing into the vector.

The vector is implemented by internally allocating an array where the data is stored. When the vector grows, that array might run out of space, and when it does, the vector allocates a new, bigger, array, copies the data over to that, and then deletes the old array.

So your old iterators, which point into the old memory, are no longer valid.
If the vector is resized downwards (for example by pop_back()), however, the same array is used. The array is never downsized automatically.

One way to avoid this reallocation (and pointer invalidation) is to call vector::reserve() first, to set aside enough space that this copying isn't necessary. In your case, if you called a.reserve(3) before the first push_back() operation, then the internal array would be big enough that the push_back's can be performed without having to reallocate the array, and so your iterators will stay valid.

When shrinking a container via resize, in which order are the elements destroyed?

Based on the January 2012 working draft

The January 2012 working draft contains the C++11 standard plus minor editorial changes.

Source, working draft

For vector:

void resize(size_type sz);
Effects: If sz <= size(), equivalent to erase(begin() + sz, end());. If size() < sz, appends
sz - size() value-initialized elements to the sequence.

vector::erase does not specify the order of removal. I would expect it to be in order from begin() + sz to end(), because that makes sense to me, but that is just my expectation. I can't find anything about it in the standard.

The implementation of vector distributed with Visual Studio 2013 does appear to indeed erase in that order, as does MinGW's g++ 4.8.1 as well as g++ 4.7.3 (not MinGW). These are the compilers I happen to have easy access to.

In the same standard, for list:

void resize(size_type sz);
1 Effects: If size() < sz, appends sz - size() value-initialized elements to the sequence. If sz <= size(), equivalent to

list<T>::iterator it = begin();
advance(it, sz);
erase(it, end());

and

void resize(size_type sz, const T& c);
Effects:

if (sz > size())
    insert(end(), sz-size(), c);
else if (sz < size()) {
    iterator i = begin();
    advance(i, sz);
    erase(i, end());
}
else
    ; // do nothing

It then goes on to specify absolutely nothing useful about ordering for list::erase.

The implementation of list distributed with Visual Studio 2013 does appear to erase in reverse order, while MinGW's g++ 4.8.1 and g++ 4.7.3 (not MinGW) do not.

Based on the latest working draft at the time of writing

Working draft

For vector

void resize(size_type sz);
Effects: If sz <= size(), equivalent to calling pop_back() size() - sz times. If size() < sz,
appends sz - size() default-inserted elements to the sequence.

This indicates that elements are removed in reverse order.

For list:

void resize(size_type sz);
1 Effects: If size() < sz, appends sz - size() value-initialized elements to the sequence. If sz <= size(), equivalent to

list<T>::iterator it = begin();
advance(it, sz);
erase(it, end());

and

void resize(size_type sz, const T& c);
Effects:

if (sz > size())
    insert(end(), sz-size(), c);
else if (sz < size()) {
    iterator i = begin();
    advance(i, sz);
    erase(i, end());
}
else
    ; // do nothing

It then goes on to specify absolutely nothing useful about ordering for list::erase.

For deque the standard specifies the same behavior as for vector.

what's wrong with vector::reserve?

This is a common mistake. std::vector::reserve does not create elements or change the size of the container; you're actually causing undefined behavior. reserve changes just the capacity. You are looking for std::vector::resize to change the size. Here's an example for clarity:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> ivec;
    std::cout << ivec.size() << " - " << ivec.capacity() << '\n'; // 0 - 0
    ivec.reserve(100);
    std::cout << ivec.size() << " - " << ivec.capacity() << '\n'; // 0 - 100
    ivec.resize(30);
    std::cout << ivec.size() << " - " << ivec.capacity() << '\n'; // 30 - 100
}

---

Related Topics