[C++] A thread-Safe Bounded Queue Based on STL Container and C++11 Threading Library

要寫一個平行化的程式通常多半免不了需要一個 thread-safe 的 container，很不巧的是 STL 並沒有提供一個 thread-safe 的 container。雖然通常純讀不修改多半是可以 thread-safe，但如果要允許同時可讀又可寫就需要自己想辦法了。

這篇就是自己想辦法用 STL 的 container 生了一個 thread-safe 的 bounded queue。用 STL container 當基底純粹是因為我懶得自己做記憶體管理 XD

基本想法其實滿單純的，先利用 std::vector 生出一個固定大小的 array，隨後利用兩個 pointer：一個 head 指到第一筆資料；一個 tail 指到最新加入的一筆資料，這樣只要管控這兩個 pointer 基本上就能達到目標。不過可惜的是原本希望能做到 lock-free 的設計，但就現階段來說利用 STL container 我還想不到怎麼做才能 lock-free。

達到 lock-free 的一個重點就是必須要確保下面的操作是 atomic：

1. 更新 head / tail
2. 更新 container 中的資料

1 & 2 這兩件事情中間不能有其他 thread 來搗亂，一旦其他 thread 有可能在中途參與就無法確保資料的正確性 (因為會有 data race)。

所以就結論來說要達到 lock-free 目前只想得到自己寫 container 的方法。雖然是辦得到，不過 memory management 我想用 smart pointer 來協助。不過目前直到 C++17 的 smart pointer 都沒有 thread-safe 的版本 (std::shared_ptr 的 control block像是 reference counter 是 thread-safe，但它自身不是)。要有 thread-safe 的 smart pointer 要等到 C++20 才會提供 (有 std::atomic_shared_ptr 及 std::atomic_weak_ptr)

github page
不過上面的實作我把 head 跟 tail 弄相反了 XD