c++ - 列表容器的 equal_range

Question

我正在制作一个自定义容器，它使用 STL 列表容器作为其内部结构。我要添加到此容器中的项目之一是 equal_range。

我的 equal_range 的代码在这里:

template <typename T> typename square_list<T>::iterator_pair square_list<T>::equal_range(key_type const& key) {
    auto range = std::equal_range(data_.begin(), data_.end(), key);
    for (square_list<T>::iterator it = range.first; it != range.second;) {
         if (range.first == data_.end() && range.second == data_.end())
            return std::make_pair(data_.end(), data_.end());
    ++it;
}

    return range;
}

我有一些针对此实现运行的单元测试，一切正常，除非键值不在数据结构中。它导致了问题，并且 .first 和 .second 没有返回等于 data_ 的末尾。

为了使 range.first 和 range.second 等于 std::list<T> data_ 的末尾，我需要更改什么？如果键值不在列表中？

这也是单元测试的代码:

BOOST_AUTO_TEST_CASE(ut_equal_range) {
    vector<int> v{ 1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 8, 8 };
    square_list<char> sql(v.begin(), v.end());

    auto res = sql.equal_range(0);
    BOOST_CHECK(res.first == sql.cend());
    BOOST_CHECK(res.second == sql.cend());
}

Answer 1

std::equal_range 将返回一个大小为 0 的范围，其中 key 如果它不在 data_ 中则将是。因此，如果您想在这种情况下将一对迭代器返回给 data_.end()，您应该检查是否 range.first == range.second，并且相应地返回一对结束迭代器。

值得注意的是 std::equal_range 的输入限制:http://en.cppreference.com/w/cpp/algorithm/equal_range

简而言之，equal_range 的输入必须根据键进行分区，这意味着必须存在两个子范围，其中一个由小于要搜索的键的值组成，并且一个由更大的值(value)组成的。已排序的范围已具有此保证。