[prev in list] [next in list] [prev in thread] [next in thread] 

List:       boost-users
Subject:    [Boost-users] =?utf-8?q?=5Bmulti=5Findex=5D_Announcing_preview_of?= =?utf-8?q?_ranked_indices?=
From:       Joaquin M Lopez Munoz <joaquin () tid ! es>
Date:       2015-04-22 19:34:04
Message-ID: loom.20150422T212903-565 () post ! gmane ! org
[Download RAW message or body]

Hi,

It's been 11 years since first proposed, but here it is at last. I'm
releasing a prereview of ranked indices for Boost.MultiIndex:

  struct person
  {
    int         age;
    std::string name;
  };

  typedef multi_index_container<
    person,
    indexed_by<
      ranked_non_unique<member<person,int,&person::age> >,
      ordered_non_unique<member<person,std::string,&person::name>>>>
  multi_t;


  multi_t m={{40,"Joe"},{25,"Jill"},{30,"Kurt"},{32,"Sue"}};

  auto it=m.emplace(31,"Maggie").first;
  std::cout<<m.rank(it)<<" persons younger than "<<it->name<<"\n";

  auto n=m.size()/2;
  std::cout<<n<<" persons are less than "<<m.nth(n)->age<<" years old\n";

Ranked indices add a bunch of extra rank-related capabilities to the
interface of ordered indices. The rank of an element is its numerical
position in the index. nth(i) returns an iterator to the element with
rank i, whereas rank(it) is the inverse operation. Both execute in
log(n) time.

Additionally, the member functions

  find_rank
  lower_bound_rank
  upper_bound_rank
  equal_range_rank
  range_rank

behave as their "_rank"-less counterparts except they return ranks rather
than iterators.

One drawback of ranked indices wrt ordered indices (other than their
slower perfomance and higher memory consumption) is that deletion of
elements is log(n) (in ordered indices it is constant time).

Download lib preview: http://tinyurl.com/kemwk8q
Tutorial: http://tinyurl.com/q36c9f7
Reference: http://tinyurl.com/pvoulgr

For people interested in this, I'd appreciate if you could download the
source, copy it on top of Boost 1.58 (1.57 should work as well), play a bit
with the new feature and report your results. Also, opinions on naming
are welcome. Target version for releasing is Boost 1.59, so we have
plenty of time to discuss the design before it is final.

Thank you,

Joaquín M López Muñoz
Telefónica
_______________________________________________
Boost-users mailing list
Boost-users@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users
[prev in list] [next in list] [prev in thread] [next in thread]