哪个是最快的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 :: list ， std :: set 或 std :: map over std :: 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.

我也可以使用C +

推荐答案

要搜索特定值，使用 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 use find instead.

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