Containers in C++ STL (一)

15 Nov 2019 • C++

「工欲善其事，必先利其器。」在開始使用 C++ 解決問題之前，必須先熟悉 C++ 的 containers，這樣才能利用這些 containers 來幫助我們解決更困難的問題。如何使用這些 containers 是基本且無需討論的，自行上網查詢就可以獲得技能，我們討論的將會著重在這些 containers 的差異，以及優缺點和特色。以更高層次的學習 C++ containers 是能夠知道在哪些情境或是場景下，該使用哪個 container，讓我們的學習更貼近真實場景，實際地做出判斷並且解決問題。

Introduction

A container is a holder object that stores a collection of other objects (its elements). They are implemented as class templates, which allows a great flexibility in the types supported as elements. The container manages the storage space for its elements and provides member functions to access them, either directly or through iterators.

C++ containers 基本上分成四大類：

  • Sequence containers
  • Container adaptors
  • Associative containers
  • Unordered associative containers。

還有兩個是特殊 containers : valarray, bitset。

我們將以各種角度來探討分析每個 container 的特性和比較，並且將 member function 分成數類來討論，更能有架構的來學習 C++ containers。

Sequence containers

Sequence containers implement data structures which can be accessed sequentially.

In computing, sequence containers refer to a group of container class templates in the standard library of the C++ programming language that implement storage of data elements.

我們分成 Iterators、Capacity、Element Access、Modifiers、Others 等五大主題來觀察這些 containers 的用法。

Name Brief Iterators Capacity Element Access Modifiers Others
array Static contiguous array begin, end size, empty operator[], at, front, back swap  
vector Dynamic contiguous array begin, end size, empty, capacity operator[], at, front, back push_back, pop_back, insert, erase, swap, clear  
deque Double-ended queue begin, end size, empty operator[], at, front, back push_back, pop_back, insert, erase, swap, clear  
list Doubly-linked list begin, end size, empty front, back push_back, pop_back, insert, erase, swap, clear sort, reverse
forward_list Singly-linked list begin, end empty front push_front, pop_front, insert_after, erase_after, swap, clear sort, reverse

Capacity

在 sequence containers 中，只有 vector 擁有 capacity member function

主要原因是，vector 是個動態長大的 array，為了效率考量，當 push_back 需要新增空間的時候，一次會多要多餘的空間，以備未來有新增 data 的需求。因此你會發現 vector 的 size and capacity 常常是不一樣的，因為他們背後所代表的意義不同：size 是指實際 data 的數量；capacity 是指 vector 所佔的空間，包含預留的多餘空間。

Instead, vector containers may allocate some extra storage to accommodate for possible growth, and thus the container may have an actual capacity greater than the storage strictly needed to contain its elements (i.e., its size). Libraries can implement different strategies for growth to balance between memory usage and reallocations, but in any case, reallocations should only happen at logarithmically growing intervals of size so that the insertion of individual elements at the end of the vector can be provided with amortized constant time complexity

Element Access

vector、array、deque 這三個 container 基本上是以連續的記憶體位置為基礎，因此 support random access，而具體的 member function 就是 operator[], at()。由上述表格可以得知，這三個 container 和 list, forward_list(主要是由 linked list 組成)在 element access 上最大的差異就是「Random Access」。以 Array 為基礎實作的 containers 通常具有「Random Access」的特色；以 linked list 為基礎實作的 containers 則不具備。

No back() member function for forward_list

你可以發現到 forward_list 並沒有 back member function，為什麼呢？主要原因是 singly-linked list push and pop 都是在 front，因此並沒有 data 紀錄 back element，也就無法擁有 back member function。

forward_list objects are thus more efficient than list objects, although they can only be iterated forwards.

Modifiers

Array 基本上不具備 Modifiers functions，因為不需要

array 通常是 compiler time 就決定好空間，不會有 capacity 和 size 不同的問題，因此可以直接修改、新增 element，也就不需要 modifiers functions。你或許會問那為什麼 vector 就需要了呢？主要原因是 vector 的 capacity and size 常常不同，因此需要有 class 包裝 information 讓 user 可以安全的 push back or pop back。

forward_list:push_front() and pop_front()

forward_list 是由 singly linked list 所構成，push and pop element 都是從 head 端，因此 modifiers for forward_list only support push_front and pop_front，如同 there is no back for forward_list。

forward_list:insert_after() erase_after()

forward_list 是由 singly linked list 所構成，因此沒有 previous pointer，只能 insert or erase 在該 element 之後；而一般的 insert and erase 意指 加入或刪除該 element 之前，因此 forward_list 的 insert and erase 才會有 after postfix。

Others:sort()

linked list 並非 random access，因此 list::iterator 並不是 random access iterator，所以無法使用 std::sort。非 random access 的 containers 必須使用該 container class 所提供的 member function，所以你會發現只有 linked list 相關的 containers (list, forward_list)才有 sort。

  1. std::sort needs random access iterator.
  2. linked list based containers can NOT random access.
  3. linked list based containers SHOULD have its own sort member function.

Reference

Sample Code

github : c_plus_plus/Containers/SequenceContainers/

Comments

Related Posts