1

以下で言及する例を使用して、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
4

1 に答える 1

2

まさにこれにstd::lower_boundandを使用します。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]
于 2012-10-05T21:03:39.390 に答える