c++ - 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_boundandstd::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]