User:Realazthat/Notes/Containers

• Tries
  • nedtries
  • http://code.google.com/p/patl/
• 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
  • http://www.chiark.greenend.org.uk/~sgtatham/algorithms/revlist.html
  • 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