16

给定一个迭代器,是否可以为该迭代器引用的集合检索/使用正确的比较函数?

例如,假设我正在编写一个通用算法:

template <class InIt, class T>
void do_something(InIt b, InIt e, T v) { 
    // ...
}

现在,假设我想做一些简单的事情,比如 find vin [b..e)。如果be是 a 的迭代器std::vector,我可以简单地使用if (*b == v) .... 然而,让我们假设bande是 a 上的迭代器std::map。在这种情况下,我应该只比较keys,而不是 map 中包含的整个 value 类型。

所以问题是,给定映射中的那些迭代器,我如何检索只会比较键的映射比较函数?同时,我不想盲目地假设我正在使用map其中之一。例如,如果迭代器指向 a set,我想使用为它定义的比较函数set。如果他们指向vectoror deque,我可能不得不使用==,因为这些容器不会定义比较函数。

哦,差点忘了:我意识到在许多情况下,一个容器只会有一个等价物operator<而不是operator==它包含的元素——我完全可以使用它。

4

3 回答 3

11

迭代器不必连接到容器,因此它们不会向您提供有关它们不一定连接到的容器的任何详细信息。这是基本的迭代器抽象:迭代器分隔序列,而不考虑序列来自何处。如果您需要了解容器,则必须编写采用容器的算法。

于 2012-11-13T16:28:06.610 回答
6

没有标准方法可以从迭代器映射到底层容器类型(如果有这样的容器的话)。您也许可以使用一些启发式方法来尝试确定哪个容器,尽管这并不简单,也可能无法保证。

例如,您可以使用元函数来确定 *value_type* 是否为std::pair<const K, T>,这暗示这可能是 astd::map和提取类型后,KT尝试使用元函数来确定迭代器的类型和std::map<K,T,X,Y>::iterator或的类型匹配,std::map<K,T,X,Y>::const_iterator的特定组合。XY

In the case of the map that could be sufficient to determine (i.e. guess with a high chance of success) that the iterator refers to a std::map, but you should note that even if you can use that and even extract the type X of the comparator, that is not sufficient to replicate the comparator in the general case. While uncommon (and not recommended) comparators can have state, and you would not know which is the particular state of the comparator without having access to the container directly. Also note that there are cases where this type of heuristic will not even help, in some implementations of std::vector<> the iterator type is directly a pointer, and in that case you cannot differentiate between an 'iterator' into an array and an iterator into a std::vector<> of the same underlying types.

于 2012-11-13T16:39:04.527 回答
3

Unfortunately iterators don't always know about the container that contains them (and sometimes they aren't in a standard container at all). Even the iterator_traits only have information about the value_type which doesn't specifically tell you how to compare.

Instead, let's draw inspiration from the standard library. All the associative containers (map, etc) have their own find methods rather than using std::find. And if you do need to use std::find on a such a container, you don't: you use find_if.

It sounds like your solution is that for associative containers you need a do_something_if that accepts a predicate telling it how to compare the entries.

于 2012-11-13T16:53:54.883 回答