The code below implements a dichotomic search to find if a runtime integral value exist in an enum. Because enum are compile time known, the code try to generate the sorted array of the enum values in a constexpr way and have a constexpr compatible find.
#include <iostream>
#include <type_traits>
// ============================
using std::cout; using std::endl;
constexpr char const * const el = "\n";
// ============================
template < typename T_, typename = typename std::enable_if<std::is_enum<T_>::value>::type >
std::ostream & operator<<( std::ostream & os, T_ const & v ) {
return os << static_cast<typename std::underlying_type<T_>::type>(v)<< " ";
}
// ============================
// Minimum support for a constexpr array because std::array::operator[] lacks constexpr
template <typename T_, size_t N_>
struct Array {
constexpr size_t size() const { return N_; }
constexpr T_& operator[]( size_t i ) { return values_[i]; }
constexpr T_ const& operator[]( size_t i ) const { return values_[i]; }
constexpr T_* begin() { return values_; }
constexpr T_* end() { return values_+N_; }
constexpr T_ const * begin() const { return values_; }
constexpr T_ const * end() const { return values_+N_; }
T_ values_[N_];
};
// ============================
// return a sorted copy of the array argument
template <typename T_, size_t N_>
constexpr Array<T_, N_> const_sort( Array<T_, N_> tab ) {
Array<T_, N_> result{ T_{} };
for( size_t i{}; i != N_; ++i )
result[i] = tab[i];
for( size_t i{}; i != N_-1; ++i ) {
size_t min {i};
for( size_t j{ i+1 }; j != N_; ++j ) {
if( result[j] < result[min] )
min = j;
}
if( min != i ) {
auto tmp = std::move( result[i] );
result[i] = std::move( result[min] );
result[min] = std::move( tmp );
}
}
return result;
}
// ============================
// The user has to specialize UnsortedFunc to return an Array<EnumType,N>
template <typename T_>
constexpr auto const UnsortedFunc();
template <typename T_>
constexpr const decltype(UnsortedFunc<T_>()) Unsorted = UnsortedFunc<T_>();
// ============================
template < typename T_ >
constexpr decltype( const_sort( Unsorted<T_> ) ) Sorted = const_sort( Unsorted<T_> );
// ============================
// check for existence of a matching enum member equal to an integral value.
// The user has to feed a specialization of UnsortedFunc with the enum values.
template< typename E_>
constexpr bool Contains( typename std::underlying_type<E_>::type v ) {
using T = typename std::underlying_type<E_>::type;
T min = static_cast<T>(Sorted<E_>[0]);
T max = static_cast<T>(Sorted<E_>[Sorted<E_>.size()-1]);
if ( v < min || max < v )
return false;
size_t low {}, high { Sorted<E_>.size() };
while ( low < high ) {
size_t mid = (high + low ) / 2;
if ( v < static_cast<T>(Sorted<E_>[ mid ]) ) {
high = mid;
} else {
if ( !( static_cast<T>(Sorted<E_>[ mid ]) < v ) )
return true;
low = mid+1;
}
}
return false;
}
template < typename T_ >
void Dump() {
for( auto & v : Unsorted<T_> )
cout << v << " ";
cout << el;
for( auto & v : Sorted<T_> )
std::cout << v << " ";
cout << el;
}
enum class Foo : int { a=5, b=2, c = 8, d = 1, e = 4, f = 9 };
template <> constexpr auto const UnsortedFunc<Foo>() {
return Array<Foo,6>{ Foo::a, Foo::b, Foo::c, Foo::d, Foo::e, Foo::f };
}
By playing with this code in the main function, i can have a lot of different of warnings and errors.
That one compile and link but i had to dump the two arrays first, still with a warning :
int main() {
cout << std::boolalpha << __VERSION__ << el;
for( auto & v : Unsorted<Foo> )
cout << v << " ";
cout << el;
for( auto & v : Sorted<Foo> )
std::cout << v << " ";
cout << el;
constexpr bool b1 = Contains<Foo>(2);
constexpr bool b2 = Contains<Foo>(10);
cout << b1 << " " << b2 << el;
for( int i{}; i != 10; ++i )
cout << i << " : " << Contains<Foo>(i) << ", ";
}
And the output :
main.cpp:60:46: warning: variable 'Unsorted<type-parameter-0-0>' has internal linkage but is not defined [-Wundefined-internal]
constexpr const decltype(UnsortedFunc<T_>()) Unsorted = UnsortedFunc<T_>();
^
main.cpp:64:71: note: used here
constexpr decltype( const_sort( Unsorted<T_> ) ) Sorted = const_sort( Unsorted<T_> );
^
1 warning generated.
4.2.1 Compatible Clang 3.5 (trunk 198621)
5 2 8 1 4 9
1 2 4 5 8 9
true false
0 : false, 1 : true, 2 : true, 3 : false, 4 : true, 5 : true, 6 : false, 7 : false, 8 : true, 9 : true,
If i remove the two array dump, i have compilation errors, b1 and b2 cannot anymore be evaluated as constexpr expressions :
int main() {
cout << std::boolalpha << __VERSION__ << el;
constexpr bool b1 = Contains<Foo>(2);
constexpr bool b2 = Contains<Foo>(10);
cout << b1 << " " << b2 << el;
for( int i{}; i != 10; ++i )
cout << i << " : " << Contains<Foo>(i) << ", ";
}
With the output :
main.cpp:116:20: error: constexpr variable 'b1' must be initialized by a constant expression
constexpr bool b1 = Contains<Foo>(2);
^ ~~~~~~~~~~~~~~~~
main.cpp:72:28: note: subexpression not valid in a constant expression
T min = static_cast<T>(Sorted<E_>[0]);
^
main.cpp:116:25: note: in call to 'Contains(2)'
constexpr bool b1 = Contains<Foo>(2);
^
main.cpp:117:20: error: constexpr variable 'b2' must be initialized by a constant expression
constexpr bool b2 = Contains<Foo>(10);
^ ~~~~~~~~~~~~~~~~~
main.cpp:72:28: note: subexpression not valid in a constant expression
T min = static_cast<T>(Sorted<E_>[0]);
^
main.cpp:117:25: note: in call to 'Contains(10)'
constexpr bool b2 = Contains<Foo>(10);
^
2 errors generated.
Last, if i try to dump the arrays with the Dump function, link errors arrive too :
int main() {
cout << std::boolalpha << __VERSION__ << el;
Dump<Foo>();
}
With the output :
main.cpp:60:46: warning: variable 'Unsorted<type-parameter-0-0>' has internal linkage but is not defined [-Wundefined-internal]
constexpr const decltype(UnsortedFunc<T_>()) Unsorted = UnsortedFunc<T_>();
^
main.cpp:64:71: note: used here
constexpr decltype( const_sort( Unsorted<T_> ) ) Sorted = const_sort( Unsorted<T_> );
^
main.cpp:60:46: warning: variable 'Unsorted<Foo>' has internal linkage but is not defined [-Wundefined-internal]
constexpr const decltype(UnsortedFunc<T_>()) Unsorted = UnsortedFunc<T_>();
^
main.cpp:93:21: note: used here
for( auto & v : Unsorted<T_> )
^
main.cpp:64:50: warning: variable 'Sorted<Foo>' has internal linkage but is not defined [-Wundefined-internal]
constexpr decltype( const_sort( Unsorted<T_> ) ) Sorted = const_sort( Unsorted<T_> );
^
main.cpp:97:21: note: used here
for( auto & v : Sorted<T_> )
^
3 warnings generated.
/tmp/main-22b320.o: In function `void Dump<Foo>()':
main.cpp:(.text._Z4DumpI3FooEvv[_Z4DumpI3FooEvv]+0xc): undefined reference to `_ZL8UnsortedI3FooE'
main.cpp:(.text._Z4DumpI3FooEvv[_Z4DumpI3FooEvv]+0x20): undefined reference to `_ZL8UnsortedI3FooE'
main.cpp:(.text._Z4DumpI3FooEvv[_Z4DumpI3FooEvv]+0x98): undefined reference to `_ZL6SortedI3FooE'
main.cpp:(.text._Z4DumpI3FooEvv[_Z4DumpI3FooEvv]+0xb0): undefined reference to `_ZL6SortedI3FooE'
clang: error: linker command failed with exit code 1 (use -v to see invocation)
Bonus question, on the Sorted and Unsorted definition line, if i use const auto instead of decltype :
main.cpp:73:49: error: member reference base type 'const auto' is not a structure or union
T max = static_cast<T>(Sorted<E_>[Sorted<E_>.size()-1]);
~~~~~~~~~~^~~~~
main.cpp:77:37: error: member reference base type 'const auto' is not a structure or union
size_t low {}, high { Sorted<E_>.size() };
~~~~~~~~~~^~~~~
main.cpp:77:20: error: variables defined in a constexpr function must be initialized
size_t low {}, high { Sorted<E_>.size() };
^
main.cpp:93:19: error: invalid range expression of type 'const auto'; no viable 'begin' function available
for( auto & v : Unsorted<T_> )
^ ~~~~~~~~
main.cpp:114:5: note: in instantiation of function template specialization 'Dump<Foo>' requested here
Dump<Foo>();
^
main.cpp:97:19: error: invalid range expression of type 'const auto'; no viable 'begin' function available
for( auto & v : Sorted<T_> )
^ ~~~~~~
5 errors generated.
https://stackoverflow.com/questions/22116097
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian