c++ - 填充指向 vector 元素的指针的无序队列

Question

我有一个数据结构，其工作方式类似于无序队列和一个充满A 类 对象的vector。我想用指向 vector 中每个对象的指针一次填充队列一个元素(使用 push() 函数)。

此实现需要:

1. 跟踪 vector 中对象的原始顺序，即使存储在队列中的指针根据比较器和对象的值交换位置
2. 允许继续向 vector 中添加对象(同样注意顺序)
3. 允许对象根据它们在 vector 中的原始顺序进行编辑，而无需将所有内容重新复制到队列(因此​​，指针队列而不是对象队列)

为了解决这个问题，我已经用头撞墙好几个小时了。现在我有两个解决方案，但都因不同原因而失败。

第一个是

for(auto i = vector.begin(); i < vector.end(); i++)
{
    queue->push(new A (*i));
}

在编辑 vector 中的元素之前，它一直运行良好，此时我意识到它似乎对队列中的值没有任何影响。也许指针在某处解耦了。

第二个是

for(A* ptr = vector.data(); ptr <= (vector.data()+vector.size()-1); ptr++)
{
    A** bar = new A*;
    *bar = ptr;
    queue->push(*bar);
}

据我所知，这个成功地将指针与 vector 中的对象匹配，但由于某些其他原因我无法判断在对队列执行一些额外操作后导致核心中止(pop()、max() 等)。

如果有人能提供任何建议，我将不胜感激。

哦，在我忘记之前，尽管我很想使用 shared_pointers 或 unique_pointers 或 boost，但我限制了它只是 STL 和 vector、list 和 deque。没有其他容器。

Answer 1

你的第一个和第三个需求可以通过指针满足，实现起来并不困难。我建议你做的是不要使用 auto因为它会给你一个迭代器对象并将其转换为指针可能很困难。

关于您的第二个要求，它无法完成，因为向 vector 中添加内容会触发内存的重新分配以增加 vector 容量，除非您事先知道 vector 应容纳的最大对象数 .为了满足您的所有要求，最好的解决方案是使用 vector 索引而不是指针来“链接”对象。这也更简单。

但话又说回来，如果你从 vector 中删除东西，那么你必须更新整个队列。允许您做几乎所有事情的最灵活的解决方案是使用列表而不是 vector 。但它可能会对性能产生影响，您在做出选择之前必须三思。

为了让它与 vector 和指针一起工作，我会这样做:

class A { /* your class here */ };
vector<A> vec;

/* Avoid vector reallocating memory. */
vec.reserve(MAX_NUMBER_OF_OBJECTS);

/* Then, populate the vector. */
/* No need for fully populating it though. */
/* ... */

/* Populate the queue. */
queue<A*> q;
for(int i = 0; i < vec.size(); i++){
  q.push(&vec[i]);
}