|
|
Comments and Discussions
|
|
 |
|
|
Hello, just wondering if these classes are still being supported. I just tried to compile with g++ version 4.2.3 on kubuntu 8.04, and I got some errors. The first few are:
index_set/iterator_base.h:42: error: to refer to a type member of a template parameter, use ‘typename I::value_type’
index_set/iterator_base.h:42: error: to refer to a type member of a template parameter, use ‘typename I::distance_type’
index_set/iterator_base.h:75: error: type ‘I’ is not derived from type ‘stl_bidirectional_iterator<I>’
Thanks.
|
|
|
|
|
I am not uploading new version, but you can fix this issue by adding the "typename" parameter in front of the class type definitions as reported for line 42. That may get rid of the one on 75. There may be several other places where "typename" must be added.
I compiled on MSVC which does not enforce the typename rule which I believe is required by ANSI.
|
|
|
|
|
Thanks Ray. I actually wasn't able to get it to compile as I'm not well versed in typenames, class templates, and the other tools I need to get this to work. ( I also got an error about an expected "nested-name-specifier" ). I mainly use STL classes, but don't add anything into the implementation.
Basically, I need a data structure that is an STL set, but where I can select elements at random. So, your index_set would be perfect. Can you recommend another implementation that compiles readily in Ubuntu? Or an implementation of a red-black tree that allows random selection of elements that compiles readily on Ubuntu?
Thanks very much.
|
|
|
|
|
Sorry, never saw another container like you describe. I think you should get a friend who knows STL pretty well and have him/her make the correction. It should be easy. Wherever you see a class definition that has "typedef X: ", you replace it with "typedef typename X: ". For example:
typedef T:iterator_type iterator_type
should be changed to:
typedef typename T:iterator_type iterator_type
I hope that helps. I would be a shame not be able to use the class just because of simple compiler error. I'm sorry I did not compile under ANSI restrictions myself.
Ray Virzi
|
|
|
|
|
Thanks Ray. I still can't get it to compile. I realize that you're not maintaining this anymore, but if for any reason you end up modifying it to compile on Linux/Ubuntu, please let me know.
Best Regards,
Maciek
|
|
|
|
|
I just can't understand why one would want to map linear structures onto binary search trees. I can understand if one wants to track the order items were put into a tree, but as far as I can tell, that's not possible using these structures.
Search trees are used when there is a functional relation between the domain and range (key/value pairs), and linear structures when there exists no such relation.
If I understand the code correctly, an index into a tree is not fixed. By that I mean tree[1] may not necessarily be the same value as tree[1] after an insertion or deletion of a value in the tree due to rotations. That doesn't seem too advantageous to me. It looks like a linear structure, but doesn't behave like one.
I cannot see what problems indexed access to tree structures can solve. Am I missing something here? 
--
Weiter, weiter, ins verderben.
Wir müssen leben bis wir sterben.
I blog too now[^]
|
|
|
|
|
I can understand your puzzlement, but you don't have to use the code if you don't need it 
But to offer a suggestion, what this container does is to allow lists, sets, and maps to have a random access iterator. Normally, they only have bi-directional iterators. This allows them to work inside algorithms that require random access iterators. You can do a lot of things with and indexed list that you could normally only do with an array. As for sets and maps, it is a little more obscure as you have mentioned. The algorithms you use on these must be non-mutating.
|
|
|
|
|
Ray Virzi wrote:
But to offer a suggestion, what this container does is to allow lists, sets, and maps to have a random access iterator.
Aha, I see. 
--
Weiter, weiter, ins verderben.
Wir müssen leben bis wir sterben.
I blog too now[^]
|
|
|
|
|
Another thing that is confusing: stl maps already have an operator[] defined.
The new operator[] defined in index_map has a completely different action.
|
|
|
|
|
http://judy.sourceforge.net
|
|
|
|
|
Hadn't heard of them, but I checked out your link. Looks VERY interesting. Seems to be tuned for performance at the machine level. I'll have to read more about it.
Thanks
Ray
|
|
|
|
|
I tried including the header files into my Visual Studio .NET 2003 C++ project and it fails with all kinds of errors like the following:
warning C4346: 'I::value_type' : dependent name is not a type prefix with 'typename' to indicate a type, see reference to class template instantiation 'stl_bidirectional_iterator' being compiled
error C2923: 'std::iterator' : 'I::value_type' is invalid as template argument '#2', type expected
warning C4346: 'I::distance_type' : dependent name is not a type prefix with 'typename' to indicate a type
error C2923: 'std::iterator' : 'I::distance_type' is invalid as template argument '#3', type expected
Any suggestions?
|
|
|
|
|
I guess Microsoft decided to adhere to the C++ standard more strictly in VS.NET. How convenient for them.
You can fix the errors by putting in the typename keyword just before the template type reference. Like so...
typedef typename I:value_type value_type
I don't have time to fix it right now, so I hope that helps.
Ray
|
|
|
|
|
Well as Ray Virzi wrote it seems that one has to put a lot of "typename" keywords, especially before "iterator"(e.g. "AVLTree::iterator"->
"typename AVLTree::iterator"), "const_iterator", "reference",
"const_reference", "value_type", "size_type".
So it compiles under VS 2005.
|
|
|
|
|
I downloaded the source files at top of the article, but it only has base_iterator.h and avltree.h... where are all the index_* classes?
thanks,
Matias
|
|
|
|
|
They are at the end of the avltree.h file. These are template classes so they don't need a source code file. Just include the header in your code and declare the class as an instantiated template.
|
|
|
|
|
Sometimes can be useful to know the index where new elements are inserted or elements are found. Some overloaded member functions find() and insert() can be easily implemented based on the provided functionality, for example for index_set:
template<class T, class Cmp>
index_set<T,Cmp>::const_iterator index_set<T,Cmp>::find(const T& item, unsigned long& index) const
{
AVLNode<T>* pos = Find(item);
if(!pos)
pos = _endnode;
index = pos->GetIndex();
return AVLTree_Iterator(*this, pos);
}
template<class T, class Cmp>
std::pair<index_set<T,Cmp>::iterator,bool> index_set<T,Cmp>::insert(const value_type& item, unsigned long& index)
// Inserts an item into the set. Returns end of sequence and false if the item is
// already in the set, otherwise returns a pointer to the item inserted and true.
{
AVLNode<T>* pos = Insert(item);
index = pos->GetIndex();
bool found = (pos ? true: false);
return std::make_pair(AVLTree_Iterator(*this, pos), found);
}
|
|
|
|
|
Interesting extensions to the standard library. I must point out that the GetIndex() function does not work for the _endnode marker, so you must check for that condition. What is 'index' set to when the item is not found or cannot be inserted? Perhaps -1?
I think the conventional way to get the index is to take the iterator returned by both find() and insert() and subtract it from the beginning of the container, like so:
index_set<T> myset;
index_set<T>::iterator at;
unsigned index;
at = myset.insert(T()).first; (or at = myset.find(T());)
index = myset.begin() - at;
This should give you the 0-based index. If the function fails, at is set to myset.end() and index will be the total size of the container, so this condition must still be checked for.
But I have also noticed a bug in my code as well. The insert function won't work this way for set and map if the item cannot be inserted. This is because the end maker must point to _endnode. My last line of the insert function should read:
return std::make_pair(AVLTree_Iterator(*this, (pos ? pos : _endnode)), found);
I will upload a corrected version of the code when I get a chance.
Ray
|
|
|
|
|
I tried your suggestions and everything is fine, exept that instead of:
index = myset.begin() - at;
it should be:
index = at - myset.begin();
See the following example code:
//Some Testing Code
#include "avltree.h"
#include <iostream>
using namespace std;
int main()
{
index_set<int> oSet;
oSet.insert(11);
oSet.insert(17);
oSet.insert(5);
oSet.insert(3);
oSet.insert(9);
oSet.insert(15);
oSet.insert(101);
oSet.insert(97);
oSet.insert(91);
//List Contents
index_set<int>::const_iterator it = oSet.begin();
while(it != oSet.end())
{
cout << *it << endl;
it++;
}
//Check Index Operator
cout << endl;
cout << "[7] = " << oSet[7] << endl;
//Test find with index
cout << endl;
it = oSet.find(15);
if(it != oSet.end())
{
unsigned long index = it - oSet.begin();
cout << index << endl; //should be 4
}
//Test insert with index
cout << endl;
pair<index_set<int>::iterator, bool> pr = oSet.insert(93);
if(pr.first != oSet.end())
{
unsigned long index = pr.first - oSet.begin(); //should be 7
cout << index << endl;
}
return 0;
}
Thanks!
|
|
|
|
|
>>I tried your suggestions and everything is fine, exept >>that instead of:
>>
>>index = myset.begin() - at;
>>
>>it should be:
>>
>>index = at - myset.begin();
You are correct. My mistake. Glad the suggestion worked out.
Ray
|
|
|
|
|
I tried the sources on linux, gcc 3.0.1..
first I needed to do some adjustments in sources in order to make it work..
I made 3 classes, 1 std::map, 1 indexed_map, 1 std::hash_map, each inserted with 1000000 elements, key type of long int, value type of my class A (consists of int, char, std::string).
I run tests, where I was generating random numbers using random() which was my key and I read the data from containers using at() or find() methods.
Filling the index_map was a little faster than filling std::map but a lot slower than filling std::hash_map.
Finding an element in index_map was slower (about 1.3 times slower) than finding an element in std::map and about 5 times slower than finding and element in std::hash_map.
|
|
|
|
|
This results are absolutly obvious. std::hash_map works faster then std::map because it uses hash table algorithm that has O(1) time estimation for search|add|delete operations, while map uses "red-black tree" data structure that has O(log N) for this opearions, but it has a capability to store data in sorted order while hash_map could not. And in conclusion the "red-black tree" is the fastest structure in general case from the all wide balanced trees structures.
|
|
|
|
|
I use an AVL tree for this implementation. If your point is that a red-black tree is faster than an AVL tree, my research indicates that they are essentially the same average speed. But these containers could be just as easily implemented with a red-black tree. It's just a matter of choice.
The unique thing about it is that I have added fast indexing capability to the tree, which is not possible for a normal tree structure and has no meaning for a hash-map. So until someone does this with a red-black tree instead of AVL, its the best one here .
Ray
|
|
|
|
|
By the way, Red black tree in fact is AVL tree, but more advanced. It used the same idea of subtree rotaion, but Red-Black tree is optimized for best perfomance in case of large number of random additions and removing from the tree, because it could be more disbalanced then simple AVL, so it requres less rotations in common case, but could require some much time to search operations it the same time. Anyway the speed diffrence between this realizations is minimal.
|
|
|
|
|
No, AVL-trees are AVL-trees, and RB-trees are RB-trees. Different algorithms, although the same goal. RB-trees are slightly faster than AVL-trees, by a constant factor. The AVL algorithm got its name from its inventors: Adelson & Velskii, and RB-trees got its name from Rudolf Bayer (Red/Black was no coincidence )
As the height difference in RB-trees may be at most 1 as in the AVL case, there is a not much of a difference between AVL-trees and RB-trees in terms of "optimization".
--
Weiter, weiter, ins verderben.
Wir müssen leben bis wir sterben.
I blog too now[^]
|
|
|
|
|
Oops - I didn't see you were replying to another message (dumb webmail system). My reply should have been to m.
Ray
|
|
|
|
|
|
A bundled example would be useful here. For instance, in using the index_map instead of plain old map I can theoretically now iterate through the map using [] instead of an iterator, right? If this is the case, how do I determine the size (number of entries in the map)? I just started looking at this and didn't immediately see how to use it.
Thanks,
Matt
|
|
|
|
|
These classes will not be very useful to you until you have knowledge of the STL container interfaces. I suggest you read a tutorial on the original containers list, set, and map in the standard library. You will find, for example, that the standard function for finding the total number of items in any STL container is to use the size() function.
As a side note, you should not use the array operator [] to iterate through any container. The STL provides iterator classes for that. The array operator is for random access at a particular indexed location.
Ray
|
|
|
|
|
One of STL's more important features is algorithms, which ought to be used whenever possible, with few exceptions. This is something overlooked by many C++ programmers, even experienced ones, mostly due to lack of insight on how efficient algorithms can be.
An article well worth reading was written by the 'guru' Scott Meyers on the subject: STL Algorithms vs. Hand-Written Loops (C/C++ Users Journal, October 2001).
|
|
|
|
|
Hi Ray,
I see you updated your article... can you post the changes? anything worthwhile?
¡Adiós!
|
|
|
|
|
(Re-post of private email)
Just a few bug fixes with the iterators. See the revistion history in the source file.
Ray
|
|
|
|
|
Ray,
Are you familar with Boost.org? This is an open-source project creating libraries for C++, much like CodeProject, except everything is generic C++ (no MFC) and it's seriously peer-reviewed.
Their goal is to create libraries which may one day be added to the Official C++ Standard (many of Boost's founders are committee memebers).
Since extensions to the STL such as yours are very much a part of what they do, they may be interested in your contributions.
Truth,
James
|
|
|
|
|
(Re-post of private email)
Yes, I know about Boost and would love to contribute, but I don't have time to do all the documentation and test examples that they require. If anyone wants to submit my code for me and add their name to the credits be my guest.
Ray
|
|
|
|
|
Hi!
Your stl-style wrapper of the AVL tree is just what i'm looking for. But I'm testing your index_map class, and I found a little detail:
int main(int argc, char* argv[])
{
std::map<DWORD,DWORD> a, b; // this line works
//index_map<DWORD,DWORD> a, b; // this line blows!
a=b;
return 0;
}
I guess the map needs an assigment operator.:(
|
|
|
|
|
Oops! I guess I don't copy containers very often. I have just uploaded an update with assignment operators. Consequently, there were also bugs in the copy constructor and swap function of the sorted container base class. I'm glad you caught it before too many downloads.
Cheers,
Ray
|
|
|
|
|
|
|
 General  News  Suggestion  Question  Bug  Answer  Joke  Rant  Admin
|
Source code for STL compliant container classes that add fast indexing capability to existing container types
| Type | Article |
| Licence | CPOL |
| First Posted | 6 Mar 2001 |
| Views | 166,043 |
| Downloads | 1,206 |
| Bookmarked | 37 times |
|
|
Submit an article or tip
Post your Blog
