 |
|
|
|
|
|
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.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Rant 
Admin