Interest in O(log n) linear list?
The STL contains vector, which has O(1) lookup and O(n) insertion. It also has list, which has O(n) lookup and O(1) insertion. There is also a third type of container, which doesn't exist in the STL, which has O(log n) lookup and O(log n) insertion. (For those who have read Knuth's TAOCP, it's a balanced tree with the RANK field). AFAIK, there is no well-known name for this structure, but a linear list with both operations fairly fast seems a useful item to have. Any interest? Thanks, Stephen Dolan
--- Stephen Dolan wrote:
There is also a third type of container, which doesn't exist in the STL, which has O(log n) lookup and O(log n) insertion. (For those who have read Knuth's TAOCP, it's a balanced tree with the RANK field). AFAIK, there is no well-known name for this structure, but a linear list with both operations fairly fast seems a useful item to have.
The STL treats trees as either sets or maps. In your case, you might want to look at std::set first; it should have the time complexities you're looking for, in addition to linear iteration through the elements. HTH, Cromwell D. Enage __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com
Nope, not the same. Sorry, maybe I wasn't clear enough. A set or map is an associative container which supports lookup *by key* and insertion (deletion, etc) *by key*. A "linear list" is any data structure which supports lookup *by position* and insertion,etc *by position*. A map<int, foo> is not a linear list because if I insert another element into the map, the existing elements aren't "pushed right". I can, using std::map, insert an element in log time, but to find the n-th element takes linear time. It is possible to implement a data structure supporting both the operations "insert in position n" and "find element in position n" in log time, I was wondering if there was any interest for it. Sorry about the confusion, Stephen Dolan
Am Samstag, den 29.07.2006, 18:54 +0100 schrieb Stephen Dolan: [...]
A map<int, foo> is not a linear list because if I insert another element into the map, the existing elements aren't "pushed right". I can, using std::map, insert an element in log time, but to find the n-th element takes linear time. It is possible to implement a data structure supporting both the operations "insert in position n" and "find element in position n" in log time, I was wondering if there was any interest for it.
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
Bernhard Reiter wrote:
Am Samstag, den 29.07.2006, 18:54 +0100 schrieb Stephen Dolan: [...]
A map<int, foo> is not a linear list because if I insert another element into the map, the existing elements aren't "pushed right". I can, using std::map, insert an element in log time, but to find the n-th element takes linear time. It is possible to implement a data structure supporting both the operations "insert in position n" and "find element in position n" in log time, I was wondering if there was any interest for it.
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)
For those who care about names and such... The description I based it on is from the "Introduction to Algorithms" textbook. In it they refer to the category of trees that keep additional data "order-statistic tree" and the extra order info as the "rank". Not something that rolls of the tongue :-) The big change from their description is that instead of implementing it as a red-black tree with the extra rank data. I removed the color component of the node as it can be inferred from the rank information. -- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org - grafik/redshift-software.com -- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo
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
--- Johan Råde wrote:
"rank tree" is not a good name. It focuses too much on the implementation.
rank_tree is fine for the name of the class.
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
What's needed is a new Container concept that covers these requirements.
So what would be a good name?
I'm thinking 'Logarithmic Access Container', analogous to std::vector fulfilling the requirements of a 'Random Access Container'. Cromwell D. Enage __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com
Cromwell Enage wrote:
--- Johan Råde wrote:
"rank_tree" is not a good name. It focuses on the implementation.
rank_tree is fine for the name of the class.
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
What's needed is a new Container concept that covers these requirements.
No. rank_tree is definitely not a good name. It is as if set had been named red_and_black_tree. There will be no ranks and no trees visible through the public interface of the class. The name of a class should reflect its interface and its observable behaviour, and not its implementation. Aside from this detail, I think this class is an excellent idea. If you need a sequential container with fast access and fast insertion, then there is no good option in STL and Boost today. I will use this class. --Johan Råde
Johan Råde wrote:
Cromwell Enage wrote:
--- Johan Råde wrote:
"rank_tree" is not a good name. It focuses on the implementation. rank_tree is fine for the name of the class.
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 What's needed is a new Container concept that covers these requirements.
No. rank_tree is definitely not a good name. It is as if set had been named red_and_black_tree.
If given the chance there would be an std::red_black_tree, which is used as an implementation detail of the associative containers. Or more preferable one could specialize map and set to use any associative container implementation of your liking. But until there is a standard tree interfaces this won't happen.
There will be no ranks and no trees visible through the public interface of the class.
Why not? It is perfectly useful information in some algorithms and use cases. Specifically that information is why I wrote the my implementation. It allows bidirectional mapping of the index and value (through the iterator).
The name of a class should reflect its interface and its observable behaviour, and not its implementation.
Yes. But you are limiting the implementation to reflect your use case. PS. There have been many times when I wished I had access to the tree internals of map and set to improve the efficiency of some algorithms. So it's not just a problem in this case. -- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org - grafik/redshift-software.com -- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo
Rene Rivera wrote:
Johan Råde wrote:
There will be no ranks and no trees visible through the public interface of the class.
Why not? It is perfectly useful information in some algorithms and use cases. Specifically that information is why I wrote the my implementation. It allows bidirectional mapping of the index and value (through the iterator).
The name of a class should reflect its interface and its observable behaviour, and not its implementation.
Yes. But you are limiting the implementation to reflect your use case.
OK. If the interface exposes the tree internals, then the name is fine. I assumed the class would have an interface similar to the interfaces of vector and list. Maybe I was wrong. Anyway, the class seems like an excellent idea.
Rene Rivera wrote: et had been named red_and_black_tree.
If given the chance there would be an std::red_black_tree, which is used as an implementation detail of the associative containers. Or more preferable one could specialize map and set to use any associative container implementation of your liking. But until there is a standard tree interfaces this won't happen.
I agree. My ideal container library would have low level container classes such as vector, deque, list, red_and_black_tree, hash_container and higher level adapter classes such as random_access_container, stack, queue, map, multimap, set, multiset It should be possible to instantiate each adapter classes with several different container classes. --Johan Råde
On 7/29/06, Stephen Dolan <stedolan@gmail.com> wrote:
The STL contains vector, which has O(1) lookup and O(n) insertion. It also has list, which has O(n) lookup and O(1) insertion. There is also a third type of container, which doesn't exist in the STL, which has O(log n) lookup and O(log n) insertion. (For those who have read Knuth's TAOCP, it's a balanced tree with the RANK field). AFAIK, there is no well-known name for this structure, but a linear list with both operations fairly fast seems a useful item to have.
Sounds much like a map< size_t, T > to me...
Ok, here's an example. map<int, char> list; list[0] = 'a'; list[1] = 'b'; list[2] = 'c'; list[3] = 'd'; So, the nth element of the list is list[n]. How do I insert an element into the middle of the list? I have to move all the other elements out of the way. e.g. if I make 'x' list[2], then I want list[3] == 'c' and list[4] == 'd' Using std::map, you have to change them all giving O(n) performance. There is another data structure, *not in the STL*, which can emulate linear lists using a binary tree, thus giving log n performance for all operations. It is *not* an associative structure like set or map, but a *linear list* like list or vector. It's semantics are exactly the same as the semantics of list or vector, but with different complexities. HTH, Stephen Dolan
participants (6)
-
Bernhard Reiter -
Cromwell Enage -
Johan Råde -
me22 -
Rene Rivera -
Stephen Dolan