Составные ключи std::map с++

Question

У меня есть картеж/структура из 3 чисел, по нему производится лексеграфическое сравнение, могу ли я в std::map получить диапазон всех картежей, которые начинаются c определенного числа, к примеру (1,2,3),(1, 3, 2)... Я понимаю что std::map не поддерживает составные ключи, но может быть есть хитрый способ перегрузить компаратор, но в голову не приходит как это сделать.

Answer 1

struct tuple_less
{
    using is_transparent = int;

    template< typename...T1, typename ... T2 >
    bool operator() ( const std::tuple<T1...>& lhs,
                      const std::tuple<T2...>& rhs ) const
    {
        // выделяем общее начало кортежей
        constexpr size_t min_size = std::min( sizeof...(T1), sizeof...(T2) );
        auto l_tie = sub_tie( lhs, std::make_index_sequence< min_size >{} );
        auto r_tie = sub_tie( rhs, std::make_index_sequence< min_size >{} );

        // if(l_tie<r_tie) return true;
        // if(r_tie<l_tie) return false;
        // Более короткая строка меньше более более длинной, (если начало одинаконо).
        // Но, равные по длинне строки - равны
        // return sizeof...(T1) < sizeof...(T2);

        // Оптимизированно:
        if(sizeof...(T1) < sizeof...(T2))
            return !(r_tie<l_tie);
        else
            return l_tie<r_tie;
    }

private:
    template< typename T, size_t ... i  >
    static auto sub_tie( const T& tuple, std::index_sequence<i...> ) {
        return std::tie( (std::get<i>(tuple))... );
    }
};

// тест
int main()
{
    std::tuple<int,int,int> a1 = {1,2,3};
    std::tuple<int,int> a2 = {1,2};
    assert( tuple_less{}(a1,a2) == false );
    assert( tuple_less{}(a1,a1) == false );
    assert( tuple_less{}(a2,a1) == true  );


    using key_type=std::tuple<int, unsigned, std::string>;

    std::map< key_type, std::string, tuple_less > map={
        { { 1, 2, "12"}, "x"},
        { { 1, 5, "15"}, "yy"},
        { { 2, 0, "20"}, "zzz"},
    };

    auto begin = map.lower_bound( std::tuple<int>{1} );
    auto end = map.lower_bound( std::tuple<int>(1+1) );
    for( auto i=begin; i!=end; ++i)
    {
        std::cout<<i->second<<std::endl;
    }
}

Answer 2

В качестве типа ключа можно использовать std::array<int, 3> или std::tuple<int, int, int>. Или, если у полей есть осмысленные названия (а не просто индексы), то свою структуру с перегруженным оператором <.

Дальше, красивее, конечно, сделать свой компаратор, как в ответе @Chorkov.

Но, чтобы не заморачиваться, можно просто вызвать .lower_bound({n,0,0}) чтобы найти начало диапазона, и .upper_bound({n+1,0,0}) чтобы найти конец диапазона.

БЛОГ НА HUSL

Составные ключи std::map с++

Ответы (2 шт):