[STL] adt_* (travtrie, deque, queue, stack)
5 Attachment(s)
A few useful stocks until official versions are added. These follow the same format as adt_array and adt_trie (even when I dislike it) just to maintain compatibility.
Deque: Meets all deque requirements for speed, at the sacrifice of space Space grows linearly, but quicker than it could Worst case for space is queue (unfortunately) Queue: Based on deque (soon to be based on circular buffer) Meets all queue requirements for speed Stack: Based on adt_array Meets all stack requirements for speed TravTrie: Based on adt_trie and adt_array Retrieve has no slow down insert has O(1) slow down delete has O(logn) or O(n) slow down constant iteration provided through Plugin Iterator like mechanism iteration occurs in O(n) unsorted, O(nlogn) sorted TravTrie Tripups: 1. Getting the string key (not the value) will not increment the iterator 2. A function is provided to sort the travtrie if wanted Note: These functions have been compile tested and moderately runtime tested, but not stress tested (except for queue and travtrie). Tell me if an error occurs. Please tell me how if you like it! |
Re: [STL] adt_* (travtrie, deque, queue, stack)
Good job. :D
Could you show some examples? |
Re: [STL] adt_* (travtrie, deque, queue, stack)
1 Attachment(s)
(partial) adt_queue implementation based upon my C++ implementation
The SourceMod version is 150-200 times slower than the C++ one (benchmark: (push_back 2k, pop_front 1k, push_back 1k, pop_front 2k)*1k). |
Re: [STL] adt_* (travtrie, deque, queue, stack)
Got any comparisons of mine and yours? I assume yours will beat mine, but my circular buffer one should beat both.
|
Re: [STL] adt_* (travtrie, deque, queue, stack)
yours "crashes"
Code:
L 03/24/2008 - 16:08:24: [SM] Native "SetArrayCell" reported: Invalid index 4224 (count: 1280) |
Re: [STL] adt_* (travtrie, deque, queue, stack)
benchmark:
Code:
public OnPluginStart() { |
Re: [STL] adt_* (travtrie, deque, queue, stack)
sweet googly moogly! Have to look into that.
The cost of the native overhead to just access the members in our fake structs is rather high. Wonder if I could pack the members somehow... |
All times are GMT -4. The time now is 16:01. |
Powered by vBulletin®
Copyright ©2000 - 2024, vBulletin Solutions, Inc.