我应该使用 std::list 还是有更好的方法？
Should I use std::list or is there a better method?
我目前正在用 C++ 编写二维几何编辑器。我有用户放置节点。可以通过选择 2 个节点来绘制直线和圆弧。
现在，我将节点存储在 std::deque 容器中（直线和圆弧也是如此）因为我想将节点的地址存储到每个 line/arc 中。当我实现移动节点的功能时，这使得编码变得非常方便。如果我要在每个 line/arc 中存储实际节点，那么当我想移动一个节点时，我将不得不遍历整个线和弧结构以找到我刚刚移动的节点并更新参数。此选项不是 table 上的选项。因此，需要能够在每个 line/arc.
里面存储节点的地址
但是，我 运行 遇到了一些需要删除节点的问题。查看参考手册，似乎对于所有指针，当您从双端队列中删除一个元素时，这些都是无效的（除非该元素在开头或结尾。为了讨论，我不会考虑这种情况） .这会导致擦除问题，因为现在，我所有的 lines/arc 都将自己重新连接到不同的节点，或者当一个节点被擦除并且程序最终崩溃时根本不会被绘制。
继续在线查看，我发现 std::list（根据我阅读文档的理解）在删除其中一个元素时不会使任何指针或引用无效。这似乎是解决我的问题的一个很好的方法。
但是，我一直在研究堆栈溢出，以了解使用列表与双端队列的 benefits/disadvantages 是什么。而且似乎更倾向于使用双端队列而不是列表。似乎列表访问速度比双端队列慢。这不好，因为我不确定用户想要绘制多少个节点。据我所知，几何中可能有 10,000 多个节点，如果用户想要移动节点，我不希望用户必须等待 30 秒才能让程序遍历所有元素以找到节点(s) 擦除。
因此，一方面，双端队列要快得多，但一旦删除一个元素，所有指针和引用都会失效。另一方面，std::list 允许我擦除我想要的任何元素而不会使任何指针和引用无效，但与双端队列相比速度较慢。
我正在考虑切换到列表，因为即使列表速度较慢，如果我不能在不使指针和引用无效的情况下删除元素，那么如果程序在速度方面没有太大好处无效。
但是，在我的情况下，使用列表是最佳选择吗？有没有办法使用双端队列？或者有没有我没有考虑过的第三种选择？
编辑：
忘记说了。我不喜欢列表的一件事是无法直接获取元素的数据（在 std::deque 和 vector 中，我可以使用 at 函数访问元素）。这对我的代码来说不是什么大问题。但它确实使事情变得方便。例如，当用户在想要创建 line/arc 时选择一个节点时，代码遍历整个节点列表以找出选择了哪个节点，然后对于第一个选择，将索引存储到变量中（称为 firstNodeIndex）。对于第二个节点，它做同样的事情，但是当两个变量（firstNodeIndex 和 secondNodeIndex）都是可行的数字时，然后调用创建 line/arc 的函数，该函数使用两个存储的索引重新访问节点列表以获取节点的地址。如果我要使用该列表，我将不得不将两个节点的地址存储在变量中，然后创建一些额外的逻辑以确保包含两个节点地址的两个变量是可行的选项。
另一个替代解决方案是再次遍历整个节点列表以获取选定的节点（我会在每个节点内有一个变量来指示它已被选中）。但考虑到 std::list 限制，我担心这可能不是一个好主意。
我有点赞成我的第一种方法，但如果需要或有更好的方法，我愿意改变
经验法则：
我要随机添加和删除项目吗？
set, list, map, multimap and unordered versions of same
我是否希望能够命名单个项目并快速找到它们？
map, set, multimap and unordered versions of same
我正在存储的东西是否有可变数据，或者它是否比它的名称（密钥）更详细？
map, multimap, unordered versions thereof
我需要按顺序说这些项目吗？
yes: map, no: unordered_map
所以你的问题是你不希望你的迭代器在你插入或删除元素时失效，但你希望你的数据结构是快速的。
仅当您必须频繁迭代所有元素时，链表才会变慢。 In 不利用像 vector 或 deque 这样的连续数据访问。列表中的线性搜索也很慢。
我也遇到过类似的情况。以下是一些选项：
使用列表并尽量避免线性搜索。查看链表的内存访问速度是否会显着影响您的性能，如果不会 - 使用它。
使用地图或集合。与列表相同的缺点除了搜索，这是 O(logn)。或者，如果您不关心元素的排序，您可以使用无序版本。
使用非标准数据结构，如 plf::colony。如果您不关心插入顺序，这可能是您的最佳选择。
创建你自己的类似双端队列的数据结构，它不会使迭代器无效（使用 skipfields 或在某处存储自由元素）。我不推荐它，因为你可能最终会写出类似 plf::colony 的东西。
我目前正在用 C++ 编写二维几何编辑器。我有用户放置节点。可以通过选择 2 个节点来绘制直线和圆弧。
现在，我将节点存储在 std::deque 容器中（直线和圆弧也是如此）因为我想将节点的地址存储到每个 line/arc 中。当我实现移动节点的功能时，这使得编码变得非常方便。如果我要在每个 line/arc 中存储实际节点，那么当我想移动一个节点时，我将不得不遍历整个线和弧结构以找到我刚刚移动的节点并更新参数。此选项不是 table 上的选项。因此，需要能够在每个 line/arc.
里面存储节点的地址但是，我 运行 遇到了一些需要删除节点的问题。查看参考手册，似乎对于所有指针，当您从双端队列中删除一个元素时，这些都是无效的（除非该元素在开头或结尾。为了讨论，我不会考虑这种情况） .这会导致擦除问题，因为现在，我所有的 lines/arc 都将自己重新连接到不同的节点，或者当一个节点被擦除并且程序最终崩溃时根本不会被绘制。
继续在线查看，我发现 std::list（根据我阅读文档的理解）在删除其中一个元素时不会使任何指针或引用无效。这似乎是解决我的问题的一个很好的方法。
但是，我一直在研究堆栈溢出，以了解使用列表与双端队列的 benefits/disadvantages 是什么。而且似乎更倾向于使用双端队列而不是列表。似乎列表访问速度比双端队列慢。这不好，因为我不确定用户想要绘制多少个节点。据我所知，几何中可能有 10,000 多个节点，如果用户想要移动节点，我不希望用户必须等待 30 秒才能让程序遍历所有元素以找到节点(s) 擦除。
因此，一方面，双端队列要快得多，但一旦删除一个元素，所有指针和引用都会失效。另一方面，std::list 允许我擦除我想要的任何元素而不会使任何指针和引用无效，但与双端队列相比速度较慢。
我正在考虑切换到列表，因为即使列表速度较慢，如果我不能在不使指针和引用无效的情况下删除元素，那么如果程序在速度方面没有太大好处无效。
但是，在我的情况下，使用列表是最佳选择吗？有没有办法使用双端队列？或者有没有我没有考虑过的第三种选择？
编辑：
忘记说了。我不喜欢列表的一件事是无法直接获取元素的数据（在 std::deque 和 vector 中，我可以使用 at 函数访问元素）。这对我的代码来说不是什么大问题。但它确实使事情变得方便。例如，当用户在想要创建 line/arc 时选择一个节点时，代码遍历整个节点列表以找出选择了哪个节点，然后对于第一个选择，将索引存储到变量中（称为 firstNodeIndex）。对于第二个节点，它做同样的事情，但是当两个变量（firstNodeIndex 和 secondNodeIndex）都是可行的数字时，然后调用创建 line/arc 的函数，该函数使用两个存储的索引重新访问节点列表以获取节点的地址。如果我要使用该列表，我将不得不将两个节点的地址存储在变量中，然后创建一些额外的逻辑以确保包含两个节点地址的两个变量是可行的选项。
另一个替代解决方案是再次遍历整个节点列表以获取选定的节点（我会在每个节点内有一个变量来指示它已被选中）。但考虑到 std::list 限制，我担心这可能不是一个好主意。
我有点赞成我的第一种方法，但如果需要或有更好的方法，我愿意改变
经验法则：
我要随机添加和删除项目吗？
set, list, map, multimap and unordered versions of same
我是否希望能够命名单个项目并快速找到它们？
map, set, multimap and unordered versions of same
我正在存储的东西是否有可变数据，或者它是否比它的名称（密钥）更详细？
map, multimap, unordered versions thereof
我需要按顺序说这些项目吗？
yes: map, no: unordered_map
所以你的问题是你不希望你的迭代器在你插入或删除元素时失效，但你希望你的数据结构是快速的。
仅当您必须频繁迭代所有元素时，链表才会变慢。 In 不利用像 vector 或 deque 这样的连续数据访问。列表中的线性搜索也很慢。
我也遇到过类似的情况。以下是一些选项：
使用列表并尽量避免线性搜索。查看链表的内存访问速度是否会显着影响您的性能，如果不会 - 使用它。
使用地图或集合。与列表相同的缺点除了搜索，这是 O(logn)。或者，如果您不关心元素的排序，您可以使用无序版本。
使用非标准数据结构，如
plf::colony。如果您不关心插入顺序，这可能是您的最佳选择。创建你自己的类似双端队列的数据结构，它不会使迭代器无效（使用 skipfields 或在某处存储自由元素）。我不推荐它，因为你可能最终会写出类似
plf::colony的东西。