Re: [Boost-users] [multi-index] retrieve unique keys of a non-unique index

Subject: Re: [Boost-users] [multi-index] retrieve unique keys of a non-unique index
From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2013-08-02 03:36:55

El 01/08/2013 22:47, Rory McCarthy escribió:
Hi everyone (my apologies if this shows as a report),

In the following example is there a more efficient way to retrieve the unique keys of a non-unique index?

[...]

  boost::multi_index::index<TaggedNodes, name>::type::iterator ic0 = get<name>(taggedNodes).begin();
  boost::multi_index::index<TaggedNodes, name>::type::iterator ic1 = get<name>(taggedNodes).end();
  while (ic0 != ic1)
  {
    std::cout << ic0->name << std::endl;
    ic0 = get<name>(taggedNodes).equal_range(ic0->name).second;
  }

In big-O terms, this is as good as you can get with hashed indices. A slightly more efficient approach
(saving some unnecessary lookup) would be:

  void dump_entry_name(const TaggedNodeEntry& x)
  {
    std::cout<<x.name<<std::endl;
  }

  bool equal_entry_name(const TaggedNodeEntry& x,const TaggedNodeEntry& y)
  {
    return x.name==y.name;
  }

  ...

  std::unique_copy(
    get<name>(taggedNodes).begin(),get<name>(taggedNodes).end(),
    boost::make_function_output_iterator(&dump_entry_name),
    equal_entry_name);

(which gets nicer if you can use lambda functions instead.)

This is O(n), n being the number of total elements. If you use ordered indices, then appropriate use
of upper_bound to skip a range of equivalent elements (much as you're doing with equal_range) would
yield O(m*log(n)), where m is the number of *different* elements: this is better than the original
when m << n.

Joaquín M López Muñoz
Telefónica Digital

________________________________

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