[boost] Re: Re: indexed_set prerelease 7.0

From: Vladimir Prus (ghost_at_[hidden])
Date: 2003-10-30 11:32:02

Hi Joaqu?n,

>> some time ago I wrote a class called numbered_set. It was like a set (i.e
>> efficiently checked for duplicates) but had additional integer index, so
>> that all elements could be obtained by the index in constant time.
>>
>> Will it be possible to mimic this functionality using your library? I've
>> quickly browsed the docs and did not find if it's possible.
>>
> 
> I don't think so. Lookup in indexed_set is logarithmic, not constant.
> Your class resembles more an "ordered vector" container, I think
> Matt Austern wrote something about this some years ago.

Ok, guess I need to dig that information.

>> One more small comment. The 'tagged indices' might not be the right
>> solution: they mean that I need to introduce more-or-less global type
>> 'name' just because I want to store employee in an indexed_set. Is it
>> workable to use 'member' function to specify index. E.g. instead of
>>
>>     typedef employee_set::index_type<name>::type employee_set_by_name;
>>
>> to write
>>
>>     typedef employee_set::index_type<
>>          member<employee, std::string, &employee::name> >::type
>>          employee_set_by_name;
>>
> 
> You can do that. Any type can be specified as a tag, even member<...>
> as you propose. No modifications needed in the library, just use
> member<...> as the tag when declaring your indexed_set instantiations.
> If you're concerned about global namespace polluting, you can have the
> tags typedefed inside the employee class, for instance:
> 
> class employee
> {
>   ...
>   struct name_tag{};
> }
> 
> typedef indexed_set<
>   employee,
>   index_list<
>     unique<identity<employee> >,
> 
>
non_unique<tag<employee::name_tag>,member<employee,std::string,&employee::name>
> >
>>
>> employee_set;
> 
> typedef employee_set::index_type<employee::name_tag>::type
> employee_set_by_name;
> 
> Get the idea?

Yea, nice, except that I probably don't want to add typedefs to a class for
the sake of one client. The idea that member<> can be used as tag is really
nice.

>> I also think that
>>
>>     member<employee, std::string, &employee::name>
>>
>> is too verbose, though I'm not all all sure it can be made shorter.
> 
> There was a discussion about this some months ago, and the general
> consensus is that it cannot be shortened (no way to extract
> the info from say just &employee_name.)

It's a pity. 

> The macro BOOST_INDEXED_MEMBER, though not intended as
> an abbreviation utility, provides a slightly simpler syntax. Take a look
> at the advanced topics section for more info on this macro.

Ok, I understand.

>> And the final note: what if employee::name is a method, not member
>> variable? This does not seem to be supported. It it by design, technical
>> problems or lack of time?
> 
> It is supported. Key extractors need not be instantiations of member<> or
> identity<>, the user can provide her own extractors. Continuing with your
> proposed example, one would do as follows:
> 
> #include <boost/indexed_set.hpp>
> #include <iostream>
> #include <string>
> 
> using namespace std;
> using namespace boost::indexed_sets;

BTW, I'm not sure this namespace name is good idea. After I wrote
"indexed_set" in header name, I'm very likely to type "indexed_set" in
namespace name. Maybe, it the file really provides more than one
indexed_set, the name can be tweaked?

> struct employee
> {
>   employee(string given_name,string family_name):
>     given_name(given_name),family_name(family_name)
>   {}
> 
>   string name()const
>   {
>     string str=family_name;
>     str+=" ";
>     str+=given_name;
>     return str;
>   }
> 
> private:
>   string given_name;
>   string family_name;
> };
> 
> struct employee_name_extractor
> {
>   typedef employee argument_type;
>   typedef string   result_type;
> 
>   string operator()(const employee& e)const{return e.name();}
> };
> 
> typedef indexed_set<
>   employee,
>   index_list<
>     unique<employee_name_extractor>
>   >
>> employee_set;

Great. 

> int main()
> {
>   employee_set es;
> 
>   es.insert(employee("Joe","Smith"));
>   es.insert(employee("Robert","Nightingale"));
>   es.insert(employee("Robert","Brown"));
>   es.insert(employee("Marc","Tuxedo"));
> 
>   for(employee_set::iterator it=es.begin();it!=es.end();++it){
>     cout<<it->name()<<endl;
>   }
> 
>   return 0;
> }
> 
> Here key extraction is made thru employee_name_extractor. Naturally,
> one cannot use modify_key() with such extractor (it does not return
> references), but this is perfectly logical.
> 
> Whether this kind of constructs (key extractors based on members) should
> be provided as a predefined utility or not depends, I guess, on how common
> a situation we deem this to be.

You're right -- it's wise to wait for more comments. 

- Volodya