为什么使用std :: less作为默认函数来比较std :: map和std :: set中的键？ [英] Why use std::less as the default functor to compare keys in std::map and std::set?
问题描述
我想知道为什么 std :: map 和 std :: set 使用 std :: less 作为比较键的默认函子。为什么不使用类似于strcmp的函子？类似：
I am wondering why std::map and std::set use std::less as the default functor to compare keys. Why not use a functor that works similar to strcmp? Something like:
template <typename T> struct compare
{
// Return less than 0 if lhs < rhs
// Return 0 if lhs == rhs
// Return greater than 0 if lhs > rhs
int operator()(T const& lhs, T const& rhs)
{
return (lhs-rhs);
}
}
说出 code>有两个对象，其中键 key1 和 key2 。现在我们要插入键 key3 的另一个对象。
Say a map has two object in it, with keys key1 and key2. Now we want to insert another object with key key3.
当使用 std :: ，插入函数需要先调用 std :: less :: operator（）与 key1 和 key3 。假设 std :: less :: operator（）（key1，key3）返回false。它必须再次调用 std :: less :: operator（）键， std :: less :: operator（）（key3， key1），以决定 key1 是否等于 key3 或 key3 大于 key1 。有两个调用 std :: less :: operator（）来决定第一个调用是否返回false。
When using std::less, the insert function needs to first call std::less::operator() with key1 and key3. Assume std::less::operator()(key1, key3) returns false. It has to call std::less::operator() again with the keys switched, std::less::operator()(key3, key1), to decide whether key1 is equal to key3 or key3 is greater than key1. There are two calls to std::less::operator() to make a decision if the first call returns false.
std :: map :: insert 使用比较，会有足够的信息做出正确的决定只使用一个电话。
Had std::map::insert used compare, there would be sufficient information to make the right decision using just one call.
根据地图中键的类型， std :: less :: operator（）（key1，key2）
Depending on the type of the key in map, std::less::operator()(key1, key2) could be expensive.
除非我缺少一些非常基本的东西，不应该 std :: map std :: set 使用比较而不是 std :: less
Unless I am missing something very basic, shouldn't std::map and std::set use something like compare instead of std::less as the default functor to compare keys?
推荐答案
基于树的容器只需要严格弱命令。
Tree based containers only require Strict Weak Total Ordering.
请参阅 https://www.sgi.com/tech/stl/ StrictWeakOrdering.html
-
写入权限
write access
地图和集合的插入点纯粹由单个二进制搜索来确定，例如 lower_bound 或 upper_bound 。二进制搜索的运行时复杂度为 O（log n）
The insertion point for maps and sets is purely determined by a single binary search, e.g. lower_bound or upper_bound. The runtime complexity of binary search is O(log n)
读访问
这同样适用于搜索：搜索比线性等式扫描有效得多，因为大多数元素 不 需要比较。诀窍是容器是有序的。
The same applies to searching: the search is vastly more efficient than a linear equality scan, precisely because most elements do not need to be compared. The trick is that the containers are ordered.
equality 信息不需要存在。
在实践中，这只是意味着减少对元素类型的约束，减少实现需求的工作量并在常见使用情况下的最佳性能。总是有取舍。 （例如对于大集合，散列表（无序集合和映射）通常更有效。注意这些 do 需要 equatable 元素，他们使用哈希方案快速查找）
In practice this just just means fewer constraints on your element types, less work to implement the requirements and optimal performance in common usage scenarios. There will always be trade-offs. (E.g. for large collections, hash-tables (unordered sets and maps) are often more efficient. Note that these do require equatable elements, and they employ a hashing scheme for fast lookup)
这篇关于为什么使用std :: less作为默认函数来比较std :: map和std :: set中的键？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
