Sequence container (C++)
vector (array):索引和遍歷花費便宜,但是要隨機插入或移除其中元素花費較高,需要搬移其中其它元素。
Linked list
:隨機插入或移除其中元素相對於 vector (array) 來說較為便宜。但當資料量不大的情況下,使用 linked list 不會佔到太大便宜。
Simple C++ Linked List
// 單向鍊結串列 (singly-linked list)
typedef
struct
Node
{
struct
Node
*
next
;
int
data
;
}
Node
;
插入或刪除節點
遍歷鍊結串列
Associative containers (C++)
map: 用來儲存 (key, value),以 key 為索引搜尋 map 有效率。
Binary tree
Self-balancing binary search tree
插入或移除樹中節點之後,會藉由樹旋轉將其高度重新調整至最小值,讓左右子樹的高度相差不會超過一。
Unordered associative containers (C++)
使用 hash 來搜尋樹中節點。
Priority queue
B-tree
B+ tree
Computational geometry
Spatial database
spatial index
外部連結
Algorithms and data structures in C/C++