矢量和指针

Question

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

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

代码也是如此

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

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

保证我创建的任何指针nodes都不会被无效？即这会保证向量不被重新分配吗？

---

编辑:我已经实现了这一点,并在运行时不断收到以下错误.

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)

可能导致这种情况的任何想法？

Answer 1

根据标准(N4140):

23.3.6.3载体容量
....

void reserve(size_type n);

....
之后reserve(),capacity()是大于或等于如果重新分配发生储备的参数; 并等于之前的capacity()其他值.当且仅当当前容量小于参数时,才会发生重新分配reserve().

和

23.3.6.5矢量修饰符
....

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

备注:如果新大小大于旧容量,则会导致重新分配.如果没有重新分配,插入点之前的所有迭代器和引用仍然有效.