为什么 unordered_map::equal_range upper_bound returns 如果键小于第一个映射元素则结束

Question

我注意到 unordered_map::equal_range upper_bound (first) returns 如果传递的键小于 map 的第一个

#include <iostream>
#include <map>
#include <tr1/unordered_map>

using namespace std;

int main ()
{
    {
        std::map<char,int> mymap;
        mymap['c'] = 60;
        std::map<char,int>::iterator itup = mymap.equal_range('a').first;
        std::cout << "map::itup " << itup->first << std::endl;
    }

    {
        tr1::unordered_map<char, int> mymap;
        mymap['c'] = 60;
        mymap['d'] = 70;

        tr1::unordered_map<char, int>::iterator itlo = mymap.equal_range('a').first;
        tr1::unordered_map<char, int>::iterator itup = mymap.equal_range('a').second;

        cout << "unordered_map::itup " << (itup == mymap.end() ? "END" : "NOT END") << std::endl;
        cout << "unordered_map::itlo " << (itlo == mymap.end() ? "END" : "NOT END") << std::endl;
    }

    return 0;
}

输出为：

map::itup c
unordered_map::itup END
unordered_map::itlo END

请注意，地图和 unordered_map 的行为不同 - 任何原因或者这是 unordered_map 中的问题？

Answer 1

发生这种情况是因为 unordered_map 是无序的，这不足为奇。

参见 §22.2.7 [unord.req]、Table 70，关于 equal_range 的要求：

Returns: A range containing all elements with keys equivalent to k. Returns make_­pair(b.end(), b.end()) if no such elements exist.

这与有序关联容器的要求不同，例如 std::map，其中 equal_range 是根据 lower_bound 和 upper_bound 定义的。

std::unordered_map 没有 lower_bound 和 upper_bound，原因很明显。

Answer 2

您要求的范围包含 unordered_map 中的所有元素，其键为 'a'。您的无序地图不包含此类元素。所以，范围是空的。

map的情况也是如此。然而，这种情况的表示方式因容器而异（尽管不是真的；继续阅读）。容器 std::map 和 std::unordered_map 不是一回事（因此它们有不同的名称）。前者是有序的，而后者不是，所以出于逻辑实现的原因，它的工作方式略有不同：

unordered_map

Return value
std::pair containing a pair of iterators defining the wanted range. If there are no such elements, past-the-end (see end()) iterators are returned as both elements of the pair.

map

Return value
std::pair containing a pair of iterators defining the wanted range: the first pointing to the first element that is not less than key and the second pointing to the first element greater than key. If there are no elements not less than key, past-the-end (see end()) iterator is returned as the first element. Similarly if there are no elements greater than key, past-the-end iterator is returned as the second element.)

这种差异无关紧要。 无论哪种情况，您都应该简单地迭代 (first, second] 来检查您范围内的元素（如果存在），就像您对任何迭代器范围所做的那样。

在您的代码中，您没有检查 map 案例中返回的对的 和 部分。如果你这样做，那么 you'll find that first == second（再次表示一个空范围）。

您的 map 代码有效地取消引用了返回范围的 "past-the-end" 迭代器。

---

#include <iostream>
#include <map>
#include <unordered_map>

using namespace std;

int main ()
{
    {
        std::map<char,int> mymap;
        mymap['c'] = 60;
        std::map<char, int>::iterator itlo = mymap.equal_range('a').first;
        std::map<char, int>::iterator itup = mymap.equal_range('a').second;

        // This compares each range extent to the map's end, which is not really useful
        cout << "map::itup " << (itup == mymap.end() ? "END" : "NOT END") << '\n';
        cout << "map::itlo " << (itlo == mymap.end() ? "END" : "NOT END") << '\n';

        // This examines the range itself
        cout << "map range empty: " << (itlo == itup ? "YES" : "NO") << '\n';
        cout << "map range size: " << std::distance(itlo, itup) << '\n';
    }

    {
        std::unordered_map<char, int> mymap;
        mymap['c'] = 60;
        mymap['d'] = 70;

        std::unordered_map<char, int>::iterator itlo = mymap.equal_range('a').first;
        std::unordered_map<char, int>::iterator itup = mymap.equal_range('a').second;

        // This compares each range extent to the map's end, which is not really useful
        cout << "unordered_map::itup " << (itup == mymap.end() ? "END" : "NOT END") << std::endl;
        cout << "unordered_map::itlo " << (itlo == mymap.end() ? "END" : "NOT END") << std::endl;

        // This examines the range itself
        cout << "unordered_map range empty: " << (itlo == itup ? "YES" : "NO") << '\n';
        cout << "unordered_map range size: " << std::distance(itlo, itup) << '\n';
    }
}

// Output:
// 
// map::itup NOT END
// map::itlo NOT END
// map range empty: YES
// map range size: 0
// unordered_map::itup END
// unordered_map::itlo END
// unordered_map range empty: YES
// unordered_map range size: 0

(live demo)