c++ - 我应该使用std::list还是有更好的方法？

Question

我目前正在使用C++的2D几何编辑器进行编码。我有用户放置节点。可以通过选择2个节点来绘制直线和圆弧。

现在，我将节点存储在std::deque容器中(线和弧同样)，因为我想将节点的地址存储到每条线/弧中。当我实现移动节点的功能时，这使事情变得非常方便。如果要将实际节点存储在每个线/弧内，那么当我要移动节点时，我将不得不遍历整个线和弧结构以找到刚移动的节点并更新参数。该选项不是表上的选项。因此，需要能够在每个线/弧内存储节点的地址。

但是，我遇到了需要删除节点的问题。查看引用手册，似乎对于所有指针，当您从双端队列中删除一个元素时，这些指针都是无效的(除非该元素位于开头或结尾。为便于讨论，我将不考虑这种情况) 。这会导致擦除问题，因为现在，当删除一个节点并最终导致程序崩溃时，我所有的线/弧都将自己重新连接到其他节点，或者根本没有被绘制。

继续在线查看，我遇到了std::list(从我对阅读文档的理解来看)在删除其中一个元素时不会使任何指针或引用无效。这似乎是解决我的问题的一个很好的解决方案。

但是，我一直在堆栈溢出中寻找一点点，以了解使用列表和双端队列的优点/缺点。似乎更喜欢使用双端队列而不是列表。似乎列表访问速度比双端队列慢。这不好，因为我不确定用户要绘制多少个节点。就我所知，几何中可能有10,000+个节点，如果用户要移动节点，我不希望用户必须等待30秒让程序迭代所有元素以找到该节点(s)擦除。

因此，一方面，双端队列要快得多，但是一旦删除元素，所有的指针和引用都将失效。另一方面，std::list允许我擦除所需的任何元素，而不会使任何指针和引用无效，但与双端队列相比，速度较慢。

我正在考虑切换到列表，因为即使列表比较慢，如果我不能在不使指针和引用无效的情况下擦除元素，那么如果程序无法正常工作，那么在速度上就没有太多好处。

但是，在我的情况下，使用列表是否是最佳选择？有什么办法可以使用双端队列？还是我没有考虑过的第三种选择？

编辑:

我忘了提。我不喜欢列表的一件事是无法直接获取元素的数据(在std::deque和vector中，我可以使用at函数访问元素)。对于我的代码来说，这不是一个大问题。但这确实使事情变得方便。例如，当用户在要创建线/弧时选择一个节点时，代码将遍历整个节点列表以找出选择了哪个节点，然后对于第一个选择，将索引存储到变量中(称为firstNodeIndex)。对于第二个节点，它执行相同的操作，但是当两个变量(firstNodeIndex和secondNodeIndex)都是可行的数字时，将调用用于创建行/弧的函数，并且该函数使用两个存储的索引来重新访问节点列表以抓取到该节点的地址。如果要使用该列表，则必须将两个节点的地址存储在变量中，然后创建一些附加逻辑以确保包含两个节点地址的两个变量是可行的选项。

另一个替代解决方案是再次遍历整个节点列表，以获取所选的节点(我将在每个节点内部都有一个变量，以表明它已被选中)。但是恐怕鉴于std::list的限制，这可能不是一个好主意。

我有点支持我的第一种方法，但是如果需要或有更好的方法，我愿意改变

Answer 1

因此，您的问题是，当您插入或擦除元素时，您不希望迭代器无效，但是您希望数据结构快速。

仅当您必须频繁迭代所有元素时，链表才很慢。 In不利用 vector 或双端队列之类的连续数据访问的优势。列表中的线性搜索也很慢。

我有类似的情况。以下是一些选项:

使用列表，并尝试避免线性搜索。查看链接列表的内存访问速度是否会显着影响您的性能，如果没有，请使用它。

使用 map 或集合。除搜索为O(logn)外，其他与列表相同。或者，如果您不关心元素的排序，则可以使用无序版本。

使用像 plf::colony 这样的非标准数据结构。如果您不关心插入顺序，这可能是您的最佳选择。

创建您自己的类似双端队列的数据结构，该结构不会使迭代器无效(使用skipfields或将自由元素存储在某处)。我不建议您这样做，因为您可能最终还是会写类似plf::colony的内容。