2

我注意到 unordered_map::equal_range upper_bound (first) 如果传递的键小于 map 的第一个键，则返回 end

#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

请注意，map 和 unordered_map 的行为是不同的——有什么原因，或者这是 unordered_map 的问题吗？

4

2 回答 2

2

发生这种情况是因为 anunordered_map是无序的，这并不奇怪。

参见§22.2.7 [unord.req]，表 70，关于以下方面的要求equal_range：

返回： 包含所有元素的范围，其键等效于k。make_­pair(b.end(), b.end())如果不存在此类元素，则返回。

这不同于对有序关联容器的要求，例如std::map，其中用和equal_range定义。 lower_boundupper_bound

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

于 2019-04-25T11:15:05.530 回答
2

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

情况也是map如此。但是，表示此条件的方式因容器而异（尽管并非如此；继续阅读）。容器std::map和std::unordered_map不是同一个东西（因此它们有不同的名称）。前者是有序的，而后者不是，因此出于逻辑实现原因，它的工作方式略有不同：

unordered_map

返回值
std::pair包含一对定义所需范围的迭代器。如果没有这样的元素，则过去的（请参阅end()）迭代器作为该对的两个元素返回。

map

返回值
std::pair包含一对定义所需范围的迭代器：第一个指向不小于的第一个元素，key第二个指向大于的第一个元素key。如果没有不小于 key 的元素，则将过去的（请参阅end()）迭代器作为第一个元素返回。同样，如果没有大于 的元素key，则返回结束迭代器作为第二个元素。）

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

在您的代码中，您没有检查案例中返回的对的两个部分。map如果你这样做了，那么你会发现first == second（同样，表示一个空范围）。

您的map代码有效地取消引用返回范围的“过去的”迭代器。

#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

（现场演示）

于 2019-04-25T11:15:27.940 回答