Boost.MultiIndex

-
    Boost.MultiIndex позволяет определять контейнеры, поддерживающие произвольное количество интерфейсов. В то время как std::vector предоставляет интерфейс, который поддерживает прямой доступ к элементам с индексом, а std::set предоставляет интерфейс, который сортирует элементы, Boost.MultiIndex позволяет вам определять контейнеры, которые поддерживают оба интерфейса. Такой контейнер можно использовать для доступа к элементам с использованием индекса и отсортированным способом.           Boost.MultiIndex можно использовать, если к элементам нужно обращаться по-разному и, как правило, необходимо хранить в нескольких контейнерах. Вместо того, чтобы хранить элементы как в векторе, так и в наборе, а затем непрерывно синхронизировать контейнеры, вы можете определить контейнер с Boost.MultiIndex, который обеспечивает векторный интерфейс и заданный интерфейс.       Boost.MultiIndex также имеет смысл, если вам нужно получить доступ к элементам, основанным на нескольких разных свойствах. В примере 12.1 происходит поиск по имени и по числу ног. Без Boost.MultiIndex потребуется два контейнера для хэшей - один для поиска животных по имени, а другой для поиска их по количеству ног.

Пример 12.1. Использование boost::multi_index::multi_index_container

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/member.hpp>
#include <string>
#include <iostream>
using namespace boost::multi_index;struct animal
{
  std::string name;
  int legs;
};typedef multi_index_container<
  animal,
  indexed_by<
    hashed_non_unique<
      member<
        animal, std::string, &animal::name
      >
    >,
    hashed_non_unique<
      member<
        animal, int, &animal::legs
      >
    >
  >
> animal_multi;int main(){
  animal_multi animals;

  animals.insert({"cat", 4});
  animals.insert({"shark", 0});
  animals.insert({"spider", 8});

  std::cout << animals.count("cat") << '\n';

  const animal_multi::nth_index<1>::type &legs_index = animals.get<1>();
  std::cout << legs_index.count(8) << '\n';
}

      Когда вы используете Boost.MultiIndex, первым шагом является определение нового контейнера. Вы должны решить, какие интерфейсы должен поддерживать ваш новый контейнер и какие свойства элемента он должен получить.Класс boost::multi_index::multi_index_container, который определен в boost/ multi_index_container.hpp, используется для каждого определения контейнера. Это шаблон класса, для которого требуется не менее двух параметров. Первым параметром является тип элементов, которые должен хранить контейнер. В примере 12.1 это пользовательский класс, называемый animal. Второй параметр используется для обозначения различных индексов, которые должен предоставить контейнер.       Ключевым преимуществом контейнеров на основе Boost.MultiIndex является то, что вы можете обращаться к элементам через разные интерфейсы. Когда вы определяете новый контейнер, вы можете указать количество и тип интерфейсов. Контейнер в примере 12.1 должен поддерживать поиск животных по имени или количеству ног, поэтому определены два интерфейса. Boost.MultiIndex вызывает эти интерфейсные индексы - откуда берет начало имя библиотеки.

       Интерфейсы определяются с помощью класса boost::multi_index::indexed_by. Каждый интерфейс передается как параметр шаблона. В примере 12.1 используются два интерфейса типа boost::multi_index::hashed_non_unique, который определен в boost/multi_index/hashed_index.hpp. Использование этих интерфейсов приводит к тому, что контейнер ведет себя как std::unordered_set и ищет значения, используя значение хэша.     Класс boost::multi_index::hashed_non_unique также является шаблоном и ожидает в качестве единственного параметра класса, который вычисляет значения хэша. Поскольку оба интерфейса контейнера должны искать животных, один интерфейс вычисляет хеш-значения для имени, в то время как другой интерфейс делает это для количества ног.       Boost.MultiIndex предлагает шаблон вспомогательного класса boost::multi_index:: member, который определен в boost/multi_index/member.hpp для доступа к переменной-члену. Как видно из примера 12.1, было указано несколько параметров, чтобы позволить boost::multi_index::member знать, к какой переменной-члену животного следует обращаться, а также к типу переменной-члена.

      Хотя определение animal_multi сначала выглядит сложным, класс работает как карта. Название и количество ног животного можно рассматривать как пару ключ/ значение. Преимущество контейнера animal_multi над картой типа std:: unordered_map заключается в том, что животных можно искать по имени или по количеству ног. animal_multi поддерживает два интерфейса, один на основе имени и один, основанный на числе ног. Интерфейс определяет, какая переменная-член является ключом, и какая переменная-член является значением. Чтобы получить доступ к контейнеру MultiIndex, вам необходимо выбрать интерфейс.

      Если вы напрямую обращаетесь к объектным животным с помощью insert() или count(), используется первый интерфейс. В примере 12.1 это хэш-контейнер для имени переменной-члена. Если вам нужен другой интерфейс, вы должны явно его выбрать.
Интерфейсы нумеруются последовательно, начиная с индекса 0 для первого интерфейса. Чтобы получить доступ ко второму интерфейсу, как показано в примере 12.1, вызовите функцию-член get() и передайте индекс нужного интерфейса в качестве параметра шаблона.Возвращаемое значение get() выглядит сложным. Он обращается к классу контейнера MultiIndex с именем nth_index, который, опять же, является шаблоном. Индекс используемого интерфейса должен быть указан как параметр шаблона. Этот индекс должен быть таким же, как тот, который передан get(). Последний шаг - получить доступ к типу определения типа nth_index. Значение типа представляет тип соответствующего интерфейса. Следующие примеры используют ключевое слово auto для упрощения кода.     Хотя вам не нужно знать специфику интерфейса, так как они автоматически выводятся из nth_index и типа, вы все равно должны понимать, к какому интерфейсу обращаются. Так как интерфейсы последовательно нумеруются в определении контейнера, на это можно легко ответить, поскольку индекс передается как get(), так и nth_index. Таким образом, legs_index - это хэш-интерфейс, который смотрит на животных ногами.

    Поскольку данные, такие как имена и ноги, могут быть ключами контейнера MultiIndex, их нельзя произвольно изменить. Если количество ног изменено после того, как животное было просмотрено по имени, интерфейс, использующий ноги в качестве ключа, не будет знать об изменениях и не будет знать, что нужно вычислить новое значение хэш-функции.      Так же, как ключи в контейнере типа std::unordered_map не могут быть изменены, ни данные, хранящиеся в контейнере MultiIndex, не могут быть изменены. Строго говоря, все данные, хранящиеся в контейнере MultiIndex, постоянны. Сюда входят переменные-члены, которые не используются каким-либо интерфейсом. Даже если интерфейс не обращается к ногам, ножки не могут быть изменены.


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


Пример 12.2. Изменение элементов в контейнере MultiIndex при помощи modify()



#include <boost/multi_index_container.hpp>

#include <boost/multi_index/hashed_index.hpp>

#include <boost/multi_index/member.hpp>

#include <string>

#include <iostream>



using namespace boost::multi_index;



struct animal
{

std::string name;

int legs;

};



typedef multi_index_container<

animal,

indexed_by<

hashed_non_unique<

member<

animal, std::string, &animal::name

>

>,

hashed_non_unique<

member<

animal, int, &animal::legs

>

>

>

> animal_multi;



int main(){

animal_multi animals;



animals.insert({"cat", 4});

animals.insert({"shark", 0});

animals.insert({"spider", 8});



auto &legs_index = animals.get<1>();

auto it = legs_index.find(4);

legs_index.modify(it, [](animal &a){ a.name = "dog"; });



std::cout << animals.count("dog") << '\n';

}












        Каждый интерфейс, предлагаемый Boost.MultiIndex, предоставляет функцию modify(), которая работает непосредственно на контейнере. Объект, который нужно изменить, идентифицируется через итератор, переданный в качестве первого параметра для modify(). Второй параметр - объект функции или функции, который в качестве единственного параметра ожидает объект типа, хранящегося в контейнере. Объект функции или функция могут изменять элемент столько, сколько необходимо. В примере 12.2 показано, как использовать функцию modify () для изменения элемента.





      До сих пор был введен только один интерфейс: boost::multi_index:: hashed_non_unique, который вычисляет значение хэша, которое не должно быть уникальным. Чтобы гарантировать, что значение не сохраняется дважды, используйте boost::multi_index::hashed_unique. Обратите внимание, что значения не могут быть сохранены, если они не удовлетворяют требованиям всех интерфейсов конкретного контейнера. Если один интерфейс не позволяет хранить значения несколько раз, не имеет значения, разрешает ли другой интерфейс.










Пример 12.3. MultiIndex контейнер с boost::multi_index::hashed_unique







#include <boost/multi_index_container.hpp>

#include <boost/multi_index/hashed_index.hpp>

#include <boost/multi_index/member.hpp>

#include <string>

#include <iostream>



using namespace boost::multi_index;



struct animal
{

std::string name;

int legs;

};



typedef multi_index_container<

animal,

indexed_by<

hashed_non_unique<

member<

animal, std::string, &animal::name

>

>,

hashed_unique<

member<

animal, int, &animal::legs

>

>

>

> animal_multi;



int main(){

animal_multi animals;



animals.insert({"cat", 4});

animals.insert({"shark", 0});

animals.insert({"dog", 4});



auto &legs_index = animals.get<1>();

std::cout << legs_index.count(4) << '\n';

}








     Контейнер в примере 12.3 использует boost::multi_index::hashed_unique в качестве второго интерфейса. Это означает, что в контейнере не могут храниться два животных с одинаковым количеством ног, потому что хеш-значения будут одинаковыми.

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










Пример 12.4. Интерфейсы sequenced, ordered_non_unique и random_access





#include <boost/multi_index_container.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/random_access_index.hpp>
#include <boost/multi_index/member.hpp>
#include <string>
#include <iostream>

using namespace boost::multi_index;

struct animal
{
  std::string name;
  int legs;
};

typedef multi_index_container<
  animal,
  indexed_by<
    sequenced<>,
    ordered_non_unique<
      member<
        animal, int, &animal::legs
      >
    >,
    random_access<>
  >
> animal_multi;

int main(){
  animal_multi animals;

  animals.push_back({"cat", 4});
  animals.push_back({"shark", 0});
  animals.push_back({"spider", 8});

  auto &legs_index = animals.get<1>();
  auto it = legs_index.lower_bound(4);
  auto end = legs_index.upper_bound(8);
  for (; it != end; ++it)
    std::cout << it->name << '\n';

  const auto &rand_index = animals.get<2>();
  std::cout << rand_index[0].name << '\n';
}





       В примере 12.4 представлены последние три интерфейса Boost.MultiIndex: boost:: multi_index::sequenced, boost::multi_index::ordered_non_unique и boost::multi_index:: random_access.Интерфейс boost::multi_index::sequenced позволяет обрабатывать контейнер MultiIndex, как список типов std::list. Элементы сохраняются в заданном порядке.С помощью интерфейса boost::multi_index::rdered_non_unique объекты автоматически сортируются. Этот интерфейс требует, чтобы вы определяли критерий сортировки при определении контейнера. Пример 12.4 сортирует объекты типа animal по количеству ног, используя вспомогательный класс boost::multi_index::member.boost::multi_index::ordered_non_unique предоставляет специальные функции-члены для поиска определенных диапазонов в отсортированных значениях. Используя функции lower_bound() и upper_bound(), программа ищет животных, у которых есть как минимум четыре и не более восьми ног. Поскольку они требуют сортировки элементов, эти функции-члены не предоставляются другими интерфейсами.     Введенный интерфейс - boost::multi_index::random_access, который позволяет обрабатывать контейнер MultiIndex как вектор типа std::vector. Двумя наиболее важными функциями-членами являются operator[] и at().



boost::multi_index::random_access включает boost::multi_index::sequenced. С boost:: multi_index::random_access доступны все функции-члены boost::multi_index:: sequenced.



       В оставшейся части этой главы рассматриваются key экстракторы. Один из key экстракторов уже введен: boost::multi_index::member, который определен в boost/ multi_index/member.hpp. Этот вспомогательный класс называется экстрактором ключей, поскольку он позволяет указать, какая переменная-член класса должна использоваться как ключ интерфейса.



         



Пример 12.5. Экстракторы ключей identity и const_mem_fun






#include <boost/multi_index_container.hpp>

#include <boost/multi_index/ordered_index.hpp>

#include <boost/multi_index/hashed_index.hpp>

#include <boost/multi_index/identity.hpp>

#include <boost/multi_index/mem_fun.hpp>

#include <string>

#include <utility>

#include <iostream>



using namespace boost::multi_index;



class animal
{

public:

animal(std::string name, int legs) : name_{std::move(name)},

legs_(legs) {}

bool operator<(const animal &a) const { return legs_ < a.legs_; }

const std::string &name() const { return name_; }

private:

std::string name_;

int legs_;

};



typedef multi_index_container<

animal,

indexed_by<

ordered_unique<

identity<animal>

>,

hashed_unique<

const_mem_fun<

animal, const std::string&, &animal::name

>

>

>

> animal_multi;



int main(){

animal_multi animals;



animals.emplace("cat", 4);

animals.emplace("shark", 0);

animals.emplace("spider", 8);



std::cout << animals.begin()->name() << '\n';



const auto &name_index = animals.get<1>();

std::cout << name_index.count("shark") << '\n';

}










      Идентификатор ключа boost::multi_index::identity, определенный в boost/multi_index/ identity.hpp, использует элементы, хранящиеся в контейнере в качестве ключей. Это требует, чтобы класс animal мог быть сортируемым, потому что объекты типа animal будут использоваться в качестве ключа для интерфейса boost::multi_index:: ordered_unique. В примере 12.5 это достигается с помощью перегруженного оператора <.    В файле заголовка заголовка boost/multi_index/mem_fun.hpp определяются два ключевых экстрактора - boost::multi_index::const_mem_fun и boost::multi_index:: mem_fun - которые используют возвращаемое значение функции-члена в качестве ключа. В примере 12.5 возвращаемое значение name() используется таким образом. boost::multi_index::const_mem_fun используется для постоянных функций-членов, а boost::multi_index::mem_fun используется для непостоянных функций-членов.Boost.MultiIndex предлагает еще два ключевых экстрактора: boost::multi_index:: global_fun и boost::multi_index::composite_key. Первый может использоваться для автономных или статических функций-членов, а последний позволяет вам разработать ключевой экстрактор, состоящий из нескольких других экстракторов ключей.


Популярные сообщения из этого блога

Аппроксимация функций рядом Тейлора

-
Изображение
Ряды Тейлора помогают аппроксимировать функции с помощью ряда  полиномов  .  Другими словами, вы создаете функцию с множеством других меньших функций.  В качестве простого примера вы можете создать число 10 из меньших чисел: 1 + 2 + 3 + 4. Таким же образом вы можете объединить простые многочлены для создания более сложной функции. Зачем вам это делать?  1.  Во многих случаях вы знаете, как выглядит функция на графике; но вы не знаете этого уравнения. 2. Если сложную функцию представить как суперпозицию простых (то есть разложить в ряд), - то поведение сложной функции можно будет предсказать по анализу поведения простых. 3. Используя лишь стандартные операции сложения, умножения, вычитания, деления находит с заданной точностью результат. Точность зависит от того, сколько членов ряда взято в расчет. 4. Так как вычисления приближенные, то это уменьшает общее время расчета. Все зависит от заданной точности. Ряд Тейлора Многочле...
Далее...

Основные структуры данных: Множества

-
Изображение
Множество (set) — это структура данных, представляющая собой не организованный набор уникальных элементов одного типа. Данная структура  очень тесно связано с математическим понятием теории множеств. В наиболее упрощенном понимании, множество — это набор уникальных однотипных данных, рассматриваемых как единое целое. Давайте рассмотрим пример реализации множества и основных операций выполняемых с множествами на языке C#. На рисунке ниже схематически представлены два множества A и B, а также основные операции: объединение, пересечение, разность. Set Давайте подробнее рассмотрим все наиболее часто встречающиеся операции над множествами:                       Add — добавление элемента. Если такой элемент уже присутствует, то он не будет добавлен. Remove — удаление элемента из множества. Union — объединение множеств. Создается новое множество, включающее в себя все элементы из множества А и множества В. Если эле...
Далее...

Doxygen, оформление документации

-
Изображение
Настройка внешнего вида документации Сначала рассмотрим то, какой функционал предоставляет Doxygen для настройки оформления (при этом следует обратить внимание на то, что в основном описываемые далее настройки относятся именно к генерируемому HTML документу). Вообще, этот раздел подробно описан в официальной документации, отмечу лишь основные детали в нём и разбавлю его для ясности примерами. Настройки оформления Иконка для проекта Самое простое, что можно настроить в оформлении – это иконку проекта. Для этого необходимо указать в файле настроек в опции PROJECT_LOGO путь к иконке: PROJECT_LOGO = <путь_к_иконке> Цветовая схема Для того, чтобы просто изменить цветовую схему HTML страницы используются следующие опции в файле настроек: Опция      Значение HTML_COLORSTYLE_HUE    Указывает тон цветовой схемы HTML_COLORSTYLE_SAT    Указывает яркость цветовой схемы HTML_COLORSTYLE_GAMMA    Указывает гамму цве...
Далее...