O Boost Multi-index Containers

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

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

Конечно всё уже придуманно до нас и в библиотеке Boost уже есть модуль для решения данных проблем — boost::multi_index. Огромное преимущество — скорость, multi_index очень быстрый. Однако документация этого модуля скажем сложна для понимания и новички стараются обходить этот модуль стороной. И конечно отдельно можно сказать о сообщениях компилятора при ошибках при работе с multi_index_container — разобрать длинные сообщение о шаблонах не каждому под силу.

Постараемся ликвидировать этот пробел и показать простые примеры для горячего старта и использования этого мощного инструмента. Буду пользовать немного вместе с Qt в примерах. (Как раз в Qt с их собственной системой шаблонов мне часто не хватает примитива сравнимого с multi_index)

Допустим у нас есть небольшая структурка с полями:

struct Rec { QString name, phone, addr; };

multi_index даёт очень удобную возможность использования тэгов/(метки в рус доке) для ключей.
Определим их прямо в Rec чтобы не расползались по коду:

struct Rec {
	QString name, phone, addr;
	struct ByName {}; struct ByPhone {}; struct ByAddr {};
};

Мы можем создать следующий массив:

typedef boost::multi_index_container<Rec,
	indexed_by<
		ordered_unique<
			tag<Rec::ByName>, member<Rec,QString,&Rec::name>
		>,
		ordered_non_unique<
			tag<Rec::ByPhone>, member<Rec,QString,&Rec::phone>
		>,
		ordered_non_unique<
			tag<Rec::ByAddr>, member<Rec,QString,&Rec::addr>
		>
	>
> Store;

Мы принимаем что записи у нас уникальны по имени(name), но неуникальны по адресу и телефону. Уникальность по имени также в том что мы не сможем добавить в массив две записи с одним и тем же именем.

{
	Store store;
	Rec r1 = { "Basilio Pupkinio", "022", "Neron st" };
	qDebug() << "ok1" << store.insert(r1).second; // ok1 true
	qDebug() << "ok2" << store.insert(r1).second; // ok2 false
}

Для меня это важное удобство что сам массив не допустит появления дубликатов и при доступе к нему я могу полагаться на правильность содержимого a priori.

Найдём запись по имени:

{
	QString find_id = "Basilio Pupkinio";
	typedef Store::index<Rec::ByName>::type List;
	const List & ls = store.get<Rec::ByName>();
	List::const_iterator it = ls.find(find_id);
	if ( it != ls.end() ) {
		qDebug() << (*it).addr; // "Neron st"
	}
}

Если у нас несколько записей с телефоном 022

{
	Store store;
	Rec r1 = { "Basilio Pupkinio", "022", "Pushkina st" };
	Rec r2 = { "Vasya Pupkin",     "022", "Around st" };
	store.insert(r1)
	store.insert(r2)
}

Тогда найти все записи с телефоном 022

{
	QString find_phone = "022";
	Store::index<Rec::ByPhone>::type::iterator it0, it1;
	tie(it0,it1) = store.get<Rec::ByPhone>().equal_range(find_phone);
	while(it0 != it1) { qDebug() << (*it0).name; ++it0; }
}

Что если нам интересен поиск по комбинации телефона и адреса?
Мы можем добавить композитный индекс в наш массив таким блоком:

		ordered_non_unique<
			tag<Rec::ByKey>, composite_key<
				Rec,
				member<Rec,QString,&Rec::phone>,
				member<Rec,QString,&Rec::addr>
			>
		>,

(Плюс не забываем добавить метку struct ByKey {}; )

{
	Rec r1  = { "Basilio Pupkinio", "022", "Pushkina st" };
	Rec r2  = { "Vasya Pupkin",     "022", "Around st" };
	Rec r3  = { "Vasilisa Pupkina", "022", "Around st" };
	store.insert(r1);
	store.insert(r2);
	store.insert(r3);
	{
		QString find_phone = "022";
		QString find_addr = "Around st";
		Store::index<Rec::ByKey>::type::iterator it0, it1;
		tie(it0,it1) = store.get<Rec::ByKey>().equal_range(make_tuple(find_phone, find_addr));
		while(it0 != it1) { qDebug() << (*it0).name; ++it0; }
	}
}

Опять же понимаем что для композитных ключей мы можем пользовать как и ordered_non_unique так и ordered_unique.
Таим способом очень удобно накладывать некоторые дополнительные условия на содержимое дозволенных ключей и их комбинаций — сам масив не даст нам добавить «неправильные» объекты.
Если мы хотим возможность иметь доступ в массив одновременно как к вектору мы можем легко добавить random_access:

typedef boost::multi_index_container<Rec,
	indexed_by<
		random_access<>,		
		ordered_unique<
			tag<Rec::ByName>, member<Rec,QString,&Rec::name>
		>,
		ordered_non_unique<
			tag<Rec::ByPhone>, member<Rec,QString,&Rec::phone>
		>
	>
> Store;

Тогда у нас есть возможность доступа как store[0] итд, push_back().
Если мы хотим использовать массив как хеш чтобы иметь быстрый доступ по ключу О(1), но медленнее O(log(n)) по insert/remove то мы можем пользовать hashed_unique/hashed_non_unique вместо ordered_unique/ordered_non_uniue:

typedef boost::multi_index_container<Rec,
	indexed_by<
		hashed_non_unique<
			tag<Rec::ByName>, member<Rec,QString,&Rec::name>
		>,
		ordered_non_unique<
			tag<Rec::ByPhone>, member<Rec,QString,&Rec::phone>
		>
	>
> Store;
std::size_t hash_value(QString x) { return qHash(x); }

Также можно использовать hashed_uniqie/hashed_non_unique и для композитных ключей.

О модификации записей.
Так как поля объектов должны быть синхронизированными с индексами массива нельзя просто изменить только поле у объекта. Допустим у нас есть необходимость изменить телефон для одной из записей. Чтобы наши ключи были синхронизированными с объектами это изменение должно быть сделано через функтор:

struct Rec {
	QString name, phone, addr;
	struct ByName {};
	struct ByPhone {};
	struct ByAddr {};
	struct PhoneChange : public std::unary_function<Rec,void> {
		QString p; PhoneChange(const QString &_p) : p(_p) {}
		void operator()(Rec & r) { r.phone = p; }
	};
}; 

Мы можем сделать поиск в масиве по имени, получить итератор по имени, с помощью project() перевести его в итератор по телефону и провести модификацию объекта и массива через функтор:

{
	Store store;
	Rec r1  = { "Basilio Pupkinio", "021", "Around st" };
	Rec r2  = { "Vasya Pupkin",     "022", "Around st" };
	Rec r3  = { "Vasilisa Pupkina", "022", "Around st" };
	store.insert(r1);
	store.insert(r2);
	store.insert(r3);

	QString find_id = "Basilio Pupkinio";
	typedef Store::index<Rec::ByName>::type NList;
	typedef Store::index<Rec::ByPhone>::type PList;
	NList & ns = store.get<Rec::ByName>();
	PList & ps = store.get<Rec::ByPhone>();
	NList::const_iterator nit = ns.find(find_id);
	if ( nit != ns.end() ) {
		PList::const_iterator pit = store.project<Rec::ByPhone>(nit);
		ps.modify(pit, Rec::PhoneChange("022"));
	}
}

Использование индексов не ограничено полями — можно пользовать и методы классов, например:

struct Rec {
	QString n, phone, addr;
	QString name() const { return n; }
	struct ByName {};
	struct ByPhone {};
};

typedef boost::multi_index_container<Rec,
	indexed_by<
		hashed_unique<
			tag<Rec::ByName>, const_mem_fun<Rec,QString,&Rec::name>
		>,
		ordered_non_unique<
			tag<Rec::ByPhone>, member<Rec,QString,&Rec::phone>
		>
	>
> Store;

Отдельно стоит упомянуть использование указателей:

struct Rec {
	QString n, phone, addr;
	QString name() const { return n; }
	struct ByName {};
	struct ByPhone {};
};
typedef boost::shared_ptr<Rec> Rec_ptr;

typedef boost::multi_index_container<Rec_ptr,
	indexed_by<
		hashed_non_unique<
			tag<Rec::ByName>, const_mem_fun<Rec,QString,&Rec::name>
		>,
		ordered_non_unique<
			tag<Rec::ByPhone>, member<Rec,QString,&Rec::phone>
		>,
		hashed_non_unique<
			tag<Rec::ByKey>, composite_key<
				Rec,
				member<Rec,QString,&Rec::phone>,
				member<Rec,QString,&Rec::addr>
			>
		>,
		ordered_non_unique<
			tag<Rec::ByAddr>, member<Rec,QString,&Rec::addr>
		>
	>
> Store;

Вся остальная логика остаётся практически той же самой (только -> вместо. в пару мест).

{
	QString find_phone = "022";
	Store::index<Rec::ByPhone>::type::iterator it0, it1;
	tie(it0,it1) = store.get<Rec::ByPhone>().equal_range(find_phone);
	while(it0 != it1) { qDebug() << (*it0)->name(); ++it0; }
}

Плюс стоит добавлять например блок

		ordered_unique<
			tag<Rec::ByPtr>, const_mem_fun<Rec_ptr,Rec *,&Rec_ptr::get>
		>,

Чтобы исключать добавление дупликатов указателей.

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

Надеюсь простыми примерами я даю возможность «горячего старта» пользования этого замечательного инструмента, так как изучениe оригинальной документации и попытки разобрать ошибки компилятора о шаблонах в использовании multi_index вызывают сразу большое уныние у новичков и попытки сделать что-то своё. Получается как всегда.

Автор: yshurik

Источник ^[1]