1

I have a

vector< pair<vector<double> , int>> samples;

This vector will contain a number of elements. For efficiency rason I initialize it in this way:

vector< pair<vector<double> , int>> samples(1000000);

I know the size in advance (not a compile-time) that I get from another container. The problem is that I have to decrease of 1 element the dimension of vector. Indeed, this case isn't a problem because resize with smaller dimension than the initial no do reallocation.I can do

samples.resize(999999);

The problem is that in some cases rather than decrease the dimension of 1 element I have to increment the dimension of an element. If I do

samples.resize(1000001);

there is the risk of do reallocation that I want avoid for efficiency rasons. I ask if is a possible solution to my problem do like this:

vector< pair<vector<double> , int> samples;
samples.reserve(1000001);
samples.resize(1000000);
.
. Elaboration that fill samples 
.
samples.resize(1000001); //here I don't want reallocation

or if there are better solutions? Thanks in advance!

(I'm using C++11 compiler)

jww
  • 97,681
  • 90
  • 411
  • 885
Nick
  • 1,439
  • 2
  • 15
  • 28
  • 6
    That is what `vector::reserve` is for. Are you looking for a [code review](https://codereview.stackexchange.com/)? – nwp Jun 02 '17 at 15:31
  • 1
    `vector< pair , int> samples;` isn't valid C++. Did you mean `vector< pair , int> > samples;`? – cdhowie Jun 02 '17 at 15:32
  • @ChrisDrew No, I know. But in the elaboration I have the necessity of increment the initial size of 1 – Nick Jun 02 '17 at 15:35
  • @cdhowie Yes, you are right. Correct the code – Nick Jun 02 '17 at 15:36
  • @nwp I do not want to examine the correctness of my code but find a solution to the problem. Instead of just saying how to do it? I also tried to propose a solution. – Nick Jun 02 '17 at 15:47
  • 1
    I don't see the problem here. Is your solution working as you expect? – iehrlich Jun 02 '17 at 15:51
  • @iehrlich I repeat. I want avoid reallocation, that can happen behind the hood and I don't see it – Nick Jun 02 '17 at 15:55
  • 1
    But you do. Among other wonderful things that you might've found in C++ reference manuals, there's [this](http://en.cppreference.com/w/cpp/container/vector/reserve) and [this](http://en.cppreference.com/w/cpp/container/vector/capacity). These two links fully answer your question. – iehrlich Jun 02 '17 at 16:05
  • 1
    probably a duplicate of [When does a std::vector reallocate its memory array?](https://stackoverflow.com/questions/5410035/when-does-a-stdvector-reallocate-its-memory-array) – underscore_d Jun 02 '17 at 16:19
  • You can go for a higher limit and then use [shrik_to_fit](http://en.cppreference.com/w/cpp/container/vector/shrink_to_fit). Although you are not guaranteed to reduce the capacity. – gudge Jun 02 '17 at 16:48
  • Why did you think this was relevant? They want to _avoid_ reallocation by setting a _higher_ `capacity` than they need. `shrink_to_fit()` is explicitly _allowed_ to reallocate as part of _reducing_ the `capacity`. – underscore_d Jun 03 '17 at 09:24

3 Answers3

5

Just wrote a sample program to demonstrate, that resize is not going to reallocate space if capacity of the vector is sufficient:

#include <iostream>
#include <vector>
#include <utility>
#include <cassert>

using namespace std;

int main() 
{
  vector<pair<vector<double>, int>> samples;
  samples.reserve(10001);

  auto data = samples.data();

  assert(10001==samples.capacity());

  samples.resize(10000);
  assert(10001 == samples.capacity());
  assert(data == samples.data());

  samples.resize(10001); //here I don't want reallocation
  assert(10001==samples.capacity());
  assert(data == samples.data());  
}

This demo is based on assumption that std::vector guarantees contiguous memory and if data pointer does not change, than no realloc took place. This is also evident, by capacity() result to remain 10001 after every call to resize().

cppreference on vectors:

The storage of the vector is handled automatically, being expanded and contracted as needed. Vectors usually occupy more space than static arrays, because more memory is allocated to handle future growth. This way a vector does not need to reallocate each time an element is inserted, but only when the additional memory is exhausted. The total amount of allocated memory can be queried using capacity() function.

cppreference on reserve:

Correctly using reserve() can prevent unnecessary reallocations, but inappropriate uses of reserve() (for instance, calling it before every push_back() call) may actually increase the number of reallocations (by causing the capacity to grow linearly rather than exponentially) and result in increased computational complexity and decreased performance.

cppreference also sates to resize:

Complexity

Linear in the difference between the current size and count. Additional complexity possible due to reallocation if capacity is less than count

ovanes
  • 5,483
  • 2
  • 34
  • 60
  • At first is vector< pair , int>> samples(1000000); Later I do samples.resize(1000001), this could cause reallocation if contiguous memory is busy or not? – Nick Jun 02 '17 at 16:37
  • 1
    Yes, it might resize. Thus is better to create an empty vector, do the reserve(1000001) and then resize(1000000) to the size needed. – ovanes Jun 02 '17 at 16:42
  • even creating a vector with count of `0`, e.g. `vector zero{0};` might allocate space. But that space can be very small like 1 element. In the impl that I have tested. – ovanes Jun 02 '17 at 16:48
1

I ask if is a possible solution to my problem do like this:

samples.reserve(1000001);
samples.resize(1000000);

Yes, this is the solution.

or if there are better solutions?

Not that I know of.

Community
  • 1
  • 1
eerorika
  • 232,697
  • 12
  • 197
  • 326
  • Thanks. I know that resize() call reserve. Thus, when later reserve(1000001) I do resize(1000000) that call reserve(1000000): Does this invalid the previous call of reserve? – Nick Jun 02 '17 at 16:11
  • 1
    @Umbert Removing elements from the vector does not cause reallocation. The reserve does not become "invalid". – eerorika Jun 02 '17 at 16:14
  • 2
    @Umbert: `resize()` doesn't call `reserve()`. Also: "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." – erenon Jun 02 '17 at 16:14
  • Responding to my previous comment when reserve is called with a minor capacity than previous happens nothing ( I saw it in the documentation). Thus the code should works! – Nick Jun 02 '17 at 16:18
  • @erenon Here https://stackoverflow.com/questions/37196329/c-standard-vector-resize-function the opposite is said instead – Nick Jun 02 '17 at 16:24
  • @Umbert: Please note, reserve will only do anything if the requested size is greater than the current capacity, which is not your second case. – erenon Jun 03 '17 at 07:49
1

As I recall when resize less than capacity, There will not be reallocation. So, your code will work without reallocation.

cppreference.com
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.

Ian.Zhang
  • 151
  • 1
  • 10