Sorting std::unique_ptr in associative containers

在工作時因為 associative container 遇到的 bug。在這裡分享一下 XD

使用 associative container 做 resource management

在撰寫管理元素，作為集合功能的物件時，為了 resource management，會讓元素以 unique_ptr 被 Collection 所有。與 Collection 互動的其他結構，可以呼叫它提供的 API 來操作裡頭蒐集的物件。另外為了方便加入與刪除，會使用 associative container （例如 std::set 或是 std::map ）。

template<T>
class Collection {
public:
  using CollectionT = std::set<std::unique_ptr<T>>;
  using iterator = CollectionT::iterator;
  using const_iterator = CollectionT::const_iterator;
public:
  iterator begin();
  iterator end();
  const_iterator begin() const;
  const_iterator end() const;
  const_iterator cbegin() const;
  const_iterator cend() const;  
private:
  CollectionT collection;
public:
  /* more utilities ... */
};

為了讓 Collection 與 STL container 一樣可以使用 range-based for ，因此會幫它 overload iterator 們。這時 Collection 作為 STL container 的 wrapper 之後，不小心就讓錯誤發生了！

造成 Non-deterministic 的執行結果

使用 Collection 的人如果下意識覺得這是一個 sequential container，假設 container 是照著「固定的順序」來遍歷在裡頭的物件。這時 std::set 持有 unique_ptr ，會使得它根據記憶體位置大小來排序。而這件事情會讓程式執行變成 non-deterministic ，因為配置記憶體位置是由作業系統來負責，在不同的環境之下會產生不一樣的結果。

檢討

有 bug 就代表寫出來的 code 不足以表達所有資訊，造成合作之間的誤會。當然要來檢討一下。

提供順序性。為 collection 構造 compare class 即可。不過要注意的是，如果你為底下的物件 class T 去構造比較函數的話不會有效果，因為容器持有的物件是經過 std::unique_ptr wrapper 的物件。因此做 template specialization 時要比較的是 unique_ptr<T>。

以下以 int 作為舉例。這樣就可以為持有 unique_ptr 的 associative container 構造順序性了。有辦法構造順序性，就可以依據底下元素的特性來排序，避免容器使用記憶體位置來排序。

template<> struct std::less<unique_ptr<int>>
{
  bool operator()(const unique_ptr<int>& a, const unique_ptr<int>& b) const {
    return *a < *b;
  }
};

改進命名。class 會在最剛開把使用到的容器以及型態做 type alignment。但是上面那個例子中，命名為 Collection 並不適當。因為他沒有表達這個容器是 sequential 還是 associative。簡單的命名為 SetT 都會比較好，至少使用者可以馬上知道現在操作的容器為 std::set，而不會有剛剛誤用成 sequential container 的事發生。

檢討的檢討

不過這裡要繼續討論下去。剛剛的檢討中提出了兩種做法。第一種為了「解決使用者誤會（忘記）這是一個 sequential 容器」而改變了底層容器的構造。這其實是一種 XY Problem。為了解決「想要以固定（deterministic）的方式存取該集合內的物件」而改變原本單純作為「集合」的物件，額外定義出「順序性」。為了解決 high-level 使用上的問題而更動了 low-level 處的內容。這樣是倒因為果，並不是一個好的作法。

從 top-down 的角度來說，責任歸屬並不應該那麼快交給 Collection 物件來處理。而是對順序性有需求的使用方來做。在取得所有物件之後，使用者再自己做排序就好。這應該是修改起來最快速也能夠使影響到的程式碼盡量少的情況。

從 bottom-up 的角度來說，我覺得原本在構造 associative container 時，就應該要意識到是以記憶體位置來作為順序，而使用者或許會有 sequential access 的需求，直接根據 unique_ptr 底下包裝的物件來做比較來使得順序是固定的。如果試問，使用者需要多於一種的順序性怎麼辦？或許這時可能要換個角度思考，為什麼對單一物件有多重屬性，是不是應該區分成兩種物件。

最後附上剛剛提到 overloading 的 code snippet。

Original link: eopXD