Re: [boost] interest in sorted vector containers?

From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2006-07-30 11:46:44

> OK, great, I think it'll be excellent to have them in there. I hadn't 
> seen that library, it looks like it will be useful for a lot of people!

I would be happy to have official Boost ordered vector containers (I 
don't care if those are based on Boost Interprocess ones or not) if we 
can have an implementation that can be placed in shared memory. That 
means that we should have a vector implementation that can be also 
placed in shared memory (we can't use std::vector). Otherwise I would 
need to maintain duplicated ordered vectors in Boost.Interprocess.

Apart from this problem there is an interesting ISO paper by Howard Hinnant:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1780.html

discussing insertion hints. These hints can be used also to specify 
insertion point in multikey containers and optimize insertions. 
Interprocess code implements "insert before" approach of this proposal 
with a small optimization.

I know that implementing a vector (or the minimal subset to implement 
ordered vector classes) is quite a big task (well, it's already 
implemented in Boost.Interprocess) but I would like to minimize the 
number of containers in Boost. If ordered vectors are created for boost, 
I'm ready to help to make them compatible with shared memory and drop 
Interprocess ones. I'm ready to help also when unordered containers are 
proposed for Boost.

Apart from this, there are allocator improvement proposals from Howard 
(http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1953.html) and 
another one written by me 
(http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2045.html) to 
  allow in-place expansion features. Ordered vectors are good candidates 
to implement allocation optimizations. Boost Interprocess code uses 
allocator versioning based on my proposal to allow in-place expansions.

So if anyone wants to have a look and needs explanations, ask here!

Regards,

Ion