multi_index

Ne Zaman Kullanılır?
Elimizde bir liste varken, elemanlara güncelleme yapmak gerekiyorsa O(n) arama yerine O(1) arama yapmak için multiindex kullanılmaz! Basit bir map sorunu halledebilir. Elemanlara farklı indeksler kullanarak erişmek gerekiyorsa bu sınıf işe yarar.

İçi Neye Benzer
İç modelinin aşağıdaki şekle benzediğini düşünüyorum.

Index çeşitleri

Key kullananlar

1. hashed_unique - std::unordered_map gibi

2. hashed_non_unique - std::unordered_multimap gibi. hashed_non_unique Sınıfı yazısına taşıdım.

3. ordered_unique - std::set gibi. ordered_unique Sınıfı yazısına taşıdım.

4. ordered_non_unique - ordered_non_unique Sınıfı yazısına taşıdım.

Key kullanmayanlar

1. sequenced - std::list gibi. sequenced Sınfı yazısına taşıdım.

2. random_access - std::vector gibi. random_access Sınıfı yazısına taşıdım.

multi_index_container Sınıfı
multi_index_container Sınıfı yazısına taşıdım.

1. hash_unique Index

Hash Index ve Composite Key

Tag kullanan bir hashed index şöyle tanımlanır. Örnekte composite_key kullanılıyor. Include olarak şunlar gerekir. Bu sefer member field yerine getter() metodlar kullandığımız için member.hpp yerine mem_fun.hpp'yi dahil etmek gerekir.

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/mem_fun.hpp>
#include <boost/multi_index/composite_key.hpp>

Kod ise şöyledir.

typedef multi_index_container<
      MyClass,
      indexed_by<
        hashed_unique< tag<struct hash> ,
          composite_key< 
            MyClass,
            const_mem_fun<MyClass,int,&MyClass::get_int >,
            const_mem_fun<MyClass,const std::vector<int>&,&MyClass::get_vec >
          >
        >,
        random_access< >
      >
    > my_list;

identity kullanılan örnekler de var. identity şöyle tanımlanır.

typedef multi_index_container<
          MyClass,
          indexed_by<
              hashed_unique< tag<hash>,
              identity<MyClass>
            >
          >
        > my_list;

Identitiy anladığım kadarıyla nesne için hash metodu olmasını istiyor. Nesne için hash metodu şöyle tanımlanıyor.

std::size_t hash_value(const MyClass& myClass)
{
  std::size_t seed = 0;

  boost::hash_combine(seed, myClass.getX());
  boost::hash_combine(seed, myClass.getY());
  boost::hash_combine(seed, myClass.getZ());

  return seed;
}

find metodu

Metodun imzası şöyle

template<
  typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
>
iterator find(const CompatibleKey& k,
              const CompatibleHash& hash,
              const CompatiblePred& eq) const;

Parametrelerin anlamları ise şöyle

KeyFromValue = composite_key<...>
CompatibleKey = MyClass
CompatibleHash = boost::hash<KeyFromValue>
CompatiblePred = equal_to<KeyFromValue>

find() metoduna key yerine tüm nesneyi geçersek hata alıyoruz. Yani şu kod hata verebiliyor.

MyClass tempy(5);
hashed_index::iterator pos = mylist.get<hash>().find(tempy);

Sebebi ise find metodunun key beklemesi. Biz ise tüm nesneyi geçiyoruz. Çözümü iki şekilde olabiliyor. İlk çözümü anlamadım ama çalışıyor.

hashed_index::iterator pos =
  mylist.get<hash>().find(boost::make_tuple(tempy));

İkinci çözüm çok daha karmaşık ama o da çalışıyor. Ben bu yöntemi kullandım çünkü projede boost::tuple bağımlılığı yaratmak istemedim.
hashed_index::iterator pos = mylist.get<hash>().find( mylist.get<hash>().key_extractor()(tempy));

Hashed Indeks'in find metodu bir iterator döner. Bu iterator end() ile karşılaştırılarak nesnenin mevcudiyeti bulunabilir.

hashed_index::iterator it = mylist.get<hash>().find(myObject);