向量和指针 [英] Vectors and Pointers

问题描述

向量和指向其元素的指针的主要问题是，每当调用push_back时，它们都可以在内存中重新分配，从而使指针无效.

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.

我正在尝试实现后缀特里，在其中将数据结构node存储在节点向量中.我知道对于大小为 n 的字符串，数字 n(n + 1)/2 是trie中节点数量的上限.

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.

代码也会

std::string T = "Hello StackOverflow!";
std::vector<Node> nodes;

int n = T.length();
nodes.reserve(n*(n+1)/2);

保证我创建的引用nodes元素的任何指针都不会失效?即能保证不重新分配向量吗?

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?

推荐答案

根据标准(N4140):

23.3.6.3向量容量
....

23.3.6.3 vector capacity
....

void reserve(size_type n);

....
在reserve()之后，如果capacity()大于或等于reserve的参数，则 重新分配发生；等于capacity()的先前值.重新分配发生 此时且仅当当前容量小于reserve()的参数时.

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

和

23.3.6.5矢量修饰符
....

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.

这篇关于向量和指针的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！