[Gambas-user] Data Structures like C++

[Emil Lenngren]

Sometimes linked list are used to manipulate data in the middle of the list
(insertions, removals), then arrays are too slow. O(1) vs O(n). However, a
linked list is very easy to implement in Gambas, using object references.

Sometimes (ordered) sets are used by the fact that they are ordered. Then
gambas collections won't work, since they are unordered. Same thing with
maps/multimaps.

A priority queue can easily be written in Gambas using an array as backend.
Or, simply use an ordered tree instead (the first/last element is always
the one with highest priority...)

I agree that Tree would be the most interesting data structure to be
implemented in C ;)
Red-black trees are very efficient and useful but is quite complicated to
write, so a C implementation would be nice, even if it could be written in
Gambas.

/Emil

2012/5/21 Benoît Minisini <gambas at ...1...>

> Le 21/05/2012 21:51, Demosthenes Koptsis a écrit :
> > Basic languages have simple data structures like vars and arrays but
> > other languages
> > like c++ with the help of pointers can have advanced data structures
> > like containers etc...
> >
> > see a full list here
> > http://en.wikipedia.org/wiki/List_of_data_structures
> >
> > i wonder if such data structures can be implemented with gambas with
> > pointers and if such an action have any mean for real life
> > applications?
> >
> > Is it possible to have such data structures in gambas?
> > How about some of these to be part of the core libraries?
>
> Some data structures are missing, but not so many as you may think at
> first sight.
>
> If they are implemented, I don't think they will go inside the
> interpreter, to keep its size small (it is already too big for my
> tastes), but in an extern component.
>
> * Map/Associative array/Dictionary
> * Hash
>
> Use a Collection in both case. If the key is not a string, you must find
> a way to identify your key with a unique string.
>
> * Multimap
>
> Use a Collection whose values are arrays.
>
> * List
>
> Use an array. Since CPU have now one, two, three... memory caches,
> arrays as almost always faster than linked lists.
>
> * Set
>
> One could use a Collection to emulate it: by transforming a value into a
> string key, we can assume that the value belongs to the set if the
> collection has something associated with the key.
>
> But it would be better to add a Set native class with a native
> implementation (in C. Stop with C++!).
>
> * Multiset
>
> Same remarks (the value is associated to its number of occurence in the
> collection).
>
> * Priority queue
>
> Is it worth having a native implementation for that? I don't think so. A
> implementation in Gambas should be enough.
>
> * Queue
> * Deque
> * Stack
>
> Use an Array. The Push() and Pop() methods can help.
>
> * String
>
> We have strings of characters. Is something else really needed?
>
> * Tree
> * Graph
>
> Native implementation of that would be interesting.
>
> Any volunteer? :-)
>
> --
> Benoît Minisini
>
>
> ------------------------------------------------------------------------------
> Live Security Virtual Conference
> Exclusive live event will cover all the ways today's security and
> threat landscape has changed and how IT managers can respond. Discussions
> will include endpoint security, mobile security and the latest in malware
> threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
> _______________________________________________
> Gambas-user mailing list
> Gambas-user at lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/gambas-user
>