0

基本上，我想要一个 std::list 但具有 std::map 属性，例如 find()，我真的需要遍历每个列表条目以找到我需要的内容吗？

4

9 回答 9

15

如果你想要 std::map 的属性，为什么不使用 std::map 呢？这将比遍历每个元素更有效。

于 2009-01-08T02:09:03.110 回答
11

Checkout Boost.MultiIndex，它比使用带有指针的多个容器更容易和更有效。

于 2009-01-08T02:42:50.827 回答
9

如果你想要一个容器：

1）插入顺序不重要（这是一个列表）
2）搜索速度是。

然后使用一个

标准::设置<>
于 2009-01-08T02:40:01.020 回答
3

使用std::find或std::find_if在某个迭代器范围内查找某个值的第一个位置。

于 2009-01-08T02:09:23.983 回答
3

如果您担心搜索时间但想保留订单，您可以保留两个具有相同数据的容器。

于 2009-01-08T02:13:25.240 回答
2

std::list 的目的是不查找/搜索。这就是 std::map 的用途。列表非常适合插入、提取、移动和使用排序算法。如果您只需要存储数据并随机找到它，请使用地图。如果您想构建数据的存储方式和存储位置，请使用列表。

于 2009-01-08T02:41:37.460 回答
1

选项1

听起来您想要的是单个元素的映射，而不是成对的映射。使用std::set<T>，这是一个实现为 的适配器std::map<T,void>。这意味着您的所有元素都是独一无二的；也就是说，您的容器中不会有重复项。这也意味着您的元素不会被严格排序；也就是说，您不能在任何给定时间依赖任何元素的位置。然后您可以使用 的find()成员函数std::set<T>，它将在对数时间内执行快速搜索元素。

选项 2

如果您想要的是一个可以快速访问最小或最大元素的容器，那么您可以使用您选择std::priority_queue<T,C>的容器C。如果未指定，则使用的默认容器是std::vector<T>. std::priority_queue<T>使用make_heap(),push_heap()和pop_heap()算法，因此需要底层容器支持随机访问迭代器； std::list<T>在这种情况下是不够的。top()使用成员函数在恒定时间内访问“第一个”（最大或最小）元素。push()使用和成员函数推送和弹出第一个元素pop()，它们以对数时间运行（实际上是 2*log(n)，因为它们需要搜索和冒泡）。

选项 3

如果您想要的只是一个包含对的列表，只需将其声明为：

std::list<std::pair<T> > the_list;

这只会给出一个链表，它具有任何其他链表的限制和好处，但会像地图一样保存对。因此，您将使用标准算法来操作列表。您可能需要使用此列表将专门的函数或仿函数传递给算法，以取消引用该对中的键或值。

如果您只想在列表中搜索一个项目，而不考虑效率，您可以使用std::find()算法在 O(n) 时间内完成此操作。这正是这个算法的目的，为任何容器提供线性时间搜索功能，而不是做得比这更好。这是我们对未排序的数组或向量、列表等使用的方法。这应该是你最后的选择，因为它可能比其他方法慢得多，尽管它本身会变慢。如果您不经常搜索，如果您知道元素在第一个迭代器附近，如果容器很小，没有更快的替代方案等，请使用此方法。

于 2009-01-08T03:52:43.450 回答
0

我需要完全相同的东西，所以我写了一些列表和地图的组合。我称它为 map_list<> 和 hash_map_list<>。基本上，我把源代码放到了 xmap.h 和 xlist.h 中，并将两者结合起来制作了 xmap_list.h。此类的工作方式是将键存储在给定的映射中，但与指向包含该值的节点的指针配对。该节点包含一个指向地图的迭代器。节点保存在单独的链表中。以这种方式，您可以像通常使用地图类一样使用 find 函数，但您也可以按照插入元素的顺序迭代元素，就像列表类一样。您甚至可以像在列表中一样迭代键本身。我没有实现每一个最后的等效列表函数，但你最常使用的大多数函数都在那里（例如，我不处理自定义分配器，尽管您可以自己轻松添加）。它有点像带有 find() 函数的 list<> 。

对于我写这篇文章的项目，我最终转向了 boost::multi_index，但我仍然尽可能使用上面的 map_list<> 类，因为它更轻量级并且更接近 std::list<>界面。

我没有将代码上传到任何地方，但是如果我看到有人对此答案添加了评论，我会尝试将其发布到某个地方，并在此处记下位置。

于 2009-08-27T11:26:24.387 回答
0

@obecalp 有一个很好的答案。boost MultiIndex 是一个很好的建议。@Bklyn：这不是一个“非常愚蠢”的问题。

于 2009-08-24T19:46:19.793 回答