使用std容器的稳定内存地址(如vector,list,queue,...)

Question

注意:我没有意识到指针被认为是迭代器,因此有人可能会认为我所谓的缺乏内存地址稳定性应该称为迭代器失效.请阅读副本,以获得更抽象和更健全的问题.

我的问题与这个问题有关:当push_back新元素到std :: vector时,C++引用会发生变化.

我想使用一组对象,为简单起见,这些对象在内存中只存在一次.因此,我想使用一个容器,如std :: vector,来存储所有对象一次.然后我将使用指向其他结构中的对象的指针.不幸的是,std :: vector可能会改变它元素的内存地址,因此使用指向这些元素的指针是不明确的.我需要指针,因为我想使用其他结构来引用这些对象,比如std :: priority_queue或其他std数据结构.

在特定情况下,对象是图算法中连接的标签,这意味着它们是在整个算法中创建的,因此不能预先分配.这意味着std :: vector是不够的,因为它可能会重定位其内容,使指向std :: priority_queues或其他数据结构中可能存在的这些标签的指针无效.

但是,我需要标签的唯一时刻是创建它们的时候或者我可以从包含数据结构以外的数据结构访问它们.因此,我永远不需要从容器中获取第n个元素,我只需要能够将对象保留在堆栈或堆上,并在创建它们时获取指针以在其他结构中使用它.最后,当容器从堆栈中弹出时,其中的元素需要很好地清理.我认为std :: list可能是合适的,因为我对抽象链表的知识永远不需要重新分配; 允许稳定的指针.

但是,我无法找到std :: lists的指针稳定性为何.也许有一些优越的东西,一些容器类完全符合我的要求.当然,我总是可以使用new,将所有指针追加到std :: list并迭代在最后执行删除.但这不是我喜欢的方式,因为它需要更多的内存管理,因为我认为应该只需要获得稳定的指针.

问题: std :: list 指针是否稳定？有比std :: list更好的解决方案吗？

为了说明这个问题,我也做了这个例子:http://ideone.com/OZYeuw.用std :: vector替换std :: list,行为变得不确定.

#include <iostream>
#include <list>
#include <queue>
#include <vector>

struct Foo {
    Foo(int _a) : a(_a) {}
    int a;
};

struct FooComparator {
    bool operator()(Foo *a, Foo *b) { return a->a < b->a; }
};

int main() {
    std::list<Foo> foos;
    //std::vector<Foo> foos; // when used instead, the behaviour will become undefined
    std::priority_queue<Foo *, std::vector<Foo *>, FooComparator> pq;

    // Simulate creation and 'containment' of objects, while they are being processed by other structures.
    for(int i=0; i<100; ++i) {
        foos.push_back(Foo((100-i) % 10));
        pq.emplace(&foos.back());
    }

    while(not pq.empty()) {
        std::cout << pq.top()->a << " "; // the dereference -> may segfault if foos is not *pointer stable*
        pq.pop();
    }

    std::cout << std::endl;
    return 0;
}

Answer 1

对于所有标准容器,指针/引用和迭代器失效都有特定的规则.std::vector<T>如果您可以预测最大容量,甚至可能是一个选项:

• std::vector<T>除非std::vector<T>需要重新分配其内部结构,否则在结尾处添加/删除对象会使指针和迭代器保持稳定.也就是说,指针和迭代器只在添加对象时才会失效v.size() == v.capacity().您可以v.reserve(n)用来预留空间.
• 在一端添加/删除对象std::deque<T>会使指针保持稳定,但会使迭代器无效.
• 在a中的任何地方添加/删除对象可以std::list<T>使指针和迭代器保持稳定.

显然,删除对象的指针和迭代器在所有情况下都是无效的.但是,指向其他对象的指针和迭代器遵循上述规则.

操作和内存的开销按容器显示的顺序增加.也就是说,理想情况下,您要使用a std::vector<T>并提前分配足够的内存以保持对象稳定.如果无法预测所需的最大大小,std::deque<T>则是下一个最佳选择:std::deque<T>是一个固定大小的数组数组,即每个对象开销相对较小且内存分配相对较少.只有当你需要保留指针和迭代器表时,才能预测容器的大小,std::list<T>是一个合理的选择.要降低每个对象的开销,您可以考虑使用std::forward_list<T>具有相同失效约束的开销,std::list<T>但只能在一个方向上遍历,并且使用起来更不方便.

我使用了std::vector<T>足够的保留内存.如果我不能,我会这样做,我可以使用std:vector<T>.只有在真的不可能的情况下,我会考虑使用a std::deque<T>来存储对象.......我很少使用,std::list<T>因为几乎没有理由使用它.