0

I was debugging an issue and realized that when a vector is resizing, the reference will not work anymore. To illustrate this point, below is the minimal code. The output is 0 instead of 1. Is there anyway that we can prevent this happen except reserving a large space for x? 

#include <iostream>
#include <vector>
using namespace std;


vector<int> x{};

int main(){
  x.reserve(1);
  x.push_back(0);
  int & y = x[0];
  x.resize(10);
  y=1;
  cout << x[0] << endl;
  return 0;
}
drbombe
  • 609
  • 7
  • 15
  • 1
    .reserve() will find a new memory location/address to create the space you want. You would need to assign y to x[0] again after the resize. – Omid CompSCI May 28 '19 at 03:12
  • @OmidCompSCI sometimes push_back() can trigger resize implicitly to make the bug difficult to find. Any best practice to resolve this? – drbombe May 28 '19 at 03:14
  • Use a deque instead of vector if you really need this functionality – smac89 May 28 '19 at 03:15
  • As far as “best practice” — don’t keep references to elements inside a vector that you want to resize. – Dietrich Epp May 28 '19 at 03:17
  • @drbombe, agreed with Dietrich. – Omid CompSCI May 28 '19 at 03:17
  • @smac89 this seems a good idea when continuous memory is not essential. Anyway that we can let the reference to track the object? Smart reference? Smarter pointer? – drbombe May 28 '19 at 03:18
  • @drbombe Yeah. That's easy to do. Keep a reference to the `vector` and the index. See my answer. – David Schwartz May 28 '19 at 03:19
  • Not possible. Smart pointers are only good for freeing memory that has gone out of scope and will only result in quickly freeing any memory it points within the vector when the vector reallocates everything. – smac89 May 28 '19 at 03:20
  • @smac89 I mean smartER pointer :) – drbombe May 28 '19 at 03:23
  • 1
    If they get any smarter, they would have to copy the object :) – smac89 May 28 '19 at 03:25
  • Possible duplicate of [Keeping a reference to a vector element valid after resizing](https://stackoverflow.com/questions/50867703/keeping-a-reference-to-a-vector-element-valid-after-resizing) – smac89 May 28 '19 at 03:33
  • Possible duplicate of [Iterator invalidation rules](https://stackoverflow.com/questions/6438086/iterator-invalidation-rules) – L. F. May 28 '19 at 09:47

4 Answers4

1

This is called invalidation and the only way you can prevent it is if you make sure that the vector capacity does not change. 

x.reserve(10);
x.push_back(0);
int &y = x[0];
x.resize(10);
Dietrich Epp
  • 205,541
  • 37
  • 345
  • 415
  • If you were to do this, there is no point in doing the resize then, but yes good explanation – Omid CompSCI May 28 '19 at 03:16
  • This is the only answer that will actually yield the correct result as long as you know before hand how big the vector should be. Otherwise, I think the best thing to do is go with `std::deque` – smac89 May 28 '19 at 03:29
  • @DrPhil: You can't put references in a vector. – Dietrich Epp May 28 '19 at 13:22
1

The only way I can think of is to use std::deque instead of std::vector.

The reason for suggesting std::deque is this (from cppreference):

The storage of a deque is automatically expanded and contracted as needed. Expansion of a deque is cheaper than the expansion of a std::vector because it does not involve copying of the existing elements to a new memory location.

That line about not copying is really the answer to your question. It means that the objects remain where you placed them (in memory) as long as the deque is alive.

However, on the very next line it says:

On the other hand, deques typically have large minimal memory cost; a deque holding just one element has to allocate its full internal array (e.g. 8 times the object size on 64-bit libstdc++; 16 times the object size or 4096 bytes, whichever is larger, on 64-bit libc++).

It's now up to you to decide which is better - higher initial memory cost or changing your program's logic not to require referencing the items in the vector like that. You might also want to consider std::set or std::unordered_set for quickly finding an object within the container

smac89
  • 39,374
  • 15
  • 132
  • 179
0

There are several choices:

  1. Don't use a vector.
  2. Don't keep a reference.
  3. Create a "smart reference" class that tracks the vector and the index and so it will obtain the appropriate object even if the vector moves.
David Schwartz
  • 179,497
  • 17
  • 214
  • 278
  • Seems like overkill just to track a single object within said vector. How would it know that an object within the vector has been copied to a new location? – smac89 May 28 '19 at 03:23
  • @smac89 It would have a dereference operation (or a cast) that just returned `vector[index]`. – David Schwartz May 28 '19 at 03:53
  • @drbombe Look at the code for any smart pointer. You would need two member variables, one some kind of pointer/reference to the vector and one an integer index. The dereference operation would just return `vector[index]`. If you want to be fancy, you can make an insert operation that adds an object to a vector and returns an instance of this reference. (Similar code to `make_shared` or `make_unique`.) – David Schwartz May 28 '19 at 03:53
0

You can create a vector of std::shared_ptr<> as well and keep the values instead of the interators.

Michael Chourdakis
  • 10,345
  • 3
  • 42
  • 78