User:Realazthat/Notes/Containers: Difference between revisions
< User:Realazthat | Notes
Content added Content deleted
No edit summary |
mNo edit summary |
||
(4 intermediate revisions by the same user not shown) | |||
Line 6: | Line 6: | ||
** google dense_hash_set |
** google dense_hash_set |
||
** gnu hash_set |
** gnu hash_set |
||
** https://launchpad.net/libmct |
|||
**: Similar performance to Google Sparsehash library, but no restrictions |
|||
* [http://stxxl.sourceforge.net/ STDXXL] |
* [http://stxxl.sourceforge.net/ STDXXL] |
||
*: STL Containers for huge amounts of data, uses disk as storage |
*: STL Containers for huge amounts of data, uses disk as storage |
||
Line 11: | Line 13: | ||
** http://www.chiark.greenend.org.uk/~sgtatham/algorithms/revlist.html |
** http://www.chiark.greenend.org.uk/~sgtatham/algorithms/revlist.html |
||
** http://hces.bus.olemiss.edu/reports/hces0603.pdf |
** http://hces.bus.olemiss.edu/reports/hces0603.pdf |
||
* Other |
|||
** [[wp:VList]] |
|||
* Graph |
|||
** Adjacency matrix with O(n + m) init time, O(n^2) space, and O(1) lookup time |
|||
**: http://garryowen.csis.ul.ie/~cs4115/resources/oth7.pdf |
|||
** "Develop a technique to initialize an entry of a matrix to zero the first time it is accessed, thereby eliminating the O(|V|^2) time to initialize an adjacency matrix." |
|||
**: http://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html |
Latest revision as of 01:53, 9 February 2011
- Tries
- Hash tables
- khash
- google dense_hash_set
- gnu hash_set
- https://launchpad.net/libmct
- Similar performance to Google Sparsehash library, but no restrictions
- STDXXL
- STL Containers for huge amounts of data, uses disk as storage
- Reversible Linked List
- Other
- Graph
- Adjacency matrix with O(n + m) init time, O(n^2) space, and O(1) lookup time
- "Develop a technique to initialize an entry of a matrix to zero the first time it is accessed, thereby eliminating the O(|V|^2) time to initialize an adjacency matrix."