RE: [boost] More ramblings on a sorted vector container

From: AlisdairM (AlisdairM_at_[hidden])
Date: 2002-01-25 16:15:43

Monkey say, monkey do...

After asking about the 'obvious' sorted_vector implementation last weekend I
took an evening off this week to knock my own up anyway (still haven't
sorted out my yahoo account to get files out the vault)

The simple answer to my question is 'because the interface will be close,
but not identical, so why limit yourself?'

First thing that must go is any non-const iterator, as a permanently sorted
vector is clearly [potentially] invalidated if a value changes, and adding
proxies and indirection to the iterators invalidates the &my_vector[0]
pointing to the start of continuous storage.  It may be fixable, but gets
messy quickly or we accept only const_iterators.

push_back is either badly named now, or replaced by insert.  If we remove
push_back, then do we also remove pop_back for symmetry, or retain it as
useful but have an odd container that can pop but not push?

Likewise, all the insert functions want a version that does not take an
iterator directing where to put them, as that is determined by sort order.

The final killer for me though was that the erase functions take iterators,
not const_iterators (as deleting an object may well have an effect on it!)

Implementing everything else in these terms (I simply wrapped an
owned-vector) we can now supply the finished container, but the interface is
clearly not quite the intuitive carry-over I had intended, so opening the
debate indeed to what other issues to take onboard in the process.

Thought I'd pass this on for anyone else wondering as I was.  There is no
substitute for experience ;¬ )

AlisdairM

> -----Original Message-----
> From: David Abrahams [mailto:david.abrahams_at_[hidden]]
> Sent: 20 January 2002 13:53
> To: boost_at_[hidden]
> Subject: Re: [boost] More ramblings on a sorted vector container

> OK, perhaps I was taking the whole thread a little *too* literally,
altough
> I do think that the 'basic' sorted vector would be a useful addition.
Must
> see if I can find enough time off to knock one out myself this week...

We already have one; no need to reinvent the wheel. Most of the job and
thought about the design has already been done:

http://groups.yahoo.com/group/boost/files/associative%20vector/potter.zip

The work in here just needs to be polished up and finalized. If you'd like
to shepherd this to formal review, it'd be greatly appreciated.