What's a good way to store a small, fixed size, hierarchical set of static data?

Viewed 666

I'm looking for a way to store a small multidimensional set of data which is known at compile time and never changes. The purpose of this structure is to act as a global constant that is stored within a single namespace, but otherwise globally accessible without instantiating an object.

If we only need one level of data, there's a bunch of ways to do this. You could use an enum or a class or struct with static/constant variables:

class MidiEventTypes{
   public:
   static const char NOTE_OFF = 8;
   static const char NOTE_ON = 9;
   static const char KEY_AFTERTOUCH = 10;
   static const char CONTROL_CHANGE = 11;
   static const char PROGRAM_CHANGE = 12;
   static const char CHANNEL_AFTERTOUCH = 13;
   static const char PITCH_WHEEL_CHANGE = 14;
};

We can easily compare a numeric variable anywhere in the program by using this class with it's members:

char nTestValue = 8;
if(nTestValue == MidiEventTypes::NOTE_OFF){} // do something...

But what if we want to store more than just a name and value pair? What if we also want to store some extra data with each constant? In our example above, let's say we also want to store the number of bytes that must be read for each event type.

Here's some pseudo code usage:

char nTestValue = 8;
if(nTestValue == MidiEventTypes::NOTE_OFF){
   std::cout << "We now need to read " << MidiEventTypes::NOTE_OFF::NUM_BYTES << " more bytes...." << std::endl;
}

We should also be able to do something like this:

char nTestValue = 8;
// Get the number of read bytes required for a MIDI event with a type equal to the value of nTestValue.
char nBytesNeeded = MidiEventTypes::[nTestValue]::NUM_BYTES; 

Or alternatively:

char nTestValue = 8;    
char nBytesNeeded = MidiEventTypes::GetRequiredBytesByEventType(nTestValue);

and:

char nBytesNeeded = MidiEventTypes::GetRequiredBytesByEventType(NOTE_OFF);

This question isn't about how to make instantiated classes do this. I can do that already. The question is about how to store and access "extra" constant (unchanging) data that is related/attached to a constant. (This structure isn't required at runtime!) Or how to create a multi-dimensional constant. It seems like this could be done with a static class, but I've tried several variations of the code below, and each time the compiler found something different to complain about:

static class MidiEventTypes{
   
   public:
   static const char NOTE_OFF = 8;
   static const char NOTE_ON = 9;
   static const char KEY_AFTERTOUCH = 10; // Contains Key Data
   static const char CONTROL_CHANGE = 11; // Also: Channel Mode Messages, when special controller ID is used.
   static const char PROGRAM_CHANGE = 12;
   static const char CHANNEL_AFTERTOUCH = 13;
   static const char PITCH_WHEEL_CHANGE = 14;
   
   // Store the number of bytes required to be read for each event type.
   static std::unordered_map<char, char> BytesRequired = {
      {MidiEventTypes::NOTE_OFF,2},
      {MidiEventTypes::NOTE_ON,2},
      {MidiEventTypes::KEY_AFTERTOUCH,2},
      {MidiEventTypes::CONTROL_CHANGE,2},
      {MidiEventTypes::PROGRAM_CHANGE,1},
      {MidiEventTypes::CHANNEL_AFTERTOUCH,1},
      {MidiEventTypes::PITCH_WHEEL_CHANGE,2},
   };
   
   static char GetBytesRequired(char Type){
      return MidiEventTypes::BytesRequired.at(Type);
   }
   
};

This specific example doesn't work because it won't let me create a static unordered_map. If I don't make the unordered_map static, then it compiles but GetBytesRequired() can't find the map. If I make GetBytesRequired() non-static, it can find the map, but then I can't call it without an instance of MidiEventTypes and I don't want instances of it.

Again, this question isn't about how to fix the compile errors, the question is about what is the appropriate structure and design pattern for storing static/constant data that is more than a key/value pair.

These are the goals:

  • Data and size is known at compile time and never changes.

  • Access a small set of data with a human readable key to each set. The key should map to a specific, non-linear integer.

  • Each data set contains the same member data set. ie. Each MidiEventType has a NumBytes property.

  • Sub-items can be accessed with a named key or function.

  • With the key, (or a variable representing the key's value), we should be able to read extra data associated with the constant item that the key points to, using another named key for the extra data.

  • We should not need to instantiate a class to read this data, as nothing changes, and there should not be more than one copy of the data set.

  • In fact, other than an include directive, nothing should be required to access the data, because it should behave like a constant.

  • We don't need this object at runtime. The goal is to make the code more organized and easier to read by storing groups of data with a named label structure, rather than using (ambiguous) integer literals everywhere.

  • It's a constant that you can drill down into... like JSON.

  • Ideally, casting should not be required to use the value of the constant.

  • We should avoid redundant lists that repeat data and can get out of sync. For example, once we define that NOTE_ON = 9, The literal 9 should not appear anywhere else. The label NOTE_ON should be used instead, so that the value can be changed in only one place.

  • This is a generic question, MIDI is just being used as an example.

  • Constants should be able to have more than one property.

What's the best way to store a small, fixed size, hierarchical (multidimensional) set of static data which is known at compile time, with the same use case as a constant?

8 Answers

Here is my take on it, a full constexpr compile time solution. For your use also put the midi stuff in a header file and you're good to go.

With header files https://www.onlinegdb.com/lGp7zMNB6

#include <iostream>
#include "const_string.h"
#include "const_map.h"

namespace midi
{
    using data_t = char;
    using string_t = const_string<32>; // 32 is big enough to hold strings in map

    namespace control
    {
        constexpr data_t NOTE_OFF = 8;
        constexpr data_t NOTE_ON = 9;
        constexpr data_t KEY_AFTERTOUCH = 10;
        constexpr data_t CONTROL_CHANGE = 11;
        constexpr data_t PROGRAM_CHANGE = 12;
        constexpr data_t CHANNEL_AFTERTOUCH = 13;
        constexpr data_t PITCH_WHEEL_CHANGE = 14;
    } /* namespace control */

    constexpr auto required_bytes = make_const_map<data_t, data_t>({
        {control::NOTE_OFF,2},
        {control::NOTE_ON,2},
        {control::KEY_AFTERTOUCH,2},
        {control::CONTROL_CHANGE,2},
        {control::PROGRAM_CHANGE,1},
        {control::CHANNEL_AFTERTOUCH,1},
        {control::PITCH_WHEEL_CHANGE,2}
    });

    constexpr auto str = make_const_map<data_t, string_t>({
        { control::NOTE_ON,"Note on" },
        { control::NOTE_OFF,"Note off" },
        { control::CONTROL_CHANGE, "Control change"},
        { control::CHANNEL_AFTERTOUCH, "Channel aftertouch"},
        { control::PITCH_WHEEL_CHANGE, "Pitch wheel change"}
    });

} /* namespace midi */

int main()
{
    static_assert(midi::control::NOTE_OFF == 8, "test failed");
    static_assert(midi::required_bytes[midi::control::NOTE_OFF] == 2, "test failed");
    static_assert(midi::required_bytes[13] == 1, "test failed");
    static_assert(midi::str[midi::control::NOTE_OFF] == "Note off", "test failed");

    return 0;
}

// Edit after acceptance : cleaner syntax

#include <iostream>
#include "const_string.h"
#include "const_map.h"

namespace midi_details
{
    using data_t = char;
    using string_t = const_string<32>;
}

constexpr midi_details::data_t MIDI_NOTE_OFF = 8;
constexpr midi_details::data_t MIDI_NOTE_ON = 9;
constexpr midi_details::data_t MIDI_KEY_AFTERTOUCH = 10;
constexpr midi_details::data_t MIDI_CONTROL_CHANGE = 11;
constexpr midi_details::data_t MIDI_PROGRAM_CHANGE = 12;
constexpr midi_details::data_t MIDI_CHANNEL_AFTERTOUCH = 13;
constexpr midi_details::data_t MIDI_PITCH_WHEEL_CHANGE = 14;

namespace midi_details
{
    constexpr auto required_bytes = make_const_map<data_t, data_t>({
        {MIDI_NOTE_OFF,2},
        {MIDI_NOTE_ON,2},
        {MIDI_KEY_AFTERTOUCH,2},
        {MIDI_CONTROL_CHANGE,2},
        {MIDI_PROGRAM_CHANGE,1},
        {MIDI_CHANNEL_AFTERTOUCH,1},
        {MIDI_PITCH_WHEEL_CHANGE,2}
        });

    constexpr auto str = make_const_map<data_t, string_t>({
            { MIDI_NOTE_ON,"Note on" },
            { MIDI_NOTE_OFF,"Note off" },
            { MIDI_CONTROL_CHANGE, "Control change"},
            { MIDI_CHANNEL_AFTERTOUCH, "Channel aftertouch"},
            { MIDI_PITCH_WHEEL_CHANGE, "Pitch wheel change"}
        });

    struct info_t
    {
        constexpr info_t(data_t r, string_t n) :
            required_bytes{ r },
            name{ n }
        {
        }

        data_t  required_bytes;
        string_t name;
    };

} /* namespace midi_details */

constexpr auto midi(midi_details::data_t value)
{
    return midi_details::info_t{ midi_details::required_bytes[value], midi_details::str[value] };
}

int main()
{
    static_assert(MIDI_NOTE_OFF == 8);
    static_assert(midi(MIDI_NOTE_OFF).required_bytes == 2, "test failed");
    static_assert(midi(MIDI_NOTE_OFF).name == "Note off", "test failed");

    return 0;
}

How about something like:

struct MidiEventType
{
    char value;
    char byteRequired; // Store the number of bytes required to be read
};

struct MidiEventTypes{
   static constexpr MidiEventType NOTE_OFF { 8, 2};
   static constexpr MidiEventType NOTE_ON { 9, 2};
   static constexpr MidiEventType KEY_AFTERTOUCH { 10, 2};
   static constexpr MidiEventType CONTROL_CHANGE { 11, 2};
   static constexpr MidiEventType PROGRAM_CHANGE  { 12, 1};
   static constexpr MidiEventType CHANNEL_AFTERTOUCH { 13, 1};
   static constexpr MidiEventType PITCH_WHEEL_CHANGE { 14, 2};
};

Here is my take using templates. I'm using int instead of char but you can change these to suit your needs. Live code here

#include <iostream>

template <int V, int B>
struct MidiEventType
{
    static constexpr int value = V;

    static constexpr int bytes = B;

    constexpr operator int() const
    {
        return V;
    }
};

// dummy classes, used for accessing a given property from MidiEventType
// create as many as the number of properties in MidiEventType and specialize GetProperty for each
struct Value;
struct Bytes;

template <class T, class Property>
struct GetProperty;

template <class T>
struct GetProperty<T, Value>
{
    static constexpr auto property = T::value;
};

template <class T>
struct GetProperty<T, Bytes>
{
    static constexpr auto property = T::bytes;
};

struct MidiEventTypes
{
    static constexpr MidiEventType<8,2> NOTE_OFF{};
    static constexpr MidiEventType<9,2> NOTE_ON{};
    static constexpr MidiEventType<10,2> KEY_AFTERTOUCH{};
    static constexpr MidiEventType<11,2> CONTROL_CHANGE{};
    static constexpr MidiEventType<12,1> PROGRAM_CHANGE{};
    static constexpr MidiEventType<13,1> CHANNEL_AFTERTOUCH{};
    static constexpr MidiEventType<14,2> PITCH_WHEEL_CHANGE{};
    static constexpr MidiEventType<-1,-1> INVALID{};

    // perform the lookup
    template <class Property>
    static constexpr auto get(int key)
    {
        return get_impl<Property, decltype(NOTE_OFF), decltype(NOTE_ON),
                decltype (KEY_AFTERTOUCH), decltype (CONTROL_CHANGE),
                decltype (PROGRAM_CHANGE), decltype (CHANNEL_AFTERTOUCH),
                decltype (PITCH_WHEEL_CHANGE)>::call(key);
    }

private:

    // class to automate the construction of if/else branches when looking up the key
    // our template parameters here will be MidiEventType<X,Y>
    template <class Property, class T, class... Rest>
    struct get_impl
    {
        static constexpr auto call(int key)
        {
            if(T::value == key) return GetProperty<T, Property>::property;
            else return get_impl<Property, Rest...>::call(key);
        }
    };

    // specialization for a single class
    // if the key is not found then return whatever we've set for the INVALID type
    template <class Property, class T>
    struct get_impl<Property, T>
    {
        static constexpr auto call(int key)
        {
            if(T::value == key) return GetProperty<T, Property>::property;
            else return GetProperty<decltype(INVALID), Property>::property;
        }
    };
};

int main()
{
    std::cout << MidiEventTypes::CHANNEL_AFTERTOUCH.bytes << std::endl;
    std::cout << MidiEventTypes::get<Value>(MidiEventTypes::NOTE_OFF) << std::endl;
    std::cout << MidiEventTypes::get<Bytes>(MidiEventTypes::CHANNEL_AFTERTOUCH) << std::endl;
    std::cout << MidiEventTypes::get<Bytes>(42) << std::endl; // invalid key, return INVALID.bytes
}

Lots of good clever solutions here for sure, though I feel like someone needs to offer to represent the simple approach. As long as you can get by without needing to literally always use square brackets to look up metadata, you can just use a switch statement in a constexpr function. Here's my solution:

#include <iostream>

namespace MidiEvents {

struct MidiEventMetaData {
    int num_bytes;
    const char *str;
    uint32_t stuff;
};

enum MidiEventTypes {
   NOTE_OFF = 8,
   NOTE_ON = 9,
   KEY_AFTERTOUCH = 10,
   CONTROL_CHANGE = 11,
   PROGRAM_CHANGE = 12,
   CHANNEL_AFTERTOUCH = 13,
   PITCH_WHEEL_CHANGE = 14,
   OTHER = 17
};

constexpr MidiEventMetaData get(char event_type)
{
    switch (event_type) {
    default:
        break;
    case NOTE_OFF:
        return { 1, "note off", 7 }; 
    case NOTE_ON:
        return { 1, "note on", 20 }; 
    case KEY_AFTERTOUCH:
        return { 2, "aftertouch", 100 };
    }
    return { 0, "unknown", 0 };
}

constexpr char GetRequiredBytesByEventType(char event_type)
{
    return get(event_type).num_bytes;
}

constexpr const char *GetEventNameByType(char event_type)
{
    return get(event_type).str;
}

} // namespace MidiEvents

int main(int argc, char **argv)
{
    char num_bytes = MidiEvents::GetRequiredBytesByEventType(MidiEvents::KEY_AFTERTOUCH);
    const char * const name = MidiEvents::GetEventNameByType(MidiEvents::KEY_AFTERTOUCH);
    std::cout << "name = " << name << "\n"; 
    std::cout << "num_bytes = " << (int)num_bytes << "\n";
    return 0;
}

The one caveat is that in practice, the compiler won't collapse all of this to actual constants until you build with -O2. Check it out on godbolt. You can clearly see the main function is just calls to cout, passing in constant values. If you remove the -O2, that will no longer be the case.

The advantage here is that this code is very close to what you would write in the most simplistic of scenarios. It's understandable by pretty much everyone, requires the absolute minimum of non-volatile storage, and has no restriction on event value ordering, etc.

Solution:

First we make a generic mapper to types, map_t. We do this by requiring that each type (mapped to) has a static constexpr value named key:

template <auto, auto, typename>
struct type_if_equal {};

template <auto k, typename T>
struct type_if_equal <k, k, T> : T {};

template <auto k, typename ... Ts>
struct map_t : type_if_equal<k, Ts::key, Ts>... {};

For the OP's problem, we put the data into a struct along with its associated Event as the key. Finally we wrap it into something user-friendly with using:

struct Midi {

    enum class Event : char {
        NOTE_OFF = 8,
        NOTE_ON,    // +1 till specified
        KEY_AFTERTOUCH,
        CONTROL_CHANGE,
        PROGRAM_CHANGE,
        CHANNEL_AFTERTOUCH,
        PITCH_WHEEL_CHANGE
    };
    
private:
    // D = Data (shortened for re-use in mapping)
    template <Event e, int bytes /* other data */ >
    struct D {
        constexpr static Event key = e;
        constexpr static int BytesRequired = bytes;
        /* store other data here */
    };
    
public:
    
    template <Event e>
    using Info = map_t<e,
        D<Event::NOTE_OFF, 2>,
        D<Event::NOTE_ON, 2>,
        D<Event::KEY_AFTERTOUCH, 2>,
        D<Event::CONTROL_CHANGE, 2>,
        D<Event::PROGRAM_CHANGE, 1>,
        D<Event::CHANNEL_AFTERTOUCH, 1>,
        D<Event::PITCH_WHEEL_CHANGE, 2>>;
};

Demos:

We effectively end up with a type "array" called Info which takes in any Event type and gives us the appropriate Data type (with the static data that we care about).


Generality of solution:

Some of the other answers here are much better (simpler yet still effective) for the specific example problem given. However, the OP has asked for something more generic than the example problem.

I think the idea here is that we may want to use meta-programming (MP) to deduce an event value, then to access the appropriate data we'd need something that actually takes the event in as a variable, not just a name (I think this is the functionality that the OP was interested in). We could make our MP reliant on the data collection, but this has more coupling - and what if we didn't write the MP code?

In this answer I assume that the Key type cannot be changed to make it work nicely for the mapping. I also don't assume that the keys are going to have nice ordering to make for simple mappings: for the OP we could just map array[event - 8], but this isn't a generic solution.

This is a niche solution to a niche problem. Note that I list the Event elements twice - not by necessity - but because I'm demonstrating the separation of key definitions and the mapping.


Explanation:

Intuitively an array seems like the simplest option, but I wanted to avoid generating a mapping of indices. Instead we use the compiler's native mapping. Originally my answer was like so:

template <int b /* other data */ >
struct Data {
    constexpr static int BytesRequired = b;
    /* store other data here */
};

template <Event>
struct Info {};

// Specify mappings:
template <>
struct Info <Event::NOTE_OFF> : Data<2> {};

template <>
struct Info <Event::NOTE_ON> : Data<2> {};

template <>
struct Info <Event::KEY_AFTERTOUCH> : Data<2> {};

// ...

... But I wanted to avoid the repetitive style, so I used "conditional" multi-inheritance with pack expansion which effectively generates a list like above. I first saw this wonderful trick here. It might seem strange at first, but it's common in meta-programming, and it's surprisingly efficient for the compiler (much better than recursion), and of course, has no run-time overhead.

Just write constexpr code to access that. This my very chaotic example:

#include <array>
#include <cstddef>
#include <stdexcept>
#include <iostream>

enum class MidiEvents {
   NOTE_OFF,
   NOTE_ON,
   KEY_AFTERTOUCH,
   CONTROL_CHANGE,
   PROGRAM_CHANGE,
   CHANNEL_AFTERTOUCH,
   PITCH_WHEEL_CHANGE,
   MIDIEVENTS_CNT,
};
constexpr bool operator==(const MidiEvents& a, const char& b) {
    return b == static_cast<char>(a);
}

struct MidiEventType {
    char value;
    char num_bytes; // Store the number of bytes required to be read
    constexpr bool operator==(const char& other) const {
        return value == other;        
    }
    constexpr bool operator==(const MidiEvents& other) const {
        return static_cast<char>(other) == value;
    }
};
constexpr bool operator==(const char& a, const MidiEventType& b) {
    return b == a;
}

struct MidiEventTypes {
    static constexpr std::array<
        MidiEventType, static_cast<size_t>(MidiEvents::MIDIEVENTS_CNT)
    > _data{{
        [static_cast<char>(MidiEvents::NOTE_OFF)] = {8, 2},
        [static_cast<char>(MidiEvents::NOTE_ON)] = {9, 2},
        /* etc.... */
    }};
    static constexpr auto get(char m) {
        for (auto&& i : _data) {
            if (i.value == m) {
                return i;
            }
        }
    }
    static constexpr auto get(MidiEvents m) {
        return _data[static_cast<char>(m)];
    }
    static constexpr auto GetRequiredBytesByEventType(char m) {
        return get(m).num_bytes;
    }
    static constexpr auto GetRequiredBytesByEventType(MidiEvents m) {
        return get(m).num_bytes;
    }
    static constexpr auto NOTE_OFF = _data[static_cast<char>(MidiEvents::NOTE_OFF)];
    static constexpr auto NOTE_ON = _data[static_cast<char>(MidiEvents::NOTE_ON)];
};

Wiht that:

int main() {
    // Here's some pseudo code usage:
    constexpr char nTestValue = 8;
    if (nTestValue == MidiEventTypes::NOTE_OFF) {
        std::cout << "We now need to read " << MidiEventTypes::NOTE_OFF.num_bytes << " more bytes...." << std::endl;
    }
    // We should also be able to do something like this:
    // Get the number of read bytes required for a MIDI event with a type equal to the value of nTestValue.
    constexpr char nBytesNeeded = MidiEventTypes::get(nTestValue).num_bytes; 
    // Or alternatively:
    constexpr char nBytesNeeded2 = MidiEventTypes::GetRequiredBytesByEventType(nTestValue);
    // and:
    constexpr char nBytesNeeded3 = MidiEventTypes::GetRequiredBytesByEventType(MidiEvents::NOTE_OFF);
}

it won't let me create a static unordered_map

Yes, unordered_map allocates memory and sorts stuff inside it. Just use a plain array, do not allocate memory anywhere - it's all known at compile time.

In addition to my proposed solution using templates, here is a simpler one based on the answer by Jarod42. We'll use an array and take advantage of the fact that the keys are contiguous (8->14). When looking up for a key we'll just substract 8; that way the array can hold exactly 7 elements. This approach is simpler than the templates but can only be used when the values to look up for are contiguous. Live code here

#include <iostream>
#include <array>

struct MidiEventType
{
    char value;
    char bytes;
    
    constexpr operator char() const { return value; }
};

struct MidiEventTypes
{
    static constexpr MidiEventType NOTE_OFF { 8, 2};
    static constexpr MidiEventType NOTE_ON { 9, 2};
    static constexpr MidiEventType KEY_AFTERTOUCH { 10, 2};
    static constexpr MidiEventType CONTROL_CHANGE { 11, 2};
    static constexpr MidiEventType PROGRAM_CHANGE  { 12, 1};
    static constexpr MidiEventType CHANNEL_AFTERTOUCH { 13, 1};
    static constexpr MidiEventType PITCH_WHEEL_CHANGE { 14, 2};
    
    static constexpr std::array<MidiEventType, 7> events{NOTE_OFF, NOTE_ON, KEY_AFTERTOUCH, CONTROL_CHANGE, PROGRAM_CHANGE, CHANNEL_AFTERTOUCH, PITCH_WHEEL_CHANGE};
    
    static constexpr auto get(char key)
    {
        // offset the key by 8 and then look into the array
        return events[(std::size_t)key - 8];
    }
};

int main()
{
    MidiEventTypes::get(MidiEventTypes::CONTROL_CHANGE).bytes;
    MidiEventTypes::get(MidiEventTypes::PROGRAM_CHANGE).bytes;
}

I see two viable solutions:

  1. If your data are highly inhomogeneous and hierarchical structure can be more layers deep, using JSON will work and provide plenty of flexibility, e.g. using Niels Lohmann's C++ json library. You would lost some performance and type safety, but you are quite flexible in possibilities on how to structure your data and what types would be there.

  2. If performance and type safety is more important you can use limited but much more performant code like e.g.:

#include <iostream>
#include <map>
#include <vector>

enum class Events { NOTE_OFF, PROGRAM_CHANGE };

const std::map<Events, const int> bytes_per_events = {
    {Events::NOTE_OFF, 2},
    {Events::PROGRAM_CHANGE, 1}
    // ...
};

int main()
{
    std::cout << bytes_per_events.at(Events::NOTE_OFF) << " "
              << bytes_per_events.at(Events::PROGRAM_CHANGE) << "\n";
    return 0;
}

You can use Classes instead of ints or employ different container, depending on what is required.

Related