FastMultiSet.h File Reference

a container of multiple-level set More...

#include <iostream>
#include <map>
#include <multiset>
#include <cassert>
#include <boost/typeof.hpp>

Go to the source code of this file.

Classes
class	limbo::containers::FastMultiSet< KeyType, Compare1, Compare2 >

Namespaces
	limbo
	namespace for Limbo
	limbo::containers
	namespace for Limbo.Containers

Detailed Description

a container of multiple-level set

Description : Use 2 level comparison Compare1 is for main multiset, it allows duplicate keys. Compare2 is for secondary map, it must have unique keys. In other words, keys to Compare1 can have duplicated compare results, while to Compare2, the compare results must be unique. The data structure is as follows multiset keeps the correct order that user wants for duplicate keys, map can ensure fast access because map saves <key, iterator in multiset>

This data structure can provide O(logN) in insert, erase and update for even duplicate keys

It is suitable to use pointers as key_type or value_type, which will not change during the operations. But the data the pointers point to can change, so that no data race between the order of update data and update multiset.

Author

Yibo Lin

Date

Feb 2015

Definition in file FastMultiSet.h.