哪个是查找速度最快的 STL 容器? [英] Which is the fastest STL container for find?

问题描述

好的，作为序言，我需要缓存很少修改的数据的相对较小的子集，以避免出于性能原因频繁查询数据库.此数据在只读意义上被大量使用，因为它经常被其他表中的大量数据引用.

Alright as a preface I have a need to cache a relatively small subset of rarely modified data to avoid querying the database as frequently for performance reasons. This data is heavily used in a read-only sense as it is referenced often by a much larger set of data in other tables.

我编写了一个类，该类能够在侦听提交更改以及更新缓存对象的线程安全回调机制的同时，将有问题的两个表的全部内容基本上存储在内存中.

I've written a class which will have the ability to store basically the entirety of the two tables in question in memory while listening for commit changes in conjunction with a thread safe callback mechanism for updating the cached objects.

我当前的实现有两个 std::vectors 一个用于每个表的元素.该类提供对每个向量的整体访问以及通过 std::find、std::find_if 搜索表数据的特定元素的便捷方法，等

My current implementation has two std::vectors one for the elements of each table. The class provides both access to the entirety of each vector as well as convenience methods for searching for a specific element of table data via std::find, std::find_if, etc.

有谁知道是否在 std 上使用 std::list、std::set 或 std::map::vector 用于搜索会更可取吗?大多数情况下，这是在建立新连接时从数据库填充一次后对这些容器的请求.

Does anyone know if using std::list, std::set, or std::map over std::vector for searching would be preferable? Most of the time that is what will be requested of these containers after populating once from the database when a new connection is made.

我也愿意使用 VS2010 或 Boost 支持的 C++0x 功能.

I'm also open to using C++0x features supported by VS2010 or Boost.

推荐答案

对于搜索特定值，使用 std::set 和 std::map 需要 O(log N) 时间，而其他两个则需要 O(N) 时间；所以，std::set 或 std::map 可能更好.由于您可以访问 C++0x，您还可以使用 std::unordered_set 或 std::unordered_map 平均花费恒定时间.

For searching a particular value, with std::set and std::map it takes O(log N) time, while with the other two it takes O(N) time; So, std::set or std::map are probably better. Since you have access to C++0x, you could also use std::unordered_set or std::unordered_map which take constant time on average.

对于find_if，它们之间几乎没有区别，因为它需要任意谓词，当然容器不能任意优化.

For find_if, there's little difference between them, because it takes an arbitrary predicate and containers cannot optimize arbitrarily, of course.

但是，如果您将使用某个谓词频繁调用 find_if，您可以优化自己:使用 std::map 或 std::set 使用自定义比较器或特殊键并使用 find 代替.

However if you will be calling find_if frequently with a certain predicate, you can optimize yourself: use a std::map or std::set with a custom comparator or special keys and use find instead.

这篇关于哪个是查找速度最快的 STL 容器?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！