泛型容器慣用法

意圖

建立泛型容器類（向量、列表、堆疊），對它們的值型別施加最小的要求。這些要求只是複製建構函式和非丟擲解構函式。

動機

如果需要真正的泛型容器（如 STL），那麼在 C++ 中開發泛型容器可能會變得很複雜。放寬對型別 T 的要求是開發真正泛型容器的關鍵。有幾個 C++ 慣用法實際上可以實現對型別 T 的“最低公分母”要求。

讓我們以堆疊為例。

template<class T>
class Stack
{
  int size_;
  T * array_;
  int top_;
 public:
  Stack (int size=10)
   : size_(size),
    array_ (new T [size]), // T must support default construction
    top_(0)
  { }
  void push (const T & value)
  {
   array_[top_++] = value; // T must support assignment operator.
  }
  T pop ()
  {
   return array_[--top_]; // T must support copy-construction. No destructor is called here
  }
  ~Stack () throw() { delete [] array_; } // T must support non-throwing destructor
};

除了某些陣列邊界問題外，上面的實現看起來非常明顯。但它很天真。它對型別 T 的要求比實際需要的更多。上面的實現要求在型別 T 上定義以下操作

T 的預設建構函式
T 的複製建構函式
T 的非丟擲解構函式
T 的複製賦值運算子

理想情況下，堆疊不應該在其中構造比對其執行的 push 操作次數更多的物件。類似地，在每次 pop 操作之後，應該從堆疊中彈出並銷燬一個物件。上面的實現沒有做到這一點。其中一個原因是它使用了型別 T 的預設建構函式，這完全沒有必要。

實際上，使用構造和銷燬泛型容器慣用法，可以將對型別 T 的要求減少到以下內容。

複製建構函式
非丟擲解構函式。

解決方案和示例程式碼

為了實現這一點，泛型容器應該能夠分配未初始化的記憶體，並且只在“初始化”每個元素時呼叫一次建構函式。這可以透過以下三個泛型容器慣用法來實現

#include <algorithm>
// construct helper using placement new:
template <class T1, class T2>
void construct (T1 &p, const T2 &value)
{
 new (&p) T1(value); // T must support copy-constructor
}

// destroy helper to invoke destructor explicitly.
template <class T>
void destroy (T const &t) throw ()
{
 t.~T(); // T must support non-throwing destructor
}

template<class T>
class Stack
{
  int size_;
  T * array_;
  int top_;
 public:
  Stack (int size=10)
   : size_(size),
    array_ (static_cast <T *>(::operator new (sizeof (T) * size))), // T need not support default construction
    top_(0)
  { }
  void push (const T & value)
  {
   construct (array_[top_++], value); // T need not support assignment operator.
  }
  T top ()
  {
    return array_[top_ - 1]; // T should support copy construction
  }
  void pop()
  {
   destroy (array_[--top_]);   // T destroyed
  }
  ~Stack () throw()
  {
   std::for_each(array_, array_ + top_, destroy<T>);
   ::operator delete(array_); // Global scope operator delete.
  }
};
class X
{
 public:
  X (int) {} // No default constructor for X.
 private:
  X & operator = (const X &); // assignment operator is private
};
int main (void)
{
 Stack <X> s; // X works with Stack!

 return 0;
}

operator new 分配未初始化的記憶體。它是一種呼叫 malloc 的花哨方法。construct 輔助模板函式呼叫就地 new，進而對初始化的記憶體呼叫複製建構函式。指標 p 應該是在使用 operator new 分配的未初始化記憶體塊中。如果 end 是一個指向容器最後一個初始化元素之後的元素的迭代器，那麼從 end 到 end_of_allocation 範圍內的指標不應指向型別 T 的物件，而應指向未初始化的記憶體。當從容器中刪除元素時，應該呼叫它們的解構函式。如所示，destroy 輔助函式在這裡可能會有所幫助。類似地，要刪除一個範圍，另一個過載的 destroy 函式可以接受兩個迭代器。它本質上對序列中的每個元素呼叫第一個 destroy 輔助函式。

已知用途

所有 STL 容器都採用類似的技術。它們對模板引數型別有儘可能少的限制。另一方面，一些流行的 C++ 庫對可引數化型別的要求比必要的高。

參考文獻

設計異常安全的泛型容器 -- Herb Sutter

更多 C++ 慣用法/泛型容器慣用法

泛型容器慣用法

意圖

動機

解決方案和示例程式碼

已知用途

相關慣用法

參考文獻