[Zeex]

This include package is intended to gather and bring you implementations of some common data structures which are useful for a number of applications. Currently not so many of them are supported (make them without pointers and dynamic memory is a little bit hard) but I will update this library whenever I finish implementing a new structure so keep it in mind and check this topic sometimes.

Since I've just recently become interested in this subject and now trying to understand all these things the code may be not the perfect and sometimes a little buggy, though you can report me the bugs you find and I will fix them


At the moment the following structures are provided:

• Doubly-linked linear list - ...
• Red-Black tree (self-balanced binary tree) - http://zeex.pastebin.com/Ec92KMZc
• Hash table (using cuckoo hashing) - ...

All documentation can be found right in the source code. If you have any suggestions feel free to post them here!

[RyDeR`]

Seems very useful. Thanks for sharing.

[Onyx09]

nice job

[Zeex]

Linear list is finally done!
The link updated as well. If you found a bug let me know!

[Zeex]

Added Red-Black trees (http://en.wikipedia.org/wiki/Red-black_tree).

Have fun

edit: now all keys should have RBTreeKey: tag, so you are able to overload operator< if you want all search-related functions to compare keys in different way

[¤Adas¤]

Ehm, what are these functions good for? :/

[Zeex]

Linear list is kind of structure which is supposed to hold some values connected with each other for easy and fast enumeration (remember foreach from Y_Less, it is internally based on linear list) and it take very small (constant) time for element inserting/removal (as there is no need to find free array slot every time because it has a list of free slots), but O(n) in average when searching, so basically LL is bad for lookups.

The binary tree is another kind of a linked list and more complicated. It is also good for inserting/deletion but VASTLY faster on element retrieval - it takes O(log n) in the worst case if a tree is hardly balanced and O(n) if not. For example, imagine you have an array of 1000 elements and you need to find that one located somewhere at 500th slot; if you search for it linearly, one by one, you must pass though 499 elements before you succeed; but if you use binary tree, you will find it at most in 9 steps! So what is better?

Also take a look at these links, Y_Less said a few words on this subject in his Code Optimisations topic:
http://forum.sa-mp.com/index.php?top...0.0#post_lists
http://forum.sa-mp.com/index.php?top...0.0#post_trees

and these too:
http://en.wikipedia.org/wiki/Linked_list
http://en.wikipedia.org/wiki/Binary_tree

[¤Adas¤]

Oh, thanks. I am not a mat genius, but I can understand around 85%