[C++] Branchless Singly Linked List

最近同事分享了一個一小段在新增 node 到 singly linked list 時不用判斷 head/tail 是否為 nullptr 的寫法，因為滿有趣的，所以分享一下

[python] Record Function Call

最近因為需要在程式中埋下紀錄使用者過程中用到了那些 function，這樣方便日後追蹤重現結果。當然最簡單的方法是在每個 function 內都明確地用 logger 之類的寫進 log 裡，不過 python 有更簡單更不容易出錯的方式可以達到效果，因為用 logger 很容易在未來程式改版時有所疏漏。

方法基本上有三種：proxy, build-in __getattribute__(), decorator

[C++] Metaprogram for Getting Bit Size & Converting to Power of 2

大家有沒有遇過這種狀況呢? 一些資料結構 (ex: heap, binary tree) 的節點數量往往是 2 的冪次方 - 1；或者是為了程式效率，把陣列或是 struct 的大小設定成 2 的冪次方。以往在寫這類數值時通常會利用 #define 或者是 constexpr 等等之類的方法把這種數值變成某個有意義的變數，像是這樣：

constexpr int BITSIZE = 10;
constexpr int BUFSIZE = 1024;

但這種時候會遇到一個小麻煩：開發過程中為了程式效率會常常調整這些數值，所以為了盡可能減少錯誤會有各種方式來做這些基礎設定。比方說 BUFSIZE 就可以改成 (1 << BITSIZE) 來避免改了 BITSIZE 忘記改掉 BUFSIZE。

當然，現在 compiler 已經很厲害了，如果某些基礎設定值在編譯期 (compile-time) 就是常數，現在也有不少方法可以讓後續的衍伸運算也都變成編譯期的常數，從而減少執行期的時間。這篇文章要做的主要是介紹用 metaprogramming 把這些運算通通轉成編譯期的常數。

[C++] Partial Template Specialization of class Member Function

事情是這樣的，有人問我他想做到這件事：

enum class Enum {A, B, C ... };
template <Enum E, int N>
struct MyStruct {
    void func();
};

template <int N>
void MyStruct<Enum::A, N>::func() {...}

看完後我就說了，你想做的事 function 的偏特化，這在 C++ 是不被允許的，所以當然會編譯失敗囉
當然，下一個問題就是：那要怎麼做?

以下提供幾個方法 (先不考慮整個 class 重構把 template argument 拆掉) 

[Python] Use String As Variable Name

最近做的東西有個需求有點特別，在程式跑的過程中會在某一步讓使用者可以看看目前有哪些變數他可以用，然後讓他選擇要抓哪個變數出來做後續處理，概念上有點像是 gdb 的 info variables。

然而這就表示我們程式中會需要接受一個使用者輸入的字串當作 key 去存取變數，所幸程式是用 python 寫的，所以類似的方法不難做。

[C++] Error Out Calling Overloaded Function with Type Conversion

故事的情境是這樣的：

某支 function 的設計，假設叫 func 好了，他只有一個參數 param，但是 param 有多種可能的型別，比方說 int, bool, ... 等等，根據不同的型別實作上會稍有不同，為此根據 param 的不同型別提供不同的 overloading 實作，讓使用者可以無需顧慮型別問題。

問題是，當今天使用者傳進 param 的型別，假設是 char，根據預期應該要去呼叫對應到 char 的實作，但是目前的實作中並沒有提供，理想上是應該對此另行提供一個符合 char 的實作，然後根據 C++ overloading resolution 的機制，此時會去呼叫 param 型別是 int 的實作從而導致可能有非預期的結果。

理想上此時應該在開發階段時就以某種方式告知開發者此處有缺漏須補足，但，該怎麼做?

[C] Implement SHA-1

最近因為工作需要把一串字串經過處理後變成另一個長度最多 48-byte 的唯一的字串，能做到這類事情理所當然地就會往 MD5、SHA-1 這類 hash function 去找，而且因為不是要用作加密金鑰，對於安全性的要求並不高，所以後來就選了 SHA-1 當作目標。

實際看了下演算法，其實超簡單的...雖然會有一些細節要特別注意，但整體上的實作相當容易。以下就一一說明要注意的細節，C code 就放在最後面供參囉。

[C++] Calling Unexpected Member Function when The Version of Library Header File is Older Than Shared Library

同事最近遇到一個神奇問題，簡單來說就是他修改了一個會 release 給客戶或其他產品的 library，在裡面新增了一個 API。但照理說這個剛 release 的 API 還沒有人用到才對，卻在一系列的 regression 中發現它竟然被 call 到，而且造成程式 crash?! 從此展開他的 debug 之旅...

[C] Alignment Via Bitwise Operations

有時候會因為 performance / memory access 等等考量需要把不足 4/8 bytes 的資料 align 到 4/8 bytes，做法很多個，這邊列個最近看到的作法以資紀錄。

[C++] Difference between Pointer and Array

C 的兩個型別：array & pointer 大概是觀念上最常被誤解誤用的型別了吧，雖然很多書上、文章裡也很常看到強調這兩個型別不同，不過因為 compiler 在某些情況下會把 array 退化成 pointer，也因此初學者分不清這兩個好像也滿正常的，畢竟差異的細微之處就算有一定經驗也不一定能說得很清楚。

這次剛好有人問了一個問題就是犯了 array 跟 pointer 型別混用、再加上用了 extern，連鎖效應導致遇上 segmentation fault。後來想想搭配圖跟轉出 assembly 或許比較容易了解那細微的不同之處吧。

[C++] Easy Way to Apply Producer-Consumer Parallelism

事情是這樣的，最近接到要把原本的架構套用 producer-consumer 的方式：一條 thread 產生資料、另一條 thread 處理資料 (當然，這邊只是為了方便討論所以都先假定各一條 thread)，以此增加平行度。不過雖然這種方式很常見，要在原本沒有規劃的程式上套用起來還是會改動不少地方，而且為了讓處理邏輯比較獨立、清晰，就想了個方法讓這些改動可以儘可能的集中、且只需要儘可能少的修改現有邏輯。最後最重要的是：想要撤銷 producer-consumer 變回原本 sequential 的架構時也儘可能的簡單，換句話說：能輕易套用不同的資料處理模式。

[C++] Compile Time if in C++17

要說的話...就是把原本要用 SFINAE (substitution failure is not an error) 才能做到的事情變成可以用更直覺的寫法來做到。

[C++] Mandatory Copy Elision in C++17

一言以蔽之：以前 compiler 幫你做的最佳化現在直接在標準裡規定一定要有。

[C++] inline Variable and thread_local in C++17

inline variable 最大的用意應該就是允許在 header 就把變數的宣告 + 定義一次搞定吧。在 C++17 前除了少數特例 (比方說 literal type)，基本上 header 只能放宣告，明確的定義是必須要放在單一的 translation unit 以遵守 ODR (one definition rule)。

[C++] Structure Binding in C++17

用一句最簡單的畫作結論的話就是語法糖

C++11 開始除了一些新觀念的引進 (比方說 move semantic) 之外，類似的語法糖也增加了不少，經典例子就是 lambda expression。而 structure binding 到底是啥呢? 舉個簡單例子：

std::pair<int, double> ms{1, 3.14};
auto [i, d] = ms;

一個很樸實無華但是稍微可以讓你的 code 更簡潔易懂的東西。

[Python] Dangerous default value

最近跑 pylint 時偶然發現了一個 warning 叫 "Dangerous default value as argument"，細追之後才發現一個陷阱

[程式] codeforces 1321C: Remove Adjacent

[題意]

給一個由小寫字母組的字串 s (長度介於 1 ~ 100)，每次你可以從 s 中刪掉一個滿足特定條件的字母，問最多能刪掉幾個?

刪除字母的條件：令 s[idx] 為 s 的第 idx 的字母。若 s[idx - 1] 或 s[idx + 1] 的字母其字母順序 (令字母順序為 a -> b -> c -> ... -> x -> y -> z) 在 s[idx] 的字母順序的前一個，則我們可以刪掉 s[idx]

[C] XOR linked list

一言以蔽之，這是個用 single linked list 的架構去做到 double linked list 的效果的東西，主要目的就是為了節省記憶體使用量

[C++] std::stringstream cannot output integral type

這次遇到的問題簡單來說就是不知道為什麼程式的 log 有部分訊息被吃掉，然後整份 log 就此大亂。細追分析後發現我們的 log 會先用 std::stringstream 把使用者傳進來的所有參數 (任意數量 & 型態) 轉成 std::string，隨後才把他輸出到 log file 去，而在 std::stringstream 試圖要處裡一個數值型態的參數時會丟出 exception，雖然會被他自己吃掉不會往上丟，但也導致要處理後面的參數時運作情形就不如預期。

進一步往下追原因的時候發現這其實是所有繼承 std::ios_base 的類別都會有的狀況，原因的話簡單來說就是 std::ios_base 內部會主動去處理 locale 相關問題，在這過程中的檢查出狀況時就會丟出一個 exception，而這個 exception 雖然馬上會被吃掉，但會拉起內部的 badbit，下一次要 output 時因為 badbit 被拉起來了，所以會吃掉丟進來的參數但不會真的印出去。

[C++] Deep into Hash Map in STL: std::unordered_map

std::unordered_map 是 C++11 後 STL 新增的 container，本質上可以想成是一個 hash map。相較於原先的 std::map 基本上是個 red-black tree ， std::unordered_map 的重點在於許多操作的 amortize complexity 基本上是 constant time。只是使用上有些許的重點要注意，不然效能可能會不如預期