Быстрый доступ к map по ключу строке

В статье «String enum — строковые enum» я писал о том как связывать текстовые представления с enum class — метод хороший но только если все элементы заранее известны, но зачастую бывает что строки являются некими идентификаторами и конечно же заранее не известны, а зачастую будут добавляться позднее и причем без пересборки программы.

Требования к библиотеке все теже:

• Кроссплатформенность;
• Минимум зависимостей;
• Скорость чтения;
• Простой синтаксис;

Пример конфига

{
    "objects":
    [
        {
            "id": "object1",
            "events":
            {
                "event1":{
                    "give": {"object2": 4}
                },
            }
        },
        {
            "id": "object2",
            "events":
            {
                "event2":{
                    "give": {"object1": 3}
                },
            },
            {
            "id": "object3",
            "events":
            {
                "event3":{
                    "give": {"object3": 4}
                },
            }
        },

Первая и самая простая идея которая напрашивается это:

    std::map<std::string,script> events;

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

Вторая идея парсить этот конфиг в 2 прохода тогда на 2-м проходе object1, object2, object3 будут уже известны и можно будет записать на них прямо указатели или ссылки. Но если зависимости еще более сложные то такой подход может и не сработать.

Я предлагаю способ позволяющий существенно сократить runtime издержки подобных конструкций

Основная идея в том чтобы каждая строка вычитываемая из конфига поподала в некую структуру а назад мы бы получали ее уникальный номер.
Для начала позаботимся о типобезопасности.

template <class T, class ValueType>
class StrongType
{
public:
    inline explicit operator ValueType() const { return _value;}
    inline bool operator == (const StrongType &other) const
    {
        return _value == other._value;
    }
    inline bool operator != (const StrongType &other) const
    {
        return _value != other._value;
    }
    inline bool operator < (const StrongType &other) const
    {
        return _value < other._value;;
    }
    inline bool operator > (const StrongType &other) const
    {
        return _value > other._value;
    }
    inline bool operator <= (const StrongType &other) const
    {
        return _value <= other._value;
    }
    inline bool operator >= (const StrongType &other) const
    {
        return _value >= other._value;
    }
    
protected:
    explicit StrongType(ValueType value):_value(value) {}
    
private:
    ValueType _value;
};

Идея не нова код подсмотрен в boost но как я уже писал, минимум зависимостей.

далее самое интересное

template <class T, class ValueType = int>
class StringCache
{
public:
    static_assert(std::is_integral<ValueType>::value, "not integral type");
    
    class Type: public StrongType<T,ValueType>
    {
        friend class StringCache;
    public:
        explicit Type(const std::string &value):StrongType<T,ValueType>(StringCache::get(value)){}
    private:
        explicit Type(ValueType value):StrongType<T,ValueType>(value){}
    };
    
    static Type get(const std::string &value)
    {
        return Type(_values.insert(std::make_pair(value, _values.size() + 1)).first->second);
    }
    
    static Type find(const std::string &value)
    {
        std::map<std::string,int>::const_iterator it =_values.find(value);
        if(it == _values.end())
            return Type(0);
        else
            return Type(it->second);
    }
    
    static const std::string& to_string(const Type &type)
    {
        static const std::string empty;
        if(static_cast<ValueType>(type)>=_values.size())
            return empty;
        for(const auto &it:_values)
            if(it.second == static_cast<ValueType>(type))
                return it.first;
        return empty;
    }
    
private:
    static std::map<std::string,int> _values;
};

template <class T, class ValueType>
std::map<std::string,int> StringCache<T,ValueType>::_values;

идея проста есть такая строка отдаем ее индекс нету создаем новый
+ ф-я поиска индекса без создания нового
ну и наконец ф-я для преобразования обратно в строку — она медленная и подходит только для логирования или подобных операций.

Ну и наконец несколько примеров использования вместе с оценами производительности http://ideone.com/JBHaBM

P.S. Да в большинстве реальных задач значение для поиска либо берется из других переменных либо можно заранее подготовить.

class EventId:public StringCache<EventId:public>{};
if(something)
{
    static EventId:Type event1Val = EventId:public::find("event1");
    map.find(event1Val);
}

P.P.S этот код в отличие от прошлой статьи в реальных приложениях пока не использовался это концепт, поэтому критика и рац-предложения приветствуются особо.

Автор: newnon

Источник