[boost] Re: IndexedSet Review

From: David B. Held (dheld_at_[hidden])
Date: 2004-03-29 14:57:49

"Joaquín Mª López Muñoz" <joaquin_at_[hidden]> wrote in message
news:406802F9.4990B35C_at_tid.es...
> [...]
> Ummm... If I followed your approach I would be incurring two
> extra copies which is precisely what modify() is meant to avoid.
> For non-destructive updating you can use update(), that's the
> idea. If I'm not making myself clear please tell me so.

Yeah, I'm not understanding where the extra copies would come
from.  As far as I can tell, it's possible to reorder the operations
in modify() without increasing the cost of execution except by a
few instructions.  This is my understanding of how modify() works
now:

mod(element); // changes the element immediately and in-place
unlink(element); // takes the node out of the index
link2(element); // puts it back in at the correct spot

This is what I'm suggesting:

i = find(new_element); // look to see if modify() can even succeed
if (*i == new_element) return;
mod(element); // now change the node, since modify() will succeed
unlike(element); // same as before
link2(element, i); // reinsert, but use i as a hint (which will be correct)

I don't see any copies being made at all (except possibly of an
iterator, which should hardly be prohibitively expensive).  What is
new is that you need to be able to look at the changed value without
actually changing anything.  That's why I suggested a change to
the Modifier function object:

class change_name
{
public:
    change_name(std::string const& new_name) : name_(new_name) { }
    std::string const& value(void) const { return name_; }
    void operator()(employee& em) const { em.name_ = name_; }
private:
    std::string name_;
};

So find(element) is something like lower_bound(mod.value()).
The complexity shouldn't change because in both cases, you have
to perform 2 log n searches through the index to remove and then
relink the node.  The only difference is when you perform those
searches.  I'm saying take the second insert search and move it
to the beginning of the operation, so that you know if you can
succeed before you unlink the node.  If I'm missing something,
let me know.

> [...]
> > Some of the lines are > 80 columns (e.g.: the copyright notice).
>
> Is this strictly required? If so I'll go thru the code and make the
> changes. If not, I'd rather leave it like that.

I don't think it's strictly required, but a lot of people complain
about long lines.

> <off topic> It'd be nice if Boost.Config provided a (possibly
> automatically generated) reference table showing which
> compilers do have a specific defect macro.</off topic>

That would be great, but as with many things, complaints are
usually satisfied by the complainer. ;)

> [...]
> Great! The score is 9-0 so far.

I think it's the review manager's job to keep track of that, but I
guess a little enthusiasm doesn't hurt. ;)

> [...]
> Well, I stated previously that I'll do what people agree on. I don't
> know if the final decision should be made by Pavel as the review
> manager.  IMHO, qualified identifiers will be so long anyway that
> having an additional ::container:: won't hurt much.

It won't hurt, but if it won't help, why should it be there?  We can add
gratuitous namespace levels all day long, but that doesn't mean
we should.

> [...]
> The main problem with "Set" slipping into the name of the
> container is that, for instance, the following
>
> indexed_set<int,index_list<sequenced<> > >
>
> does not have anything to do with sets (it resembles a std::list of
> constant ints.) For this reason I like Multicontainer better (or
> something along this line.)

Perhaps, but "multicontainer" sounds *too* generic.  I would expect
something with that name to support any number of back-ends, like
vector, deque, etc.  Actually, come to think of it, that might not be
such a bad idea.  However, it wouldn't really fit the implementation
of the library, because the container is a node-based one, and
vector wouldn't play as nicely as the others.  But if you could not
only created computed indices, but also *virtual indices*, then you
could create an associative vector!  However, this might exceed
the scope of the library.  By a virtual index, I mean that the vector
itself would remain sorted, and you would have an index that
performs a binary search without actually storing any additional
node information.  That sounds like a big mess, though.

The reason I think that "Set" is ok is that the STL "Set" is only
vaguely related to mathematical sets.  The only property of
essence that is related to mathematical sets is the uniqueness
property, and even that is violated by the multiset.  The vagarities
of computational performance necessitate that the STL notion
of Set be stricter than the mathematical notion for it to be usable.
In the same way, I think that IndexedSet need not strictly be even
an STL Set for similar reasons.  It supports the "essential
properties" of uniqueness and intrinsic ordering, and adds
additional concepts which cater to computational practicalities.
It's not *merely* a container, but a special kind of container.  It's
not truly a generic container, so I think it would benefit from a
more specific name.  It's primarily associative, and that's the
essence of the STL Set, which is why I think your container
ultimately *is* a set, even though a degenerate configuration
may not be.

> <off topic>Reviewers have showed little or no interest in
> sequenced indices.  Seems weird to me, as they can be used
> to construct a seemingly useful list-like container with fast
> lookup.</off topic>

This is probably because people who need the fast lookup usually
don't need the original insert order, so the list aspect of it has
limited usefulness.  However, I can think of a few use cases where
it might be handy, so I suspect that really, this is a feature waiting
to be discovered.

> As for the Composite Sorted Associative Container concept, we
> have the same problem. Technically, the requirements imposed
> to current or future index types by indexed_set are much weaker
> than being some sort of associative container. I cannot even state
> global complexity bounds (please check the reference, page
> "Index reference", section "Complexity signature").

Ok, so if the concept is not a refinement of Associative Container,
then create a new concept!

> I agree with you a concept section would be highly desirable, but
> here I definitely need some help. What you request is not trivial.

Then let's take a first stab at it.  What you have is similar to an
Associative Container, but is fundamentally different.  The way in
which it is different is that there is more than one way to access
the data.  And, as you say, it is like multiple containers in one.  So
I think the most fundamental concept here is Composite Container.
The reason we don't want to use "Multiple" is that "Multiple
Associative Container" means "multiset" and "multimap" (not my
favorite terminology, but nobody asked me when they were naming
them ;).

Let's rip off SGI for a minute:

    Description

    A Composite Container is a variable-sized Container that
    supports retrieval of elements (values) based on one or more
    keys. It supports insertion and removal of elements, but differs
    from an Associative Container in that the complexity of the
    operations depends on the type of key indices used.

    [insert additional discussion here]

    Refinement of

    Forward Container

Now, here we have a tricky issue.  By default, IndexedSet *is*
default constructible, but we can't say that Composite Container
should be, because IndexedSet might *not* be default c'tible if
one of the key types are not.  The STL solved this by simply
implicitly requiring key comparators to be default c'tible, but
perhaps this requirement is not justified.  Anyway, let's continue:

    Associated types

    [this part is lengthy, but I think you know what to fill in here]

    Notation

    [this part should be obvious as well]

    Definitions

    [just rip off SGI some more ;)]

    Valid expressions

    [this is where the interesting stuff goes]

    Expression semantics

    [this is more of the meat of the concept]

    Complexity guarantees

    [just put your conditional complexity analyses here]

In particular, I think you should note that both ordered and non-
ordered indices are possible, and give separate sets of
guarantees for each, noting how the complexity is bounded from
below by the slowest index type.  I don't see how you can do much
better than that, but I think at least that much is required.

    Invariants

    [you probably know what to put here, for the most part]

Models

    * indexed_set (of course)
    * bimap (if anyone makes it ;)

That's a start anyway, and if you fill in as much of that as you can,
I think others will be able to help you fill in the rest.  It also might
help if you define other concepts first, like Ordered Unique Index,
etc.  I know it's a lot of work, but I think it's worthwhile (especially
for people wanting to extend the library, i.e.: by defining custom
index types).

> [...]
> My Latin (I speak Spanish) heritage makes me favor "indices"
> to "indexes" (and "minuscule" to "miniscule", etc.) The Google
> metric could be biased by the fact that "indexes" is not only the
> plural of "index" but also the 3rd singular formal of the Present
> tense of the verb "index".

Good call!  That was some sloppy reasoning on my part. ;)

> [...]
> The nth_ prefix has some tradition in C++, why not use it here
> too?

I guess there is "nth_element()".  I've never had need for it, so
I didn't even notice it.

Dave

---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.581 / Virus Database: 368 - Release Date: 2/9/2004