I have a long array of key+value data that I would like to initialize into my source code with constexpr initializer. I can sort the array myself in the source code, so it could be efficiently searched with a binary search algorithm. The structure has a key part and one (or more) value parts.

Here is a simple example of what I mean:

struct MyArrayElement { const char* key, int value };
constexpr MyArrayElement MyArray[] = {
 { "abc", 923 },
 { "def", 456 },
 /* ... */
 { "xyz", 178 },
};

I can use STL algorithm “find_if” to search for the key:

std::string key_to_find{ "xyz" };
auto const elem = find_if(std::begin(MyArray), std::end(MyArray),
  [&key_to_find](auto const& elem){ return key_to_find == elem.key; });

As the find_if algorithm cannot know that I have sorted the keys, it will not be able to take advantage of that knowledge to efficiently search the array.

I had a look at std::binary_search, but this seems to want to equate the whole Element (i.e. both key and value) and I only want to specify a key in the search predicate.

I have looked over the various STL algorithm, but nothing stood out that does what I want. I could always very easily write my own binary search template function, but I was hoping to use an off the shelf standard algorithm.

So these are my potential options in order of most to least preferred:

• Try to find a different standard algorithm that does binary search on just the key field of the structure.
• Try to find a different container that can be constructed constexpr and is better designed for efficient search.
• Write my own binary search template function that will search only on the key field.
• Split the key and value structures into 2 separate arrays, but this will no doubt make maintaining the code much more prone to error, because they will be on different lines of the source code.

I’m open to other ideas on how to solve this problem.