2

The main issue with vectors and pointers to their elements is that they can be reallocated in memory whenever a push_back is called, rendering the pointer invalid.

I am trying to implement a suffix trie, where I store a data structure node in a vector of nodes. I know that for a string of size n the number n(n+1)/2 is an upperbound for the number of nodes in the trie.

So will the code

std::string T = "Hello StackOverflow!"; std::vector<Node> nodes; int n = T.length(); nodes.reserve(n*(n+1)/2);

guarantee that any pointers I create referring to elements of nodes will not be invalidated? i.e. will this guarantee that the vector is not reallocated?

Edit: I've implemented this and I keep getting the following error at runtime.

terminate called after throwing an instance of 'std::out_of_range' what(): basic_string::at: __n (which is 0) >= this->size() (which is 0) Aborted (core dumped)

Any ideas what could be causing this?

Improve this question
3
  • 2
    Check out std::deque. push_back doesn't invalidate references/pointers (but iterators are invalidated). en.cppreference.com/w/cpp/container/deque Commented Jan 9, 2017 at 21:47
  • @Kevin: The question is about std:::vector, not std::deque though :). Commented Jan 9, 2017 at 21:56
  • @AlexD I know, I'm just mentioning an alternative if he wants a container that supports push_back and doesn't invalidate references. std::deque has its uses but is often ignored. The answers below are probably fine for this question though. Commented Jan 9, 2017 at 21:58

2 Answers 2

Reset to default
5

According to the standard (N4140):

23.3.6.3 vector capacity
....

void reserve(size_type n);

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

23.3.6.5 vector modifiers
....

void push_back(const T& x); void push_back(T&& x);

Remarks: Causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

But will resereve() fix the capacity of the vector the the given size?
@LukeCollins that is exactly what the reserve function does
The standard: After reserve(), capacity() is greater or equal to the argument of reserve if reallocation happens; and equal to the previous value of capacity() otherwise.
@M.M Thank you - I wasn't sure if it had any conditions. So given that I am sure that my vector exceeds n(n+1)/2, I should be fine?
3

You can be certain that your pointers will not be invalidated if you are careful. See std::vector::push_back. It says this about invalidation :

If the new size() is greater than capacity() then all iterators and references (including the past-the-end iterator) are invalidated. Otherwise only the past-the-end iterator is invalidated.

Simply make sure you do not push_back beyond capacity or call other methods that may invalidate. A list of methods that invalidate is available here in section 'Iterator invalidation'.

Improve this answer

5 Comments

But will resereve() fix the capacity of the vector the the given size?
@LukeCollins std::vector::reserve does not set capacity to an exact value, but it does guarantee that the new capacity will be at least as large as the value supplied to reserve.
Thanks for the reply. Can you help me with the edit above?
@LukeCollins this is an unrelated problem. From the error message, you are access the first character of a string that contains no characters.
#Francois, could you help me with this? stackoverflow.com/questions/41558092/…

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.