boost multi index - possible?
suresh.amritapuri
I have a map of a set of strings and a double.
map<set<string>,double>
Typical entries are like this:
(a1,b1,c1) -> 10 ;
(a1,b1,c2)->2.5
(a1,b1,c2)-> 3
Of course if i give full set as the key, i can get the value. But if
i want all entries containing say a1, how to do it? Is it possible to
do this through boost::multi-index? I am unable to make out by reading
multi-index doc. Is there any other way than boost multi-index?
Thanks
suresh
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Joaquín M López Muñoz
wrote:
> Hi,
>
> I have a map of a set of strings and a double.
>
> map<set<string>,double>
>
> Typical entries are like this:
> (a1,b1,c1) -> 10 ;
> (a1,b1,c2)->2.5
> (a1,b1,c2)-> 3
>
> Of course if i give full set as the key, i can get the value. But if
> i want all entries containing say a1, how to do it? Is it possible to
> do this through boost::multi-index? I am unable to make out by reading
> multi-index doc. Is there any other way than boost multi-index?
Hi, you can do this with Boost.MultiIndex using the so-called
special lookup operations:
http://www.boost.org/libs/multi_index/doc/tutorial/basics.html#special_lookup
Please find below a complete example showing the technique for your
particular scenario. You'll probably have some difficulties grasping
the code, do not hesitate to ask away. For simplicity's sake, some of
the bits below are not optimal (vg. partial_key_compare::operator()
could be implemented without using boost::next).
Joaqu�n M L�pez Mu�oz
Telef�nica, Investigaci�n y Desarrollo
#include <algorithm>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/utility.hpp>
#include <iostream>
#include <iterator>
#include <set>
#include <string>
using namespace boost::multi_index;
using namespace std;
typedef set<string> key_type;
struct element
{
element(const key_type& key,double value):key(key),value(value){}
key_type key;
double value;
};
ostream& operator<<(ostream& os,const element& e)
{
copy(e.key.begin(),e.key.end(),ostream_iterator<string>(os," "));
os<<"-->"<<e.value;
return os;
}
class partial_key
{
public:
partial_key(const key_type& k):pk(&k){}
const key_type& get()const{return *pk;}
private:
const key_type *pk;
};
struct partial_key_compare
{
bool operator()(const partial_key& pk,key_type& k)const
{
return lexicographical_compare(
pk.get().begin(),pk.get().end(),
k.begin(),boost::next(k.begin(),min(pk.get().size(),k.size())));
}
bool operator()(key_type& k,const partial_key& pk)const
{
return lexicographical_compare(
k.begin(),boost::next(k.begin(),min(pk.get().size(),k.size())),
pk.get().begin(),pk.get().end());
}
};
typedef multi_index_container<
element,
indexed_by<
ordered_non_unique<member<element,key_type,&element::key> >
>
> container;
key_type make_key(const char *s1)
{
key_type k;k.insert(s1);return k;
}
key_type make_key(const char *s1,const char *s2)
{
key_type k;k.insert(s1);k.insert(s2);return k;
}
key_type make_key(const char *s1,const char *s2,const char *s3)
{
key_type k;k.insert(s1);k.insert(s2);k.insert(s3);return k;
}
void dump(container::iterator first,container::iterator last)
{
std::copy(first,last,ostream_iterator<element>(cout,"\n"));
}
void dump(const pair<container::iterator,container::iterator> p)
{
dump(p.first,p.second);
}
int main()
{
container c;
c.insert(element(make_key("a1","b1","c1"),10.0));
c.insert(element(make_key("a1","b1","c2"),2.5));
c.insert(element(make_key("a1","b1","c2"),3.0));
c.insert(element(make_key("a1","b2","c1"),5.6));
c.insert(element(make_key("a2","b1","c1"),1.0));
cout<<"contents:\n";
dump(c.begin(),c.end());
cout<<"keys beginning with \"a1\":\n";
dump(c.equal_range(partial_key(make_key("a1")),partial_key_compare
()));
cout<<"keys beginning with \"a1\",\"b1\":\n";
dump(c.equal_range(partial_key(make_key
("a1","b1")),partial_key_compare()));
suresh.amritapuri
> On 12 nov, 09:44, "suresh.amritapuri" <suresh.amritap...@gmail.com>
> wrote:
>
> > Hi,
Thanks for the wonderful mail. Could you explain the following:
1. the operator() methods.
2. how to modify the code so that, if i need to get entries containing
all "c2" could be obtained.
3. How to modify so that i can get say all entries corresponding to
"c"?
These answers might help me to understand the code better. Your
example helps me to understand the boost lib better.
suresh
suresh.amritapuri
1. how to implement partial_key_compare without using boost::next?
2. earlier, when i was trying to code myself, i used a
map<set<string>,double> for storing data. But i see in all examples of
multi-index, a structure is being used. Any reasons?
thanks
suresh
Joaquín M López Muñoz
wrote:
>
> Thanks for the wonderful mail. Could you explain the following:
> 1. the operator() methods.
There are two such call operators in partial_key_compare, so
that you can an object of this class to compare partial key
with keys and keys with partial keys, in a similar way as
sat std::less<key_type> provides one call operator allowing
to compare keys with keys. Note that partial_key is just
syntactic sugar to allow the user to specifiy that a given
key must be handled as partial rather than total.
> 2. how to modify the code so that, if i need to get entries containing
> all "c2" could be obtained.
> 3. How to modify so that i can get say all entries corresponding to
> "c"?
This can't be done. The technique shown relies on the fact
that partial_key_compare induces an order that is *compatible*
with the order by which the index keeps the element sorted.
For instance, looking for the initial letter in a phone book
that is sorted alphabetically can be easily done because the
phone book is also sorted by initial letter, but looking for
the final letter can't be done efficiently.
Joaqu�n M L�pez Mu�oz
Telef�nica, Investigaci�n y Desarrollo
Joaquín M López Muñoz
> 1. how to implement partial_key_compare without using boost::next?
By hand coding the comparison loop implcitly done inside
lexicographical_compare, with the small modification that
if the loop terminates because you've traversed all of
pk, then the comparison returns false (lexicographical_compare
would return true in thes case unless k had the same length.)
> 2. earlier, when i was trying to code myself, i used a
> map<set<string>,double> for storing data. But i see in all examples of
> multi-index, a structure is being used. Any reasons?
A map<K,V> is to some extent a set of pair<K,V>. Boost.MultiIndex
mimics the behavior and semantics of sets rather than maps,
hence the need to define an element acting as the implicit
pair of map.
Joaqu�n M L�pez Mu�oz
Telef�nica, Investigaci�n y Desarrollo
suresh.amritapuri
> > all "c2" could be obtained.
> > 3. How to modify so that i can get say all entries corresponding to
> > "c"?
>
> This can't be done. The technique shown relies on the fact
> that partial_key_compare induces an order that is *compatible*
> with the order by which the index keeps the element sorted.
> For instance, looking for the initial letter in a phone book
> that is sorted alphabetically can be easily done because the
> phone book is also sorted by initial letter, but looking for
> the final letter can't be done efficiently.
>
Is there a way this can be achieved? I mean, getting all entries
corresponding to say "c2" or say "c". Is there any other solution for
that?
Thanks
suresh
Joaquín M López Muñoz
wrote:
> > > 2. how to modify the code so that, if i need to get entries containing
> > > all "c2" could be obtained.
> > > 3. How to modify so that i can get say all entries corresponding to
> > > "c"?
>
> > This can't be done. The technique shown relies on the fact
> > that partial_key_compare induces an order that is *compatible*
> > with the order by which the index keeps the element sorted.
> > For instance, looking for the initial letter in a phone book
> > that is sorted alphabetically can be easily done because the
> > phone book is also sorted by initial letter, but looking for
> > the final letter can't be done efficiently.
>
> Is there a way this can be achieved? I mean, getting all entries
> corresponding to say "c2" or say "c". Is there any other solution for
> that?
You can look for these entries manually, but that'd involve a
O(n) cost. Or you can set up an additional ordered index that
sorts the keys (set<string>) by their 3rd element. The latter
solution does not scale if you want to also search for the 4th,
5th, etc.
Joaqu�n M L�pez Mu�oz
Telef�nica, Investigaci�n y Desarrollo