使用std容器（如向量，列表，队列，...）的稳定内存地址 [英] Stable memory addresses using a std container (like vector, list, queue, ...)

问题描述

注意：我没有意识到指针被认为是迭代器，因此我们可以认为我所说的缺少内存地址稳定性 em> iterator invalidation 。请阅读副本以获得我的问题的更抽象和更健全的版本。

我的问题与此问题相关：将C ++引用更改为push_back新元素到std :: vector 。 >

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

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

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

但是，我找不到这个指针稳定性列表。也许有一些优势，一些容器类这正是我想要的。当然，我总是可以使用 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; //当使用时，行为将变为未定义
 std :: priority_queue< Foo *，std :: vector< Foo *>，FooComparator> pq; 
 
 //模拟对象的创建和包含，而它们正在被其他结构处理。 
 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<< ; // dereference  - >可能segfault如果foos不*指针稳定* 
 pq.pop（）; 
} 
 
 std :: cout<< std :: endl; 
 return 0; 
} 
  

解决方案

/引用和迭代器无效的所有标准容器。即使 std :: vector< T> 也可以是一个选项，如果您可以预测最大容量：

• 在 std :: vector< T> 结尾处添加/删除对象保持指针和迭代器稳定，除非 std ::向量< T> 需要重新分配其内部结构。也就是说，当一个对象被添加并且 v.size（）== v.capacity（）时，指针和迭代器才会失效。您可以使用 v.reserve（n）来保留空间。


• 在<$ c $


• 在 std中的任何位置添加/删除对象： ：list< T> 保持指针和迭代器的稳定。

显然，在所有情况下都无效。但是，对其他对象的指针和迭代器遵守上面的规则。

操作和内存的开销按容器显示的顺序增加。也就是说，最好使用 std :: vector< T> 并提前分配足够的内存以保持对象的稳定。如果您无法预测所需的最大大小，则 std :: deque< T> 是下一个最佳选项： std :: deque< T& 是固定大小数组的数组，即每个对象的开销相对较小，内存分配相对较少。只有当你需要保持两个指针和迭代器表，不能断言容器的大小， std :: list< T> 是一个合理的选择。为了降低每个对象的开销，您可以考虑使用具有与 std :: list< 0相同的无效约束的 std :: forward_list< T>

我会使用 std :: vector< T> ，具有足够的保留内存。如果我不能，我会使得我可以使用 std：vector< T> 。只有这是真的不可能的，我会考虑使用 std :: deque< T> 来存储对象。 ...我很少使用 std :: list< T> ，因为几乎没有任何理由使用它。

Note: I didn't realize that pointers are to be considered iterators, hence one may fairly argue that what I call lack of memory address stability should be called iterator invalidation. Please read the duplicate for a more abstract and sound version of my question.

My question is related to this one: C++ reference changes when push_back new element to std::vector .

I want to work with a set of objects which should, for simplicity, only exist once in memory. Therefore I want to use a container, like std::vector, to store all the objects once. Then I will use a pointer to the objects in other structures. Unfortunately, std::vector may change the memory address of it's elements, hence using pointers to these elements is ill-defined. I need the pointers, as I want to refer to these objects using other structures, like std::priority_queue or other std data structures.

In the specific case the objects are labels for connections in a graph algorithm, meaning that they are created throughout the algorithm and hence cannot be pre-allocated. This means that a std::vector is not adequate, as it may relocate its content, invalidating pointers to these labels which may exist in std::priority_queues or other data structures.

However, the only moments I need the labels, is when they are created or when I can access them from data structures other than the containing data structure. Hence I never need to get the n-th element from the container, I only need to be able to keep objects on the stack or the heap and get the pointer when they are created to use it in other structures. Finally, when the container is popped from the stack, the elements in it need to be cleaned up nicely. I thought a std::list may be appropriate, as my knowledge of an abstract linked list never needs to reallocate; allowing for stable pointers.

However, I cannot find anywhere that this pointer stability is true for std::lists. And maybe there is something superior, some container class which does exactly what I want. Of course, I can always use new, append all the pointers to a std::list and iterate doing a delete at the end. But this is not my preferred way, as it takes more memory management as I think should be needed for just getting stable pointers.

Question: Is std::list pointer stable? Is there a better solution than std::list?

To illustrate the problem, I also made this example: http://ideone.com/OZYeuw . Replace the std::list with a std::vector, and the behavior becomes undefined.

#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;
}

解决方案

There are specific rules for pointer/reference and iterator invalidation for all of the standard containers. Even std::vector<T> may be an option if you can predict the maximum capacity:

• Adding/removing objects at the end of a std::vector<T> keeps pointers and iterators stable unless the std::vector<T> needs to reallocate its internal structure. That is, pointers and iterators get only invalidated when an object is added and v.size() == v.capacity(). You can use v.reserve(n) to reserve space.
• Adding/removing objects at either end of a std::deque<T> keeps pointers stable but does invalidate iterators.
• Adding/removing objects anywhere in a std::list<T> keeps both pointers and iterators stable.

Obviously, pointers and iterators to removed objects are invalidated in all case. However, pointer and iterators to other objects obey the rules above.

The overhead for operations and memory increase in the order the containers are show. That is, ideally you'd use a std::vector<T> and allocate enough memory ahead of time to keep the objects stable. If you can't predict the maximum size needed, std::deque<T> is the next best option: std::deque<T> is an array of fixed sized arrays, i.e., there is a relatively small per object overhead and relatively few memory allocation. Only if you need to keep both pointers and iterators table, can't predicate the size of the container, std::list<T> is a reasonable option. To lower the per-object overhead you might consider using a std::forward_list<T> which has the same invalidation constraints as std::list<T> but can only be traversed once and is somewhat more inconvenient to use.

I'd use a std::vector<T> with sufficient reserved memory. If I can't, I would make so that I can use a std:vector<T>. Only if that is really impossible, I would consider using a std::deque<T> for storing objects. ... and I rarely use std::list<T> as there is hardly any reason to ever use it.

这篇关于使用std容器（如向量，列表，队列，...）的稳定内存地址的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！