C++關聯容器,STL關聯容器

2020-07-16 10:04:26
關聯容器內部的元素都是排好序的,有以下四種。
  • set:排好序的集合,不允許有相同元素。
  • multiset:排好序的集合,允許有相同元素。
  • map:每個元素都分為關鍵字和值兩部分,容器中的元素是按關鍵字排序的。不允許有多個元素的關鍵字相同。
  • multimap:和 map 類似,差別在於元素的關鍵字可以相同。

不能修改 set 或 multiset 容器中元素的值。因為元素被修改後,容器並不會自動重新調整順序,於是容器的有序性就會被破壞,再在其上進行查詢等操作就會得到錯誤的結果。因此,如果要修改 set 或 multiset 容器中某個元素的值,正確的做法是先刪除該元素,再插入新元素。

同理,也不能修改 map 和 multimap 容器中元素的關鍵字。

關聯容器內部的元素或關鍵字之間比較大小可以用<運算子,也可以用自定義的比較器。因為有序,所以在關聯容器上進行查詢的速度較快。

使用關聯容器的目的也就在於快速查詢。當一個元素被插入關聯容器時,該元素會和已有的元素進行比較,最終被插入一個合適的位置。

在關聯容器中查詢元素和插入元素的時間複雜度都是 O(log(n))。從 begin() 到 end() 遍歷整個關聯容器,就是從小到大遍歷整個容器。

在排好序的 vector 和 deque 上進行折半查詢,時間複雜度也可以是 O(log(n))。但是,對於插入、刪除和查詢交替進行的情況,使用 vector 和 deque 的效率不高。因為它們上面的插入和刪除操作會引起元素的移動,時間複雜度是 O(n)。

關聯容器一般是用平衡二元樹實現的。平衡二元樹的原理屬於“資料結構”課程的內容,本教學不做介紹。

除了所有容器共有的成員函數外,關聯容器還具有以下成員函數:
  • find:查詢某個值。
  • lower_bound:查詢某個下界。
  • upper_bound:查詢某個上界。
  • equal_range:同時查詢上界和下界。
  • count:計算等於某個值的元素個數。
  • insert:插人一個元素或一個區間。