RE: [Dev-C++] 'extern const' and std::vector

[Ioannis V. <iv...@at...>]

> -----Original Message-----
> From: Per Westermark [mailto:pw...@ia...] 
> Sent: Thursday, May 01, 2003 8:54 PM
> To: Ioannis Vranos
> Cc: Dev-C++ Mailing List
> Subject: RE: [Dev-C++] 'extern const' and std::vector
> 
> 
> That's the logaritmic search time.
> 
> If the tree is binary, every step down the tree halves the 
> alternative,
> similar to the bsearch() function available in ISO 9899.
> 
> If the tree is of higher order, i.e. more than two 
> alternatives at heach
> level, it will subdivide the alternatives faster.
> 
> If there are 32 values at each level, each level will do a 2^5
> subdivision. A 6-level tree would hold up to 2^(5*6) entries. 
> Max 6 tree
> nodes to test for locating a single entry among 1 billion 
> alternatives.


Still it is not "random access" (but sounds more O(n)), so implementing an
operator[] for it would not be efficient (according with the ideals of C++
regarding [] efficiency). Unless the OP means different things for "random
access", that's why I asked him if the search is sequential (=the next room
is stored next to the existing room).



> Too bad that all insert/remove operations also takes O(log n) 
> for a total
> of O(n*log n) time to populate the tree. But then again, 
> O(n*log n) is the
> expected efficiency for a general sort.
> 
> Check out libredblack at sourceforge. A red-black tree is an 
> improvement
> of the trusty btree, with a built-in hysteresis when a tree 
> has to grow
> with one more level, or shrunk one level.
> 
> Because of the good behaviour, it isn't uncommon that the stl 
> map template
> is implemented with a red-black tree.



That's nice. :)  Trees are an interesting concept.



Ioannis Vranos
 
* Programming pages: http://www.noicys.freeurl.com
* Alternative URL 1: http://run.to/noicys
* Alternative URL 2: http://www.noicys.cjb.net