Re: [Boost-users] boost::multi_index

Subject: Re: [Boost-users] boost::multi_index
From: joaquin_at_[hidden]
Date: 2011-04-08 02:26:31

El 07/04/2011 16:20, Dominique Devienne escribió:
> On Wed, Apr 6, 2011 at 1:54 PM,<ppatel_at_[hidden]>  wrote:
>> I have a question regarding creating composite key/specifying length for
>> arrays while using multi_index container based on following structure.
>>
>> struct TestStruct {
>>                  char firstKey[50];
>>                  char secondKeyPart[3];
>>                  uint32_t thirdKeyPart;
>>                  ……Some other information….
>> };
> Using a composite key and associated hasher/equalTo types yields some
> pretty long (and ugly?) types for the multi-index
> container/extractor/hasher/equaler. If "……Some other information…." is
> not too large such that TestStruct is not too expensive to construct,
> you're often better of using the identity key extractor, and implement
> the hasher and op== in terms of TestStruct itself. The only downside I
> see is that you must constructs a whole new TestStruct when you want
> to look one up instead of doing a make_tuple(part1, part2, part3),
> which is why I mentioned above "if TestStruct is not too expensive to
> construct". This is the route we followed, away from composite keys
> and into custom hasher/equaler of our own structs. Not sure if Joaquin
> also recommend that route, but it worked fine for us and makes things
> simpler IMHO. --DD

I leans towards the composite_key solution, as it more clearly expresses the intention
than the equivalent, hand-coded solution, but this is after all a matter of personal
taste.

As for the downside you refer to, having to create a potentially expensive TestStruct,
Boost.MultiIndex features so-called compatible keys, which can come to the rescue here:

http://www.boost.org/libs/multi_index/doc/tutorial/basics.html#special_lookup

The idea is that you can simply use some structure that contains the key info without
the overload and make this interoperable with TestStruct with respect to hashing and
equality comparison:

   struct TestStructKeyInfo
   {
     TestStructKeyInfo(const char* f,const char* s,uint32_t t)
     {
       std::strcpy(firstKeyPart,f);
       std::strcpy(secondKeyPart,s);
       thirdKeyPart=t;
     }

     char firstKeyPart[50];
     char secondKeyPart[3];
     uint32_t thirdKeyPart;
   };

   std::size_t hash_value(const TestStruct& t)
   {
     std::size_t seed=0;
     for(const char* str=t.firstKeyPart;*str;++str)
       boost::hash_combine(seed,*str);
     for(const char* str=t.secondKeyPart;*str;++str)
       boost::hash_combine(seed,*str);
     boost::hash_combine(seed,t.thirdKeyPart);
     return seed;
   }

   std::size_t hash_value(const TestStructKeyInfo& t)
   {
     std::size_t seed=0;
     for(const char* str=t.firstKeyPart;*str;++str)
       boost::hash_combine(seed,*str);
     for(const char* str=t.secondKeyPart;*str;++str)
       boost::hash_combine(seed,*str);
     boost::hash_combine(seed,t.thirdKeyPart);
     return seed;
   }

   bool operator==(const TestStruct& t1,const TestStruct& t2)
   {
     return
       std::strcmp(t1.firstKeyPart,t2.firstKeyPart)==0&&
       std::strcmp(t1.secondKeyPart,t2.secondKeyPart)==0&&
       t1.thirdKeyPart==t2.thirdKeyPart;
   }

   bool operator==(const TestStruct& t1,const TestStructKeyInfo& t2)
   {
     return
       std::strcmp(t1.firstKeyPart,t2.firstKeyPart)==0&&
       std::strcmp(t1.secondKeyPart,t2.secondKeyPart)==0&&
       t1.thirdKeyPart==t2.thirdKeyPart;
   }

   bool operator==(const TestStructKeyInfo& t1,const TestStruct& t2)
   {
     return
       std::strcmp(t1.firstKeyPart,t2.firstKeyPart)==0&&
       std::strcmp(t1.secondKeyPart,t2.secondKeyPart)==0&&
       t1.thirdKeyPart==t2.thirdKeyPart;
   }

so that you can define the container like this:

   struct TestStructHash:
     boost::hash<TestStruct>,
     boost::hash<TestStructKeyInfo>
   {
     using boost::hash<TestStruct>::operator();
     using boost::hash<TestStructKeyInfo>::operator();
   };

   struct TestStructEqualTo:std::equal_to<TestStruct>
   {
     using std::equal_to<TestStruct>::operator();
     bool operator()(const TestStruct& t1,const TestStructKeyInfo& t2)const
     {
       return t1==t2;
     }
     bool operator()(const TestStructKeyInfo& t1,const TestStruct& t2)const
     {
       return t1==t2;
     }
   };

   typedef multi_index_container<
     TestStruct,
     indexed_by<
       hashed_unique<
         identity<TestStruct>,
         TestStructHash,
         TestStructEqualTo
 >
 >
 > TS;

and use TestStructKeyInfo for lookup operations:

   TS::iterator it=ts.find(TestStructKeyInfo("hello","ab",2));

This is, after all, not much different from passing tuples around when using
composite keys.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo

Este mensaje se dirige exclusivamente a su destinatario. Puede consultar nuestra política de envío y recepción de correo electrónico en el enlace situado más abajo.
This message is intended exclusively for its addressee. We only send and receive email on the basis of the terms set out at.
http://www.tid.es/ES/PAGINAS/disclaimer.aspx