11
\$\begingroup\$

This allows enum values to be outputted as strings. But enum_strings is a type, not a map or a vector, so if the enum value is known during compile time, there will be no look-up time at all. If the enum value is a run-time value, then the look-up time is \$O(\log N)\$ due to a binary search being made through the pack.

Note: This compiles on GCC 5.3. I did not run it on other compilers.

#include <iostream>
#include <string>
#include <type_traits>
#include <utility>
#include <tuple>

template <char... Cs>
struct string_literal {
    static constexpr char value[sizeof...(Cs)] = {Cs...};
};
template <char... Cs> constexpr char string_literal<Cs...>::value[sizeof...(Cs)];

template <typename CharT, CharT... Cs>
constexpr string_literal<Cs...> operator ""_e() { return {}; }

enum Colour {Red, Blue, Green};
enum Animal {Dog, Cat, Bird};
enum Fruit {Apple = -1, Orange = 3, Grape = 5, Banana = 100};

template <int Value, typename T>
struct E : std::integral_constant<int, Value> {
    using type = T;
};

using enum_strings = std::tuple<  // Note: the enum values in each tuple must be listed from least to greatest for enum_binary_search to work.
    std::tuple<Colour, E<Red, decltype("red"_e)>, E<Blue, decltype("blue"_e)>, E<Green, decltype("green"_e)>>,
    std::tuple<Animal, E<Dog, decltype("dog"_e)>, E<Cat, decltype("cat"_e)>, E<Bird, decltype("bird"_e)>>,
    std::tuple<Fruit, E<Apple, decltype("apple"_e)>, E<Orange, decltype("orange"_e)>, E<Grape, decltype("grape"_e)>, E<Banana, decltype("banana"_e)>>
>;

template <typename T, typename Pack> struct get_enum_pack;

template <typename T, template <typename...> class P, typename First, typename... Rest>
struct get_enum_pack<T, P<First, Rest...>> : get_enum_pack<T, P<Rest...>> {};

template <typename T, template <typename...> class P, typename... Es, typename... Packs>
struct get_enum_pack<T, P<P<T, Es...>, Packs...>> {
    using type = P<Es...>;
};

template <typename T, typename Pack> struct enum_binary_search;

template <typename T, template <typename...> class P, int... Is, typename... Ts>
struct enum_binary_search<T, P<E<Is, Ts>...>> {
    using Tuple = std::tuple<E<Is, Ts>...>;
    static std::istream& execute (std::istream& is, T& t) {
        std::string buf;
        is >> buf;
        execute_impl<0, sizeof...(Is) - 1>(buf, t);
        return is;
    }
private:
    template <std::size_t MinIndex, std::size_t MaxIndex>
    static void execute_impl (const std::string& buf, T& t) {
        constexpr std::size_t MidIndex = (MinIndex + MaxIndex) / 2;
        using S = std::tuple_element_t<MidIndex, Tuple>;
        const std::string str = S::type::value;
        if (buf == str)
            t = static_cast<T>(S::value);
        else if (buf < str)
            execute_impl<MinIndex, MidIndex>(buf, t);  // Replacing MidIndex with MidIndex - 1 leads to compiling error (array subscript out of bounds) for reasons I don't understand.
        else if (buf > str)
            execute_impl<MidIndex + 1, MaxIndex>(buf, t);
    }
};

enum SortMethod {quick_sort, merge_sort, insertion_sort};  // etc... (we'll only use quick_sort in this program)

template <typename, SortMethod, template <typename, typename> class> struct sort_types;

template<template <typename...> class P, SortMethod S, template <typename, typename> class Comparator>  
struct sort_types<P<>, S, Comparator> {  
    using type = P<>;  
};

template <typename, typename> struct prepend;

template <typename T, template <typename...> class P, typename... Ts>  
struct prepend<T, P<Ts...>> {  
    using type = P<T, Ts...>;  
};

template <typename Pack, template <typename> class UnaryPredicate> struct filter;  

template <template <typename...> class P, typename First, typename... Rest, template <typename> class UnaryPredicate>  
struct filter<P<First, Rest...>, UnaryPredicate> : std::conditional_t<UnaryPredicate<First>::value,
    prepend<First, typename filter<P<Rest...>, UnaryPredicate>::type>,
    filter<P<Rest...>, UnaryPredicate>
> {};

template <template <typename...> class P, template <typename> class UnaryPredicate>  
struct filter<P<>, UnaryPredicate> {  
    using type = P<>;  
};  

template <typename Pack1, typename Pack2> struct concat;  

template <template <typename...> class P, typename... Types1, typename... Types2>  
struct concat<P<Types1...>, P<Types2...>> {  
    using type = P<Types1..., Types2...>;
};

template <template <typename...> class P, typename First, typename... Rest, template <typename, typename> class Comparator>  
struct sort_types<P<First, Rest...>, quick_sort, Comparator> {
    template <typename T> struct less_than : std::integral_constant<bool, Comparator<T, First>::value> {};
    template <typename T> struct more_than : std::integral_constant<bool, !Comparator<T, First>::value> {};  
    using subsequence_less_than_T = typename filter<P<Rest...>, less_than>::type;
    using subsequence_more_than_T = typename filter<P<Rest...>, more_than>::type; 
    using type = typename concat<typename sort_types<subsequence_less_than_T, quick_sort, Comparator>::type,  
        typename prepend<First, typename sort_types<subsequence_more_than_T, quick_sort, Comparator>::type>::type 
    >::type;
};

template <typename, typename> struct lexicographically_less;

template <template <char...> class Z>
struct lexicographically_less<Z<>, Z<>> : std::false_type {};  // Since it is equality instead.

template <template <char...> class Z, char... Js>
struct lexicographically_less<Z<>, Z<Js...>> : std::true_type {};  // The "shorter" is always less than, if all elements preceding for both are equal.

template <template <char...> class Z, char... Is>
struct lexicographically_less<Z<Is...>, Z<>> : std::false_type {};

template <template <char...> class Z, char I, char... Is, char J, char... Js>
struct lexicographically_less<Z<I, Is...>, Z<J, Js...>> : std::conditional_t<(I < J),
    std::true_type,
    std::conditional_t<(J < I),
        std::false_type,
        lexicographically_less<Z<Is...>, Z<Js...>>
    >
 > {};

template <int V1, typename T1, int V2, typename T2>
struct lexicographically_less<E<V1, T1>, E<V2, T2>> : lexicographically_less<T1, T2> {};

template <typename T, typename = std::enable_if_t<std::is_enum<T>::value>>
std::istream& operator>> (std::istream& is, T& t) {
    using string_pack = typename sort_types<typename get_enum_pack<T, enum_strings>::type, quick_sort, lexicographically_less>::type;  // e.g. std::tuple<E<Blue, decltype("blue"_e)>, E<Green, decltype("green"_e), E<Red, decltype("red"_e)>>>, where the strings are sorted lexicographically, so then a binary search can be made.
    return enum_binary_search<T, string_pack>::execute(is, t);
}

int main() {
    Fruit f;
    std::cout << "\nChoose a fruit (type the word):  apple, orange, grape, banana\n";
    std::cin >> f;  // Uses the operator>> overload defined above--time complexity of search is in O(logN) time.
    std::cout << f << '\n';
    std::cin.get();  std::cin.get();
}
\$\endgroup\$
1
  • \$\begingroup\$ For the record, clang++ says: warning: string literal operator templates are a GNU extension [-Wgnu-string-literal-operator-template]. \$\endgroup\$ Nov 2, 2018 at 23:19

1 Answer 1

2
\$\begingroup\$

Putting multiple enum values into one enum_strings data structure means this one piece of code will depend on every single enum definition in the code-base where conversion to a string is required. It's also easy to forget to add a value.

Having a separate enum_strings-type structure for each enum would mean that the strings can be defined near the enum, and one is less likely to forget to add things to one central point. Headers containing unrelated enums from other places also won't be included accidentally.


enum_binary_search::execute_impl converts to std::string to do comparisons. This is likely to be very slow (it allocates memory and copys over all the data in the array). It also does the comparison multiple times.

std::strcmp can be used to do the comparison once, with no copying.


It's complicated and unreadable! This isn't your fault, it's just how template metaprogramming is in C++. Generally, constexpr-based solutions are simpler, and promise to get much easier with future versions of the language.

For example, here's a version that does a linear search, based on this stackoverflow answer.

#include <stdexcept>

class CExprStr // use std::string_view in C++17
{
public:

    template<std::size_t N>
    constexpr CExprStr(char const (&s)[N]): m_size(N), m_data(s) { }

    constexpr char operator[](std::size_t index) const
    {
        return
            (index >= m_size) ? throw std::out_of_range("Invalid index.") :
            m_data[index];
    }

    constexpr char const* data() const
    {
        return m_data;
    }

private:

    std::size_t m_size;
    char const* m_data;
};

namespace 
{

    constexpr bool EqualsImpl(CExprStr const& a, char const* b, std::size_t i)
    {
        return
            (a[i] != b[i]) ? false :
            (a[i] == 0 || b[i] == 0) ? true :
            EqualsImpl(a, b, i + 1);
    }

} // unnamed

constexpr bool operator==(CExprStr const& a, char const* b)
{
    return EqualsImpl(a, b, 0);
}


#include <tuple>
#include <stdexcept>

template<class EnumT>
using EnumStringT = std::tuple<EnumT, CExprStr>;

template<class EnumT, std::size_t N>
using EnumMapT = std::array<EnumStringT<EnumT>, N>;

template<class EnumT, std::size_t N>
constexpr char const* EnumGetValue(EnumMapT<EnumT, N> const& map, EnumT key, std::size_t i = 0)
{
    return
        (i == map.size()) ? throw std::invalid_argument("Enum key not present in map.") : // (will also fail to compile, as it's not a constant expression).
        (std::get<0>(map[i]) == key) ? std::get<1>(map[i]).data() : 
        EnumGetValue(map, key, i + 1);
}

template<class EnumT, std::size_t N>
constexpr EnumT EnumGetKey(EnumMapT<EnumT, N> const& map, char const* value, std::size_t i = 0)
{
    return
        (i == map.size()) ? throw std::invalid_argument("Enum value not present in map.") : // (will also fail to compile, as it's not a constant expression).
        (std::get<1>(map[i]) == value) ? std::get<0>(map[i]) :
        EnumGetKey(map, value, i + 1);
}


#include <array>
#include <iostream>
#include <string>

enum class Color { Red, Green, Blue };

namespace
{
    using E = EnumStringT<Color>;

    constexpr EnumMapT<Color, 3> ColorStringMap =
    {{
        E{ Color::Red, "red" },
        E{ Color::Green, "green" },
        E{ Color::Blue, "blue" },
    }};

} // unnamed 

constexpr char const* ColorToString(Color value)
{
    return EnumGetValue(ColorStringMap, value);
}

std::ostream& operator<<(std::ostream& stream, Color value)
{
    stream << ColorToString(value);
    return stream;
}

constexpr Color StringToColor(char const* value)
{
    return EnumGetKey(ColorStringMap, value);
}

std::istream& operator>>(std::istream& stream, Color& value)
{
    auto buffer = std::string();
    stream >> buffer;

    value = StringToColor(buffer.c_str());

    return stream;
}


#include <iostream>
#include <sstream>

int main()
{
    {
        constexpr auto red = ColorToString(Color::Red);
        //constexpr auto invalid = ColorToString((Color)-1); // won't compile
        //auto invalid = ColorToString((Color)-1); // throws std::invalid_argument
        std::cout << red << std::endl;
    }

    {
        std::cout << Color::Green << std::endl;
    }

    {
        constexpr auto red = StringToColor("red");
        //constexpr auto invalid = StringToColor("sdlfkj"); // won't compile
        std::cout << red << std::endl;
    }

    {
        std::stringstream stream("green");
        //std::stringstream stream("grsdfkl"); // throws std::invalid_argument when parsed

        auto c = Color::Blue;
        stream >> c;

        std::cout << c << std::endl;
    }
}

CExprStr exists purely to do string comparison between const char*s, since std::strcmp isn't a constexpr function. In C++17, we can delete the whole class and use std::string_view instead.

Similarly, in C++20, a whole bunch of std algorithms become constexpr, including std::find_if, std::binary_search, std::lexicographical_compare, which makes a constexpr based solution more appealing.

It should be fairly simple to add binary lookup to EnumGetValue and EnumGetKey above. Sorting the array in a constexpr function will still be tricky in C++14, but slightly easier in C++17.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.