C++ 常見STL容器概述

發表於 更新於

在C++中，我們常常會使用Container來存儲資料，而Container分為三種

  • Sequence Container
  • Associative Container
  • Container Adapters

    在這裡簡單介紹一下他們的特性，暫不包括method以及使用範例的部分

Sequence Container

  • 這類的容器資料是有序存放的
  • 常用範例如Vector、Deque、List

Vector(常用)

  • 類似一個動態大小的陣列
  • 支援隨機存取
  • 保證記憶體空間連續 (可善用Spatial Locality)
  • 雙頭皆可加入元素，且加入與刪除的複雜度其平攤成本均為O(1)
  • 相比於Deque，insertion in rear在速度上更有利
  • 一般建議除非很清楚知道使用其他結構的原因，不然建議使用Vector

Deque

  • 又名double-ended queue
  • 跟vector很像，但是不保證記憶體空間連續
  • 相比於Vector，insertion in front在速度上更有利

List

Associative Container

  • 這類容器中的元素無序存放，但通常元素之間有對應關係
  • 常用範例如Set、Multiset、Map、Multimap

Set

  • 如數學集合定義，集合內同樣的元素只允許存在1個，若是重複加入同樣元素則會被忽略

Multiset

  • 這類集合允許重複的元素存在於集合中，這個結構會追蹤各個元素有幾個

Map

  • 又名Associative Array
  • 有點像Python的基本字典，一次插入是一對key-value

Multimap

  • 有點像python裡面的字典，不過每組value都是一個list(multiple values for the same key)
  • 當用一個key搜尋的時候，得到一個包含所有值的container

Container Adapters

  • 一種介面，用於放在一個Container之上，用於限制他的方法
  • 比如我們會用Stack adapters型態宣告Deque Container，限制Deque的功能，讓他表現得像Stack
  • 常見範例如Stack、Queue、Priority_queue

Stack

  • LIFO access
  • 通常架在Deque上

Queue

  • FIFO access
  • 通常架在Deque上

Priority_queue

  • 插入的元素按照所決定的優先順序(優先取最低值)排列，其餘表現同queue
  • 內部通常是用heap實作，所以通常架在vector上面

以上是比較常用的一些STL容器以及相關介紹，更多的內容(物件的方法、複雜度等等)可以到這裡翻閱