[boost] Re: Formal Review: Indexed Set

From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2004-03-26 13:52:46

Powell, Gary <powellg <at> amazon.com> writes:

> 
> >Have you looked at the performance section?
>   No, will do soon.

There you'll find some performance measures of
indexed_set against compositions of several
STL containers. Maybe this is what you were after.

> 
> >Umm... Sequenced indices are modelled after std::list, which
> >contains both erase and remove operations, with different
> >semantics (remove meaning erasing *all* elements with a given
> >value.)
> 
> yeah but vector, does a "move"... blech.. its in the details section,
> do what you want.

sequenced_index_remove is in the detail subnamespace,
but sequenced_index::remove is a public memfun of
sequenced indices, so it is not only a matter of
personal taste. Let me ellaborate.

Maybe the docs don't explain it clearly enough
(please check the reference) but the idea is that
sequenced indices mimic the interface of std::lists,
which do have such a remove operation in detriment
of erase(value). I don't know why std::list has
remove instead of erase (maybe because remove
is linear time?)

So, regular indices have

  erase(it)
  erase(it1,it2)
  erase(key)

and sequenced indices provide

  erase(it)
  erase(it1,it2)
  remove(value)

in sync with std::sets and std::lists, respectively.
Darren Cook proposed that interfaces be made
regular between different indices to ease
writing generic code. He proposed it for
insert operations, but the same applies for erasing.
So I could duplicate some ops in sequenced indices
and have the following (an asterisk sigals
memfuns currently not provided):

regular indices:
  insert(value)
  insert(it,value) [hinted insertion]
  insert(it1,it2)
  erase(it)
  erase(it1,it2)
  erase(key)

sequenced indices:
 *insert(value)    [alias of push_back(value)]
  insert(it,value) [it is not a hint but the insertion position]
 *insert(it1,it2)  [iterated push_back]
  erase(it)
  erase(it1,it2)
 *erase(value)     [alias of remove(value)]
  [other std::list-borrowed ops as they stand now]
  
Have I made myself clear? Does this address your
concern? I don't have any strong opinion
in favor of / against this, but others in the list
may have.

That was a long answer, allow me to continue
with the rest of your points in a separate post.

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

> BTW, once some time has passed, get another one. There are plenty of nice
> ones that need a home. Least ways there are always a heap of cats
> in the pound. They are never the same but each has been worth it.

Yes, my gf says it's about time to be three again :)