随机访问和 push_back 是否可以在 C++ 中使元素无效？

Question

基本上，我需要能够使用像

push_back()

这样的操作+随机访问像

std::vector

这样的列表，同时还要保持它的指针有效性，就像

std::list

一样。这可能吗？

我正在使用指向列表中各种元素的指针，虽然

std::vector

提供对元素的随机访问，但一切都在

push_back()

时失效。

Answer 1

也许你听说过哈希链表这样的数据结构？这个数据结构是链表的扩展，它在普通链表之上维护了一个额外的数组，这个数组的元素个数与链表的元素个数相同，只是它的元素是指针到相应的链表元素。这种数据结构的优点是它允许随机访问并利用碎片化内存。但这似乎与您的问题描述有些偏差？我不确定这是否能满足您的需求..

代码就这样（非常抱歉，我写答案的时间太少所以没有真正编译运行，可能代码还是有bug吧，哈哈哈）：

#include <list>
#include <vector>

templete<typename T>
class CHashList
{
public:
  std::list<T> m_data;
  std::vector<T*> m_pointer;
public:
  void push_back(T newData)
  {
    m_data.push_back(newData);
    m_pointer.push_back(&m_data.back());
  }
  T& operation[](int i)
  {
    return *m_pointer[i];
  }
  // other operations...
};

希望对你有帮助

Answer 2

就像 Nathan 指出的那样，

std::deque

在推回时只会使迭代器无效，所以这就是我所做的。

Answer 3

Boost 的

stable_vector

为您的要求提供现成的解决方案。

来自它的文档：

和vector一样，迭代器是随机访问的。

stable_vector

不提供元素连续性；作为这种缺席的交换，容器是稳定的，即只要元素未被擦除

，对

stable_vector元素的引用和迭代器就保持有效。