问题标签 [containers]

的 3 参数形式list::splice()将单个元素从一个列表移动到另一个列表。 SGI 的文档明确指出所有迭代器，包括指向被移动元素的迭代器仍然有效。 Roguewave 的文档没有说明splice()方法的迭代器失效属性，而 C++ 标准明确声明它使所有迭代器和对被拼接元素的引用失效。

splicing() 在实践中按照 SGI 的定义工作，但在微软 STL 实现的调试/安全 SCL 版本（严格遵循标准的字母）中出现断言失败（取消引用无效迭代器）。

现在，我使用 list 正是因为我想在列表之间移动一个元素，同时保留指向它的迭代器的有效性。该标准对原始 SGI 的规范进行了极其无益的更改。

我该如何解决这个问题？或者我应该务实一点，把头埋在沙子里（因为在实践中拼接不会使迭代器失效——即使在 MS 的实现中，一旦迭代器调试被关闭）。

我知道大多数人认为这是一种不好的做法，但是当您试图使您的类公共接口仅与引用一起使用时，将指针保留在内部并且仅在必要时，我认为没有办法返回告诉您正在寻找的值的东西容器中不存在。

假设您不想在类的公共接口中看到危险的指针，在这种情况下如何返回未找到，抛出异常？

你对此有何看法？您是否返回一个空值并检查它的空状态？我实际上使用了 throw 方法，但我介绍了一种检查方法：

因此，当我忘记首先检查该值是否存在时，我会得到一个异常，这确实是一个异常。

你会怎么做？

这真的很容易用一个例子来解释，所以要从 dict 中删除列表的交集，我通常会这样做：

这似乎是一个不寻常的例子，但令人惊讶的是我不得不做这样的事情的次数。使用集合执行此操作会更好，但我显然想保留字典的“值”。

这种方法很烦人，因为它需要两个循环和一个额外的数组。有没有一种更清洁、更有效的方法来做到这一点。

毫无疑问，我会选择将 STL 用于大多数 C++ 编程项目。然而，最近有人向我提出了这个问题，“有没有什么情况下你不会使用 STL？”...

我想得越多，我就越意识到也许应该在某些情况下我选择不使用 STL ......例如，一个非常大的长期项目，其代码库预计将持续数年......也许精确满足项目需求的定制容器解决方案值得最初的开销吗？你怎么看，有没有什么情况下你会选择不使用 STL？

假设我有一组值，存储在 std::set 中：

{1、2、6、8}

我有一个搜索键，比如 3。我想将 3 放入一个函数并获得大于或等于 3 的第一个值，在这种情况下，我想获得 6。

map/set/multimap/and set 中提供的 find() 函数当然会返回这种情况的结束迭代器。在这种情况下，是否有类似的函数可以返回 6？

显然 ;-) 标准容器提供了某种形式的保证。

什么类型的保证以及不同类型的容器之间究竟有什么区别？

从SGI 页面工作（关于STL）我想出了这个：

我正在寻找一个能够将所有物品保持有序的容器。我查看了 SortedList，但这需要一个单独的键，并且不允许重复键。我也可以只使用一个未排序的容器，并在每次插入后对其进行显式排序。

用法：

• 偶尔插入
• 按顺序频繁遍历
• 理想情况下，不要使用与实际对象分开的键，使用比较函数进行排序。
• 需要对等效对象进行稳定排序，但不是必需的。
• 不需要随机访问。

我意识到我可以为自己构建一个平衡的树结构，我只是想知道框架是否已经包含这样一个野兽。

问题

我有时间戳数据，我需要根据时间戳进行搜索，以便获得与我的输入时间戳最接近的一个现有时间戳。
最好用 STL 解决这个问题。boost::* 或 stl::tr1::* （来自带有 Featurepack 的 VS9）也是可能的。
时间戳数据示例：

使用stl::vector,sort()和equal_range()

由于 a maporset只允许我找到完全匹配，因此我不再使用其中一个。所以现在我有一个vector我在数据进入时追加数据的地方。在搜索之前，我使用<algorithm>'ssort()并为其提供自定义比较功能。
之后，我使用<algorithm>'sequal_range()查找指定值的两个邻居x。从这两个值中，我检查哪一个最接近x，然后我有我的最佳匹配。

虽然这不是太复杂，但我想知道是否有更优雅的解决方案。
也许 STL 已经有一个算法可以做到这一点，所以我不会在这里重新发明一些东西？

更新：线性与二进制搜索

我忘了提到我有很多数据要处理，所以我不想线性搜索。
我对向量进行排序的原因sort()是它具有随机访问迭代器，而map. 使用 amap不允许equal_range()进行具有两倍对数复杂度的搜索。
我对么？

有人知道任何 C 容器库吗？我正在寻找能够提供链表、数组、哈希表等标准实现的东西，与 C++ STL 所做的方式非常相似。主要问题是：

1. 客户端代码应该能够为多种不同的数据类型创建容器，而无需修改库。
2. 创建和使用容器的界面应该是直观的。

我需要一个只有两个操作的快速容器。从一个非常稀疏的域（所有 32 位整数，并且在给定时间设置大约 100 个）插入键，并迭代插入的键。它应该处理许多命中相同条目的插入（例如，500k，但只有 100 个不同的条目）。

目前，我正在使用 std::set （仅插入和迭代接口），这很不错，但仍然不够快。std::unordered_set 慢了一倍，与 Google Hash Maps 相同。我想知道针对这种情况优化了哪些数据结构？