C++

TL;DR 本篇筆記主要是介紹 C++ 中 STL 函式庫的 iterator_traits。平常用到這個功能的地方應該比較少，但如果需要寫自己的容器並希望它能與 STL 的 <algorithms> 函式庫一起使用的話可能就會需要用到。 前言: 什麼是迭代器 (Iterator) 簡介 本篇筆記要介紹的重點並不是迭代器，故這邊只做非常簡短的介紹。 在 STL 中，迭代器對於不同種類的容器中的元素，提供了一種統一的操作方式，包含了遍歷、取值等操作，讓我們能夠在不知道容器內部實作細節的情況下，對容器內部的元素進行操作。 我們可以將迭代器理解為容器與 STL 種演算法函式庫之間的溝通橋樑：容器不需要知道有哪些演算法，而演算法也不需要知道容器內部的具體實作。 ref: Back to Basics: Classic STL - Bob Steagall - CppCon 2021 迭代器分類 迭代器是透過其所能進行的運算進行分類，而其分類方式類似於下圖中的階層結構，在圖中上方的迭代器能夠進行的運算，圖中下方的迭代器也要支援。 舉例來說，輸入迭代器 (Input Iterator) 支援箭號運算子 (->)，則圖中除了輸出迭代器 (Output Iterator) 以外的其他迭代器同樣都支援箭號運算子 (->)。 這樣的分類方式對於使用迭代器的演算法在實作上有很大的幫助，此筆記後面會做更詳細的介紹。 而迭代器主要分為以下幾類 輸入迭代器 (Input Iterator) 讀取，但不寫入; single-pass，僅遞增。 istream_iterator 詳細內容可參考 cppreference: LegacyInputIterator 輸出迭代器 (Output Iterator) 寫入，但不讀取; single-pass，僅遞增。 ostream_iterator 詳細內容可參考 cppreference: LegacyOutputIterator 正向迭代器 (Forward Iterator) 讀取及寫入; multi-pass，僅遞增。 forward_list 詳細內容可參考 cppreference: LegacyForwardIterator 雙向迭代器 (Bidirectional Iterator) 讀取及寫入; multi-pass，可遞增及遞減。 list, set, map 詳細內容可參考 cppreference: LegacyBidirectionalIterator 隨機存取迭代器 (Random-Access Iterator) 讀取及寫入; multi-pass，可隨機存取。 array, vector, deque, string 詳細內容可參考 cppreference: LegacyRandomAccessIterator iterator_traits 簡介 什麼是 iterator_traits iterator_traits 是一個模板結構 (Template struct)，它主要目的是以一種統一的方式，提取迭代器的型別，如值的型別 (value_type)、差值型別 (difference_type)、迭代器分類 (iterator_category) 等。...

TL;DR 在上一篇 std::unique_ptr 的筆記中，已經簡短介紹智能指標的目的及用法。 在本篇筆記中，會逐步介紹 std::shared_ptr 的基本概念、用法、及簡易實作。 shared_ptr 簡介 與 unique_ptr 類似，shared_ptr 也是 C++11 中引入的一種智能指標，其目的是為了減少記憶體流失 (Memory Leak) 的風險。 與 unique_ptr 不同的地方在於，shared_ptr 允許多個 shared_ptr 實例指向同一塊動態記憶體。只有當最後一個 shared_ptr 被銷毀或重置後，該記憶體才會被釋放。 shared_ptr 會維護一個引用計數 (Reference Counting) 來管理記憶體的所有權。每當一個新的 shared_ptr 被創建或複製時，引用計數會增加；而當一個 shared_ptr 被銷毀或重置時，引用計數會減少。當引用計數歸零時，表示不再有指標指向該記憶體，此時記憶體將被自動釋放。 引用計數改變的情況 shared_ptr 的引用計數會在創建或被複製時增加，並在銷毀或重置時減少，主要會在以下幾種情況改變： 建構子 (Constructor) 解構子 (Destructor) 拷貝建構子 (Copy Constructor) 拷貝賦值運算子 (Copy Assignment Operator) 要注意的是，移動建構子 (Move Constructor) 及移動運算子 (Move Assignment Operator) 會有所有權轉移的步驟，在轉移後原本的指標會被設定為空指標，所以引用計數並不會改變。 成員變數與控制區塊 (Control Block) shared_ptr 本身除了指向動態記憶體區塊的指標之外，還有另外一個指標指向一個控制區塊 (Control Block)，如下圖所示。其中控制區塊包含以下內容: 引用計數 弱引用計數: 此與 std::weak_ptr 有關，這邊先略過，會在後續筆記中做介紹 其他資料: 包含 Deletor 及 Allocator 等 而控制區塊會在以下幾種情況被建立：...

TL;DR 在 C++ 中，std::unique_ptr 是一種很常用的智能指標 (Smart Pointer)，其主要目的是自動管理動態記憶體，避免記憶體流失 (Memory Leak)。 在本篇筆記中，我會先由記憶體流失及智能指標 (Smart Pointer) 開始簡介，再逐步介紹 std::unique_ptr 的基本概念、用法、及簡易實作。 前言 記憶體流失簡介 如果要用一句話簡介記憶體流失 (Memory Leak) 的話，可以說：「當一個程式中分配的動態記憶體，在使用完畢後並未將其釋放，則會造成記憶體流失，減少可使用的主記憶體容量」。 如以下範例所示： 1 2 3 void func_with_memory_leak() { int* ptr = new int; } 在 func_with_memory_leak() 這個函式中，此函式分配了一塊記憶體，並用 ptr 指向這塊記憶體。當此函式結束後，分配的這個記憶體尚未進行釋放，由於 ptr 這個指標變數的生命週期結束了，導致沒有變數指向這塊已經分配好的記憶體，所以此塊記憶體在整個程式運行期間就沒有辦法進行釋放。 如果只有一小塊記憶體流失的話對整個程式的影響不大，但如果這類函式是放在迴圈當中 (如下列程式碼所示)，或者是需要常常被呼叫的函式中，就很有可能因主記憶體的容量不夠，進而降低電腦的效能。 1 2 3 while (some_condition()) { func_with_memory_leak(); } 因此，若是分配出來的動態記憶體，在生命週期結束後，都要記得進行釋放，如下列程式碼所示： 1 2 3 4 5 6 7 void func_without_memory_leak() { int* ptr = new int; // ... delete ptr; } 另外，使用 exception 時也會造成記憶體流失的風險。如下列程式碼所示，當例外情況發生時，如果在記憶體釋放前拋出了例外，則記憶體可能會無法正常釋放，導致記憶體流失。...