Re: [boost] Re: indexed_set prerelease 7.0

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2003-10-30 05:34:36

Hi Vladimir

Vladimir Prus ha escrito:

> 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.

>
> 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?

>
> 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.)
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.

>
> 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;

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;

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.

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