Boost logo

Boost :

Subject: Re: [boost] New library ( countertree: Binary trees with access by position like the vectors)
From: Stewart, Robert (Robert.Stewart_at_[hidden])
Date: 2010-09-28 06:49:52

Francisco José Tapia wrote:
> Is there any interest in a library implementing counter trees,
> which permit us to access to the elements by the position, as
> in the same way than a vector. The insertion, deletion and
> access to elements are operations O(log N).

How does this differ from Boost.MultiIndex which can provide
random access plus ordered, key-based indices in a single

> The first class implemented is vector_tree wich has the full
> interface of the STL vector and STL deque.
> When the information stored in the vector_tree is sorted, we
> can build the new classes boost::set, boost::multiset,
> boost::map and boost::multimap. These clases have the full
> interface of the STL set, multiset, map and multimap, plus a
> function which permit to access to the elements of the set,
> map... by the position. The iterators of this data stuctures
> are random access, and have a function to take the position of
> the element pointed by the iterator.

A sorted vector, with map-like functionality, is certainly a
useful data structure for occasions when it is mostly populated
one time and accessed many times thereafter. Indeed, Meyers
discussed it years ago in one of his books. The question is
whether your vector_tree is better than what Boost.MultiIndex can

> You can find the documentation, the code and the test programs
> in:
> <>

I haven't read your documentation yet, but may do so, based upon
your response.

Rob Stewart robert.stewart_at_[hidden]
Software Engineer, Core Software using std::disclaimer;
Susquehanna International Group, LLP

IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.

Boost list run by bdawes at, gregod at, cpdaniel at, john at