From: Christoph Kögl (christoph_at_[hidden])
Date: 2003-09-15 16:48:21
most of the Standard Library implementations I know (HP, SGI, GCC,
Dinkumware, ...) use an rb-tree template for implementing
multimap. Insert, search, and delete are of course O(log n), next and
by the tree iterator's operator++/--) are amortized O(1) (could be
but one would need node threading to do this), and min and max (easily
begin / end) are worst-case O(1). Both std::set and std::map can of
course be used to
add "extra info" to the tree nodes (by suitably choosing the template
Actually, implementing std::set etc. by rb-trees is not the only choice,
e.g. the Copenhagen
STL experimented with B-trees. Many height-balanced and weight-balanced
are candidates for implementing the standard associative containers.
This means that you cannot
be sure that a "randomly chosen" std::set is based on a rb-tree. But
from your posting
I gather that your main concern is the time complexities of various
operations. Or do you
need the special qualities of a rb-tree? If not: the C++ Standard
mandates almost exactly
the time complexities you are giving, for every conceivable
implementation of the standard
associative containers set/map etc.
Am Die, 2003-09-16 um 09.42 schrieb ch00k:
> Will it be useful to add such a data structure to boost library?
> by addming extra info in tree node we could increase speed on some oerations
> insert, search, delete are still O(log n)
> next, prev - O(1) min, max - O(1), (instead of O(log(n)),
> It will be useful to design a template, that enables developer to add extra
> info to RB-Tree.- this can be useful to build such data structures as
> intervals tree, for example
> For present moment I have ugly C rb-trees implementation and want to make a
> template on the base of it.
> Maybe, such data structure is already included in boost or can be
> implemented by STL means?
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk