Вступление

Что делать?

В конце концов я должен был к этому прийти. Когда-то я опубликовал статью «Я написал быструю хеш-таблицу», а потом ещё одну — «Я написал ещё более быструю хеш-таблицу». Теперь я завершил работу над самой быстрой хеш-таблицей. И под этим я подразумеваю, что реализовал самый быстрый поиск по сравнению со всеми хеш-таблицами, какие мне только удалось найти. При этом операции вставки и удаления также работают очень быстро (хотя и не быстрее конкурентов).

Я использовал хеширование по алгоритму Robin Hood с ограничением максимального количества наборов. Если элемент должен быть на расстоянии больше Х позиций от своей идеальной позиции, то увеличиваем таблицу и надеемся, что в этом случае каждый элемент сможет быть ближе к своей желаемой позиции. Похоже, такой подход действительно хорошо работает. Величина Х может быть относительно невелика, что позволяет реализовать некоторые оптимизации внутреннего цикла поиска по хеш-таблице.

Если вы хотите только попробовать её в работе, то можете скачать отсюда. Либо пролистайте вниз до раздела «Исходный код и использование». Хотите подробностей — читайте дальше.

Уже больше года, как у меня есть свой хобби-проект, в котором я разрабатываю движок базы данных для хранения временных рядов — dariadb. Задача довольно интересная — тут есть и сложные алгоритмы да и область для меня совершенно новая. За год был сделан сам движок, небольшой сервер для него и клиент. Написано все это на С++. И если клиент-сервер находится пока в достаточно сыром состоянии, то движок уже обрел некоторую стабильность.Задача хранения временных рядов достаточно распространена там, где есть хоть какие-то измерения (от SCADA-систем до мониторинга состояния серверов).

Коротко об алгоритме

Всем привет! В статье будет представлена упрощенная реализацию Stream из Java 8 на С++. Скажу сразу, что:

• в отличии от Java не используются отложенные вычисления;
• нет параллельных версий;
• местами совмещает Stream и Collectors;
• используются простые и готовые решения от STL, здесь нету чистого ФП, где только рекурсия;
• не используются техники оптимизации.

В этой версии основной упор сделан на то, чтобы быстро и просто сделать велосипед). Про ФП упомянуто по-минимуму (комбинаторам внимание не уделено :)).

Интерфейс

template <typename Type>
class Stream : private StreamImpl<Type>
{
private:
    typedef StreamImpl<Type> Parent;
public:
    using Parent::Parent; // конструкторы унаследованы
    using Parent::data;
    using Parent::isEmpty;
    using Parent::count;
    using Parent::flatMap;
    using Parent::map;
    using Parent::reduce;
    using Parent::filter;
    using Parent::allMatch;
    using Parent::noneMatch;
    using Parent::groupingBy;
    using Parent::partitionBy;
    using Parent::minElement;
    using Parent::maxElement;
    ~Stream() = default;
};

Части 1 и 2: ссылка

В первой части мы поговорили о разных стратегиях обработки ошибок и о том, когда их рекомендуется применять. В частности, я рассказал, что предусловия функций должны проверяться с помощью отладочных утверждений (debug assertions), т. е. только в режиме отладки.

Для проверки условия библиотека С предоставляет макрос assert(), но только если не определён NDEBUG. Однако, как и в случае со многими другими вещами в С, это простое, но иногда неэффективное решение. Главная проблема, с которой я столкнулся, — глобальность решения: у вас есть утверждения либо везде, либо нигде. Плохо это потому, что вы не сможете отключить утверждения в библиотеке, оставив их только в собственном коде. Поэтому многие авторы библиотек самостоятельно пишут макросы утверждений, раз за разом.

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

Чем полезны иммутабельные данные в С++?

Данная статья является доработанной текстовой версией одноименного доклада с конференции C++ CoreHard Autumn 2016, которая проходила в Минске в октябре прошлого года. Желание сделать эту статью возникло под впечатлением о том, что в мире C++ разработчики как бы делятся на два больших и не пересекающихся лагеря. В первом лагере находятся матерые спецы, которые все видели, все знают и все умеют, за плечами у которых десятки собственноручно написанных реализаций Модели Акторов, внутрях у которых хитрые, конечно же самостоятельно сделанные, lock-free очереди и state-of-the-art механизмы обслуживания сообщений. Такие проффи сами часами могут рассказывать про тонкости многопоточного программирования (только почему-то редко это делают). Во втором лагере — зеленые новички, которых волею судьбы занесло в мир C++, которые пока слабо представляют себе различия между unique_ptr и shared_ptr, про шаблоны только слышали, а в области многопоточности имеют поверхностное впечатление только о std::thread, std::mutex и, может быть, std::condition_variable. Для людей из первого лагеря я вряд ли что-нибудь интересное расскажу, а вот разработчикам из второго лагеря попробую вкратце рассказать о том, что Модель Акторов в C++ — это нормально. И что есть ряд готовых инструментов, на примере которых можно увидеть, что же это такое.

Вместо КДПВ — короткая драма для привлечения внимания, основанная на реальных событиях. Ее можно смело пропустить и перейти к статье, которая поможет вам разобраться в rvalue-ссылках, конструкторах перемещения, универсальных ссылках, идеальной передаче (perfect forwarding) и т. д.

Драма в трех действиях

Действие первое

Компилятор. Локальный объект x типа T, проживающий на стеке, вы приговариваетесь к изъятию у вас всего имущества в связи с тем, что не будете пользоваться им до конца своей жизни.

Объект x. Что? Я не какой-то там временный объект, у меня постоянная регистрация, вы не имеете права!

Компилятор. Никто вас не выселяет. Но согласно одиннадцатой редакции стандартного кодекса, все ваши вещи будут переданы другому объекту, которому они нужны больше.

Объект x. И как вы это сделаете? Все мои данные надежно инкапсулированы, я не позволю никому бесцеремонно обращаться с ними. Если уж они так вам нужны, то пусть приходит конструктор копирования со своей флешкой, я ему скопирую.

Привет, Хабр! Об иммутабельных данных немало говориться, но о реализации на С++ найти что-то сложно. И, потому, решил данный восполнить пробел в дебютной статье. Тем более, что в языке D есть, а в С++ – нет. Будет много кода и много букв.

О стиле – служебные классы и метафункции используют имена в стиле STL и boost, пользовательские классы в стиле Qt, с которой я в основном и работаю.

Введение

Что из себя представляют иммутабельные данные? Иммутабельные данные – это наш старый знакомый const, только более строгий. В идеале иммутабельность означает контекстно-независиую неизменяемость ни при каких условиях.

По сути иммутабельные данные должны:

• обеспечивать физическую и логическую константность;
• запрещать присваивание нового значения на этапе компиляции;
  все операции должны проводиться над копией, а не над оригиналом.

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

Как можно реализовать иммутабельные данные в С++?
В С++ у нас есть (сильно упрощенно):

• значения – объекты фундаментальных типов, экземпляры классов (структур, объединений), перечислений;
• указатели;
  ссылки;
  массивы.

Функции и void не имеет смысл делать иммутабельными. Ссылки тоже не будем делать иммутабельными, для этого есть const reference_wrapper.