std::list和std::map属性?

如果您想要std::map的属性,为什么不使用std::map?它将比遍历每个元素更有效率。

结帐 Boost.MultiIndex ,它比使用带有指针的多个容器更简单、更高效。

如果您想要一个容器,其中:

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

然后使用

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

如果您担心搜索时间,但希望保持顺序,则可以保留两个包含相同数据的容器。

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

选择1

听起来你想要的是单个元素的映射,而不是成对元素的映射。使用 std::set<T> ,这是一个适配器,实现为 std::map<T,void> . 这意味着所有元素都将是唯一的;也就是说,容器中不会有重复的元素。它还意味着您的元素将不会严格排序;也就是说,您不能在任何给定时间依赖任何元素的位置。然后你可以使用 find() 成员函数 标准::设置<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)时间内的算法。这正是该算法的目的,为任何容器提供线性时间搜索功能都比不上这一点。这就是我们对未排序数组或向量、列表等使用的方法。这应该是您最后的选择,因为它可能比其他方法慢得多,尽管它本身会慢得多。如果您不经常搜索,如果您知道元素靠近第一个迭代器,如果容器很小,如果没有任何更快的替代方法等,请使用此方法。

@奥贝卡尔普有一个很好的答案。提高多指标指数是个好建议。 @是的 不 一个“非常愚蠢”的问题。

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

对于我写这篇文章的项目,我最终改为boost::multi_index,但我仍然尽可能使用上面的map_list<gt;类,因为它更轻,更接近std::list<gt;接口。

我没有把代码上传到任何地方,但是如果我看到有人在这个答案中添加了评论,我会试着把它发布到某个地方,并在这里注明位置。