Оптимальный способ доступа к элементу std::tuple во время выполнения по индексу

У меня есть функция at, предназначенная для доступа к элементу std::tuple по индексу, указанному во время выполнения

template<std::size_t _Index = 0, typename _Tuple, typename _Function>
inline typename std::enable_if<_Index == std::tuple_size<_Tuple>::value, void>::type
for_each(_Tuple &, _Function)
{}

template<std::size_t _Index = 0, typename _Tuple, typename _Function>
inline typename std::enable_if < _Index < std::tuple_size<_Tuple>::value, void>::type
    for_each(_Tuple &t, _Function f)
{
    f(std::get<_Index>(t));
    for_each<_Index + 1, _Tuple, _Function>(t, f);
}

namespace detail { namespace at {

template < typename _Function >
struct helper
{
    inline helper(size_t index_, _Function f_) : index(index_), f(f_), count(0) {}

    template < typename _Arg >
    void operator()(_Arg &arg_) const
    {
        if(index == count++)
            f(arg_);
    }

    const size_t index;
    mutable size_t count;
    _Function f;
};

}} // end of namespace detail

template < typename _Tuple, typename _Function >
void at(_Tuple &t, size_t index_, _Function f)
{
    if(std::tuple_size<_Tuple> ::value <= index_)
        throw std::out_of_range("");

    for_each(t, detail::at::helper<_Function>(index_, f));
}

Он имеет линейную сложность. Как я могу достичь сложности O (1)?


c++ templates c++11 template-meta-programming stdtuple
person sliser    schedule 11.01.2014    source источник
comment
Являются ли типы tuple однородными?   -  person Yakk - Adam Nevraumont    schedule 11.01.2014
comment
@Yakk В общем случае это не так   -  person sliser    schedule 11.01.2014
comment
Я не уверен, сможет ли это сделать оптимизатор, но, возможно, вы сможете создать ряд if-else-if-else-if посредством метапрограммирования, который заменяется таблицей переключения/поиска.   -  person dyp    schedule 11.01.2014

Ответы (1)


arrow_upward
20
arrow_downward

Предполагая, что вы передаете что-то похожее на общую лямбду, то есть объект функции с перегруженным оператором вызова функции:

#include <iostream>

struct Func
{
    template<class T>
    void operator()(T p)
    {
        std::cout << __PRETTY_FUNCTION__ << " : " << p << "\n";
    }
};

Вы можете построить массив указателей на функции:

#include <tuple>

template<int... Is> struct seq {};
template<int N, int... Is> struct gen_seq : gen_seq<N-1, N-1, Is...> {};
template<int... Is> struct gen_seq<0, Is...> : seq<Is...> {};

template<int N, class T, class F>
void apply_one(T& p, F func)
{
    func( std::get<N>(p) );
}

template<class T, class F, int... Is>
void apply(T& p, int index, F func, seq<Is...>)
{
    using FT = void(T&, F);
    static constexpr FT* arr[] = { &apply_one<Is, T, F>... };
    arr[index](p, func);
}

template<class T, class F>
void apply(T& p, int index, F func)
{
    apply(p, index, func, gen_seq<std::tuple_size<T>::value>{});
}

Пример использования:

int main()
{
    std::tuple<int, double, char, double> t{1, 2.3, 4, 5.6};
    for(int i = 0; i < 4; ++i) apply(t, i, Func{});
}

clang++ также принимает расширение, применяемое к шаблону, содержащему лямбда-выражение:

static FT* arr[] = { [](T& p, F func){ func(std::get<Is>(p)); }... };

(хотя я должен признать, что это выглядит очень странно)

g++4.8.1 отвергает это.

person dyp    schedule 11.01.2014
comment
Создание массива из n элементов - это O (n) - person Yakk - Adam Nevraumont; 11.01.2014
comment
@Yakk Теперь это статично;) - person dyp; 11.01.2014
comment
Спасибо. Я не смог скомпилировать ваш код с msvs2013, но идея мне ясна - person sliser; 11.01.2014
comment
@sliser Хм, макрос __PRETTY_FUNCTION__ нестандартен, но остальное не должно быть слишком причудливым .. - person dyp; 11.01.2014
comment
msvs2013 имеет проблемы с ключевыми словами using и constexpr - person sliser; 11.01.2014
comment
@sliser: вы можете заменить using на typedef: typedef void (&FT)(T&, F); и ключевое слово constexpr здесь не нужно; const подойдет. - person Matthieu M.; 11.01.2014