Boost logo

Boost :

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

  string name()const
    string str=family_name;
    str+=" ";
    return str;

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

typedef indexed_set<
> employee_set;

int main()
  employee_set es;


  for(employee_set::iterator it=es.begin();it!=es.end();++it){

  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

Boost list run by bdawes at, gregod at, cpdaniel at, john at