C++ - 在 std::map 中查找相邻元素

Question

使用我在下面提到的示例在 STL 映射中查找相邻元素的最有效方法是什么:

假设我有一个整数-字符串的映射:

1 -> Test1
5 -> Test2
10 -> Test3
20 -> Test4
50 -> Test5

如果我调用:

get_adjacent(1) // Returns iterator to 1 and 5
get_adjacent(2) // Returns iterator to 1 and 5
get_adjacent(24) // Returns iterator to  20 and 50
get_adjacent(50) // Returns iterator to 20 and 50

Answer 1

为此使用 std::lower_bound 和 std::upper_bound。

更好的是 std::map::equal_range 结合了两者的力量:

观看直播 http://liveworkspace.org/code/d3a5eb4ec726ae3b5236b497d81dcf27

#include <map>
#include <iostream>

const auto data = std::map<int, std::string> {
    { 1  , "Test1" }, 
        { 5  , "Test2" }, 
        { 10 , "Test3" }, 
        { 20 , "Test4" }, 
        { 50 , "Test5" }, 
};

template <typename Map, typename It>
void debug_print(Map const& map, It it)
{
    if (it != map.end())
        std::cout << it->first;
    else
        std::cout << "[end]";
}

void test(int key)
{
    auto bounds = data.equal_range(key);

    std::cout << key << ": " ; debug_print(data, bounds.first)  ; 
    std::cout << ", "        ; debug_print(data, bounds.second) ; 
    std::cout << '\n'        ; 
}

int main(int argc, const char *argv[])
{
    test(1);
    test(2);
    test(24);
    test(50);
}

输出:

1: 1, 5
2: 5, 5
24: 50, 50
50: 50, [end]