Эффективное двунаправленное сопоставление перечислений - PullRequest
Новая
       11

Эффективное двунаправленное сопоставление перечислений

2 голосов
/ 26 марта 2019

Имея: 

enum class A : int {
    FirstA,
    SecondA,
    InvalidB
};

enum class B : int {
    FirstB,
    SecondB,
    InvalidB
};

Как включить что-то подобное? 

B b = mapper[A::FirstA];
A a = mapper[B::SecondB];

Одним из возможных решений является создание шаблона класса Mapper, который позволяет задавать отображение с помощьюсписок инициализатора в конструкторе, что-то вроде: 

Mapper<A, B> mapper(
     {
     {A::FirstA,   B::SecondB},
     {A::SecondA,  B::FirstB}
     },
     {A::InvalidA, B::InvalidB} // this is for conversions, where no mapping is specified
);

Но внутренне это потребует компромиссов - либо две карты (от A до B и от B до A), либо одна картанапример, от A до B и линейного поиска для преобразований B в A).

Возможно ли реализовать это в стандарте C++14 так, чтобы:

  • двойные контейнеры не используются
  • производительность поиска одинаково хороша в обоих направлениях
  • определение и использование отображения относительно просты (внутренняя реализация не обязательна)

С учетом требований:

  • это не отображение идентификаторов (т. Е. Значения из A не сопоставляются с теми же базовыми значениями B
  • базовых типов A и B маy отличаются
  • отображение известно во время компиляции

?

Ответы [ 3 ]

2 голосов
/ 26 марта 2019

Вы можете сделать это довольно легко, используя шаблоны функций и полную специализацию.Вы заставляете основной шаблон возвращать неверный регистр, а затем специализации возвращают нужные вам сопоставления.

Если у вас есть 

template<A>
B mapper() { return B::InvalidB; }
template<B>
A mapper() { return A::InvalidA; }

, тогда вы можете добавить все сопоставленные значения, например 

template<>
B mapper<A::FirstA>() { return B::SecondB; }
template<>
B mapper<A::SecondA>() { return B::FirstB; }
template<>
A mapper<B::FirstB>() { return A::SecondA; }
template<>
A mapper<B::SecondB>() { return A::FirstA; }

и тогда вы бы назвали это как 

B b = mapper<A::FirstA>();
A a = mapper<B::SecondB>();

Это оставляет вас без контейнеров вообще.Вы можете даже сделать несколько макросов, чтобы сделать это проще, например 

#define MAKE_ENUM_MAP(from, to) \
template<from> \
auto mapper() { return to::Invalid; } \
template<to> \
auto mapper() { return from::Invalid; }


#define ADD_MAPPING(from_value, to_value) \
template<> \
auto mapper<from_value>() { return to_value; } \
template<> \
auto mapper<to_value>() { return from_value; }

, а затем использовать их как 

MAKE_ENUM_MAP(A, B)
ADD_MAPPING(A::FirstA, B::SecondB)
ADD_MAPPING(A::SecondA, B::FirstB)

, чтобы сгенерировать весь код для вас.Приведенная выше версия использует одно значение перечисления Invalid для недопустимого случая сопоставлений.Если вы не хотите этого, вы можете добавить в макрос значения from и to, которые будут использоваться для недопустимых отображений, таких как 

#define MAKE_ENUM_MAP(from, from_value, to, to_value) \
template<from> \
auto mapper() { return to_value; } \
template<to> \
auto mapper() { return from_value; }

, и вы бы назвали их как 

MAKE_ENUM_MAP(A, A::InvalidA, B, B::InvalidB)
1 голос
/ 26 марта 2019

Если вам нужно выполнить поиск во время выполнения, следующий метод будет работать со сложностью O (1) в обоих направлениях.

Поскольку все ваши перечислители A и B не инициализированы, первый перечислитель имеет значение ноль, второй имеет значение 1 и т. Д. Рассматривая эти начальные с нуля целые числа как индексы массивов, мы можем построить двунаправленную карту, используя два массива. Например, принимая текущее отображение как 

A::FirstA  (=0) <--> B::SecondB (=1),
A::SecondA (=1) <--> B::FirstB  (=0),

, тогда давайте определим следующие два массива 

A arrA[2] = {A::SecondA, A::FirstA},
B arrB[2] = {B::SecondB, B::FirstB},

, где arrA[i] - это перечислитель A, соответствующий i -ому перечислителю B, и наоборот. В этой настройке мы можем выполнить поиск от A a до B как arrB[std::size(a)] и наоборот со сложностью O (1).

Следующий класс biENumMap является примером реализации вышеуказанного двунаправленного метода с C ++ 14 и более поздними версиями. Обратите внимание, что поскольку расширенный * constexpr доступен из C ++ 14, здесь ctor также может быть константным выражением. Две перегрузки operator() являются функциями поиска из A и B соответственно. Это также могут быть константные выражения, и этот класс позволяет нам выполнять двунаправленный поиск как во время компиляции, так и во время выполнения: 

template<std::size_t N>
class biENumMap
{
    A arrA[N];
    B arrB[N];

public:
    constexpr biENumMap(const std::array<std::pair<A,B>, N>& init) 
        : arrA(), arrB()
    {        
        for(std::size_t i = 0; i < N; ++i)
        {
            const auto& p = init[i];
            arrA[static_cast<std::size_t>(p.second)] = p.first;
            arrB[static_cast<std::size_t>(p.first) ] = p.second;
        }
    }

    constexpr A operator()(B b) const{
        return arrA[static_cast<std::size_t>(b)];
    }

    constexpr B operator()(A a) const{
        return arrB[static_cast<std::size_t>(a)];
    }
};

Мы можем использовать этот класс следующим образом:

DEMO 

// compile-time construction.
constexpr biEnumMap<3> mapper({{
    {A::FirstA  , B::SecondB },
    {A::SecondA , B::FirstB  },
    {A::InvalidA, B::InvalidB} }});

// compile-time tests, A to B.
static_assert(mapper(A::FirstA  ) == B::SecondB );
static_assert(mapper(A::SecondA ) == B::FirstB  );
static_assert(mapper(A::InvalidA) == B::InvalidB);

// compile-time tests, B to A.
static_assert(mapper(B::FirstB  ) == A::SecondA );
static_assert(mapper(B::SecondB ) == A::FirstA  );
static_assert(mapper(B::InvalidB) == A::InvalidA);

// run-time tests, A to B.
std::vector<A> vA = {A::FirstA, A::SecondA, A::InvalidA};
assert(mapper(vA[0]) == B::SecondB );
assert(mapper(vA[1]) == B::FirstB  );
assert(mapper(vA[2]) == B::InvalidB);    

// run-time tests, B to A.
std::vector<B> vB = {B::FirstB, B::SecondB, B::InvalidB};
assert(mapper(vB[0]) == A::SecondA );
assert(mapper(vB[1]) == A::FirstA  );
assert(mapper(vB[2]) == A::InvalidA);
1 голос
/ 26 марта 2019

Решение Натана трудно превзойти с точки зрения элегантности реализации. Но если вам отчаянно нужно решение, которое не зависит от макросов или может также использоваться во время выполнения, вот то, где вы указываете отображение в простом списке пар.

В основе этого лежит тот факт, что оба перечисления должны иметь смежные базовые интегральные значения (начиная с нуля), что означает, что мы можем представлять отображения в обоих направлениях как простые массивы. Это все constexpr, поэтому в случае компиляции ноль накладных расходов. Для использования во время выполнения это действительно сохраняет информацию дважды, чтобы обеспечить мгновенный поиск, но занимает только N (sizeof(A) + sizeof(B)) хранилище. Я не знаю какой-либо структуры данных, которая работает лучше (то есть не хранит никаких дополнительных данных за пределами одного из двух массивов и лучше, чем линейный поиск в обоих направлениях). Обратите внимание, что это занимает то же хранилище, что и для хранения самих пар (но ничего не получает от биективности отображения). 

template<class TA, class TB, class ... Pairs>
struct Mapper
{
    constexpr static std::array<TA, sizeof...(Pairs)> generateAIndices()
    {
        std::array<TA, sizeof...(Pairs)> ret{};
        ((void)((ret[static_cast<std::size_t>(Pairs::tb)] = Pairs::ta), 0), ...);
        return ret;
    }
    constexpr static std::array<TB, sizeof...(Pairs)> generateBIndices()
    {
        std::array<TB, sizeof...(Pairs)> ret{};
        ((void)((ret[static_cast<std::size_t>(Pairs::ta)] = Pairs::tb), 0), ...);
        return ret;
    }

    constexpr TB operator[](TA ta)
    {
        return toB[static_cast<std::size_t>(ta)];
    }
    constexpr TA operator[](TB tb)
    {
        return toA[static_cast<std::size_t>(tb)];
    }

    static constexpr std::array<TA, sizeof...(Pairs)> toA = generateAIndices();
    static constexpr std::array<TB, sizeof...(Pairs)> toB = generateBIndices();
};

(При этом используются выражения складывания + оператор запятой для присвоения значений элементам массива, см., Например, здесь ).

Код пользователя предоставляет список используемых пар сопоставления и готов: 

using MyMappingList = PairList<
    MyMappingPair<A::A1, B::B2>,
    MyMappingPair<A::A2, B::B3>,
    MyMappingPair<A::A3, B::B4>,
    MyMappingPair<A::A4, B::B1>
    >;

auto mapper = makeMapper<A, B>(MyMappingList{});

Демонстрация , включая полные тестовые сценарии во время компиляции и максимально эффективный код времени выполнения (буквально mov).

Вот предыдущая версия, которая работает только во время компиляции (см. Также историю изменений): https://godbolt.org/z/GCkAhn

...