Re: [boost] Interest in O(log n) linear list?

From: Johan Råde (rade_at_[hidden])
Date: 2006-07-30 04:21:55

Bernhard Reiter wrote:
> Am Samstag, den 29.07.2006, 18:54 +0100 schrieb Stephen Dolan:
> 
> I guess "rank tree"'s just a fine name -- I'm aware of an implementation
> by René, http://redshift-software.com/~grafik/RankTree.h -- and it being
> a kind of tree, I intend to offer such a thing as part of my SoC tree
> project... (https://boost-consulting.com:8443/trac/soc/wiki/tree)
> 
> Bernhard Reiter
> 
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
> 

"rank tree" is not a good name.
It focuses too much on the implementation.
What matters to the user is that it is a

1. sequential container with
2. O(log(n)) look-up and
3. O(log(n)) insertion

Whether it is implemented as a tree or in some other way is irrelevant 
to the user.

So what would be a good name?
When I typed "list" into an online thesaurus I got:

"account, agenda, archive, arrangement, ballot, bill, brief, bulletin, 
calendar, canon, catalog, catalogue, census, checklist, contents, 
dictionary, directory, docket, draft, enumeration, file, gazette, index, 
inventory, invoice, lexicon, lineup, listing, loop, manifest, 
memorandum, menu, outline, panel, poll, program, prospectus, register, 
roll, roll call, row, schedule, screed, scroll, series, slate, 
statistics, syllabus, table, tabulation, tally, thesaurus, ticket, 
timetable, vocabulary"

How about "slate"? It is nice, short, and as far I know, not used for 
anything else by C++ programmers.

--Johan Råde