​​Как использовать std::unordered_map с ключом в виде std::pair?
#опытным

При работе над задачами C++ часто необходимо использовать сложные ключи в контейнерах на основе хэша - std::unordered_map. Распространенным подходом является использование std::pair<int, int> в качестве типа ключа. Однако попытка объявить unordered_map следующим образом:

std::unordered_map<std::pair<int, int>, int> map;

приводит к подобной ошибке компиляции:

error: call to implicitly-deleted default constructor of  
'unordered_map<std::pair<int, int>, int>'

Происходит это, потому что для std::pair не определена хэш-функция. Она нужна для превращения значение объекта-ключа в число, которое используется для индексации элемента в хэш-таблице.

STL предоставляет нам хэш-функции для тривиальных типов данных и, например, std::string.

Но для сложных шаблонных типов непонятно в общем случае, как реализовать хэш-функцию. Поэтому эту задачу и возложили на самих программистов. Нужно самим определять хэш-функцию для объекта так, как того требует конкретная задача.

Ну хорошо. Определять надо. Но как это сделать? В азбуке не написано, как написать хэш для пары...

Давайте по порядку. Самый тривиальный подход - просто ксорим два хэша типов пары(в предположении, что они уже есть):

namespace std {
    template <typename T1, typename T2>
    struct hash<pair<T1, T2>> {
        size_t operator()(const pair<T1, T2>& p) const {
            size_t h1 = hash<T1>{}(p.first);
            size_t h2 = hash<T2>{}(p.second);
            return h1 ^ h2;
        }
    };
}

std::unordered_map<std::pair<int, std::string>, double> map;
map[{42, "foo"}] = 3.14;

Отлично, заработало! Или нет?

Это компилируется, но есть проблема с коллизиями. Если ключом будет std::pair<int, int>, то для двух разных ключей {1, 2} и {2, 1} будут одинаковые хэши. Не очень хорошо.

Сделаем ход конем:

namespace std {
    template <typename T1, typename T2>
    struct hash<pair<T1, T2>> {
        size_t operator()(const pair<T1, T2>& p) const {
            size_t h1 = hash<T1>{}(p.first);
            size_t h2 = hash<T2>{}(p.second);
            return h1 ^ (h2 << 1);
        }
    };
}

std::unordered_map<std::pair<int, int, double> map;

Побитово сдвинем второй хэш на один бит влево. Так мы не сильно ухудшим распределение(всего один бит заменим на нолик), но уберем коллизии.

Но это конечно все на коленке сделаный велосипед и можно найти антипримеры. В бусте есть функция hash_combine, которая делает ровно то, что мы хотим:

namespace std {
    template <typename T1, typename T2>
    struct hash<std::pair<T1, T2>> {
        size_t operator()(const std::pair<T1, T2>& p) const {
            size_t seed = 0;
            boost::hash_combine(seed, p.first);
            boost::hash_combine(seed, p.second);
            return seed;
        }
    };
}

Если хочется узнать, что там у этой штуки под капотом, что в сущности код выше будет эквивалентен следующему коду:

namespace std {
    template <typename T1, typename T2>
    struct hash<pair<T1, T2>> {
        size_t operator()(const pair<T1, T2>& p) const {
            size_t h1 = hash<T1>{}(p.first);
            size_t h2 = hash<T2>{}(p.second);
            return h1 ^ (h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2));
        }
    };
}

Магические числа во всей красе. Но это нормально, когда мы имеем дело с математикой: генераторы случайных чисел, шифрование, хэш-функции.

Кстати, естественно, что такой подход можно использовать и для кастомных структур, и для туплов. В общем, можно пользоваться. Хотите тяните буст, хотите сами пишите, там все равно не так сложно.

Use ready-made solutions. Stay cool.

#cppcore #STL #template

​​Методы, определенные внутри класса
#новичкам

Вы хотите написать header-only библиотеку логирования и собственно пишите:

// logger.hpp
namespace SimpleLogger {

enum class Level { Debug, Info, Warning, Error };

class Logger {
public:
    Logger(const Logger &) = delete;
    Logger &operator=(const Logger &) = delete;

    static Logger &GetInstance() {
        static Logger instance;
        return instance;
    }

    void SetMinLevel(Level level) {
        m_minLevel = level;
    }

    void Log(Level level, const std::string &message) {
        if (level < m_minLevel)
            return;
        auto time = std::chrono::system_clock::to_time_t(std::chrono::system_clock::now());
        std::lock_guard lock{m_mutex};
        std::cout << "[" << std::put_time(std::localtime(&time), "%Y-%m-%d %H:%M:%S") << "] " << "["
                  << levelToString(level) << "] " << message << std::endl;
    }

private:
    Logger() : m_minLevel(Level::Info) { Log(Level::Info, "Logger initialized"); }

    Level m_minLevel;
    std::mutex m_mutex;

    std::string levelToString(Level level) {
        switch (level) {
        case Level::Debug: return "DEBUG";
        case Level::Info: return "INFO";
        case Level::Warning: return "WARN";
        case Level::Error: return "ERROR";
        default: return "UNKNOWN";
        }
    }
};

}  // namespace SimpleLogger

Ваши пользователи вызывают из одной единицы трансляции метод Log:

...
#include <logger.hpp>
...
using namespace SimpleLogger;
Logger::GetInstance().Log(Level::Info, "Select recent items");
db->Execute("Select bla bla");
...

И из второй:

...
#include <logger.hpp>
...
using namespace SimpleLogger;
if (!result) {
  Logger::GetInstance().Log(Level::ERROR, "Result is empty");
  throw std::runtime_error("Result is empty");
}
...

А потом это все успешно линкуется в один бинарник. Как так? Должно же было сработать One Definition Rule, которое запрещает иметь более одного определения функции на всю программу? А у нас как раз все единицы трансляции видят определение метода Log.

Дело в том, что все методы, определенные внутри тела класса, неявно помечены как inline. Это не значит, что компилятор встроит код этих методов в вызывающий код. Это значит, что для таких методов разрешается иметь сколько угодно одинаковых определений внутри программы. На этапе линковки выберется одна любая реализация и везде, где будет нужен адрес метода для вызова будет подставляться адрес именно этой реализации.

Так что явно использовать ключевое слово inline в этом случае бессмысленно.

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

Каждая единица трансляции должна сгенерировать свой код для inline метода. Это значит, что обильное использование inline методов может привести к увеличенному времени компиляции.

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

Противоречивые последствия. Либо быстрый рантайм и медленный компайл-тайм, либо наоборот. Как быть?

Обычно inline делают простые и короткие методы, типа сеттеров и геттеров, а длинные методы, которые менее вероятно будут встраиваться, выносят в цпп. Короткие функции сильнее всего страдают от оверхеда на вызов, который может быть сравним с временем выполнения самой функции. Но они не засоряют собой интерфейс класса, хэдэр также легко и быстро читается. Вот такой компромисс.

Look for a compromise. Stay cool.

#cppcore #goodpractice