Raised This Month: $ Target: $400
 0% 

[STL] adt_* (travtrie, deque, queue, stack)


  
 
 
Thread Tools Display Modes
Prev Previous Post   Next Post Next
Author Message
Twilight Suzuka
bad
Join Date: Jul 2004
Location: CS lab
Old 03-23-2008 , 01:51   [STL] adt_* (travtrie, deque, queue, stack)
Reply With Quote #1

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!
Attached Files
File Type: inc adt_travtrie.inc (5.0 KB, 268 views)
File Type: inc adt_queue.inc (1.4 KB, 272 views)
File Type: inc adt_deque.inc (11.0 KB, 266 views)
File Type: inc adt_stack.inc (1.2 KB, 256 views)
__________________

Last edited by Twilight Suzuka; 03-23-2008 at 06:36. Reason: Enhanced
Twilight Suzuka is offline
Send a message via AIM to Twilight Suzuka Send a message via MSN to Twilight Suzuka
 



Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -4. The time now is 21:48.


Powered by vBulletin®
Copyright ©2000 - 2024, vBulletin Solutions, Inc.
Theme made by Freecode