RE: [boost] Is there any interest in this container?

From: Peter Palotas (peter_at_[hidden])
Date: 2004-03-17 09:31:57

> >>> peter_at_[hidden] 03/16/04 03:49PM >>> wrote:
> > I was wondering if there is any interest in a container that is a 
> > model of sequence (just like std::vector or std::list) and with an 
> > interface matching that of  std::vector (maybe with minor 
> differences 
> > due to efficiency) but with different time complexities?
> 
> On a related note, all the basic associative containers could 
> (and arguably should) have an "nth_element" method with 
> complexity O(log(n)).  With this interface addition a 
> container with an interface like vector but complexity like 
> map could be adapted from map akin to the way queue is 
> adapted from deque. 

Are you suggesting a change in the implementation of the standard sorted
associative containers?  I'm not sure that would be a good idea, since
maintaining information in them to find the nth element in O(log n) time
would add an overhead to insert/delete operations which would be undesirable
if you don't need that functionality, which in fact I think you normally
don't.

Just a thought.

// Peter Palotas