談 C++17 裏的 FlyWeight 模式 Detail - c++,c++11,c++17,design-pattern,設計模式 hedzr Blog

回顧享元模式，考慮實作它的各種問題。

Prologue

略過

FlyWeight Pattern

理論

享元模式，是將複雜對象的相同的組成元素抽出並單獨維護的一種結構型設計模式。這些相同的組成元素被稱為共享元件，它們在一個單獨的容器中被唯一性地管理，而複雜對象只需持有到該唯一實例的參考，而無需重複創建這樣的相同的元素，從而能夠大幅度地削減內存佔用。

以字處理器為例，每個字符都具有獨立的、區別於其它字符的特殊屬性：例如字體樣式，背景、邊框、對齊等等。如果一個文檔中全部字符都單獨存儲一份它的所有屬性的副本，那麼這將會是龐大的內存需求。但考慮到一大堆（例如1000個）字符可能都有相同的“宋體，9pt”這樣的屬性，那麼實際上我們只需要單獨存儲一份“宋體，9pt”的字體樣式屬性，而一個字符只需要一個指向該字體樣式屬性的指針就可以了，這就比1000個字符的1000個字體樣式屬性拷貝要節約的多。

類似的案例還有相當多，例如例子系統中的每個粒子（例如子彈、彈片，或者敵方飛機）都有一些相同的屬性（例如顏色，輪廓等等）佔地不小，但值卻相同。

工廠模式

很容易想到，我們可以在一個工廠中就地管理享元對象。當客户以具體值來請求一個享元對象時，工廠會從一個字典中檢索享元是否存在，然後返回該元素的參考引用給客户。如果享元尚未存在，那麼工廠會創建它，然後在返回引用。

不可變性

按照傳統的説法，享元模式要求這些相同的部分（享元，相同的組成元素）是不可變的。但這並不是鐵律。

一個方法是，以一個享元為整體，我們可以整體修改對象持有的享元參考。

例如我們正在修改字處理器中的一個單詞的字體樣式，從“宋體，9pt”改為“黑體，12pt”，那麼我們可以直接修改引用指向。也就是説，我們提供 character.apply_font_style(font_style& style) 這樣的整體修改接口。

另一個方法可以從更細的粒度出發進行修改，例如從“宋體，9pt”改為“宋體，10pt”，但在發生變更時，嘗試從工廠中查證新值的參考。也就是説，我們提供 character.set_font_size(float pt) 這樣的接口，但在其實現過程中記得去查證享元工廠（管理器）以求更新內部引用。

C++ 實現

傳統的享元模式的實現方式有這樣的示例代碼：

namespace hicc::dp::flyweight::basic {

  /**
     * flyweight Design Pattern
     *
     * Intent: Lets you fit more objects into the available amount of RAM by sharing
     * common parts of state between multiple objects, instead of keeping all of the
     * data in each object.
     */
  struct shared_state {
    std::string brand_;
    std::string model_;
    std::string color_;

    shared_state(const std::string &brand, const std::string &model, const std::string &color)
      : brand_(brand)
        , model_(model)
        , color_(color) {
      }

    friend std::ostream &operator<<(std::ostream &os, const shared_state &ss) {
      return os << "[ " << ss.brand_ << " , " << ss.model_ << " , " << ss.color_ << " ]";
    }
  };

  struct unique_state {
    std::string owner_;
    std::string plates_;

    unique_state(const std::string &owner, const std::string &plates)
      : owner_(owner)
        , plates_(plates) {
      }

    friend std::ostream &operator<<(std::ostream &os, const unique_state &us) {
      return os << "[ " << us.owner_ << " , " << us.plates_ << " ]";
    }
  };

  /**
     * The flyweight stores a common portion of the state (also called intrinsic
     * state) that belongs to multiple real business entities. The flyweight accepts
     * the rest of the state (extrinsic state, unique for each entity) via its
     * method parameters.
     */
  class flyweight {
    private:
    shared_state *shared_state_;

    public:
    flyweight(const shared_state *o)
      : shared_state_(new struct shared_state(*o)) {
      }
    flyweight(const flyweight &o)
      : shared_state_(new struct shared_state(*o.shared_state_)) {
      }
    ~flyweight() { delete shared_state_; }
    shared_state *state() const { return shared_state_; }
    void Operation(const unique_state &unique_state) const {
      std::cout << "flyweight: Displaying shared (" << *shared_state_ << ") and unique (" << unique_state << ") state.\n";
    }
  };

  /**
     * The flyweight Factory creates and manages the flyweight objects. It ensures
     * that flyweights are shared correctly. When the client requests a flyweight,
     * the factory either returns an existing instance or creates a new one, if it
     * doesn't exist yet.
     */
  class flyweight_factory {
    std::unordered_map<std::string, flyweight> flyweights_;
    std::string key(const shared_state &ss) const {
      return ss.brand_ + "_" + ss.model_ + "_" + ss.color_;
    }

    public:
    flyweight_factory(std::initializer_list<shared_state> lists) {
      for (const shared_state &ss : lists) {
        this->flyweights_.insert(std::make_pair<std::string, flyweight>(this->key(ss), flyweight(&ss)));
      }
    }

    /**
     * Returns an existing flyweight with a given state or creates a new one.
     */
    flyweight get(const shared_state &shared_state) {
      std::string key = this->key(shared_state);
      if (this->flyweights_.find(key) == this->flyweights_.end()) {
        std::cout << "flyweight_factory: Can't find a flyweight, creating new one.\n";
        this->flyweights_.insert(std::make_pair(key, flyweight(&shared_state)));
      } else {
        std::cout << "flyweight_factory: Reusing existing flyweight.\n";
      }
      return this->flyweights_.at(key);
    }
    void list() const {
      size_t count = this->flyweights_.size();
      std::cout << "\nflyweight_factory: I have " << count << " flyweights:\n";
      for (std::pair<std::string, flyweight> pair : this->flyweights_) {
        std::cout << pair.first << "\n";
      }
    }
  };

  // ...
  void AddCarToPoliceDatabase(
    flyweight_factory &ff,
    const std::string &plates, const std::string &owner,
    const std::string &brand, const std::string &model, const std::string &color) {
    std::cout << "\nClient: Adding a car to database.\n";
    const flyweight &flyweight = ff.get({brand, model, color});
    // The client code either stores or calculates extrinsic state and passes it
    // to the flyweight's methods.
    flyweight.Operation({owner, plates});
  }

} // namespace hicc::dp::flyweight::basic

void test_flyweight_basic() {
  using namespace hicc::dp::flyweight::basic;

  flyweight_factory *factory = new flyweight_factory({ {"Chevrolet", "Camaro2018", "pink"}, {"Mercedes Benz", "C300", "black"}, {"Mercedes Benz", "C500", "red"}, {"BMW", "M5", "red"}, {"BMW", "X6", "white"} });
  factory->list();

  AddCarToPoliceDatabase(*factory,
                         "CL234IR",
                         "James Doe",
                         "BMW",
                         "M5",
                         "red");

  AddCarToPoliceDatabase(*factory,
                         "CL234IR",
                         "James Doe",
                         "BMW",
                         "X1",
                         "red");
  factory->list();
  delete factory;
}

其輸出結果如同這樣：

--- BEGIN OF test_flyweight_basic                     ----------------------

flyweight_factory: I have 5 flyweights:
BMW_X6_white
Mercedes Benz_C500_red
Mercedes Benz_C300_black
BMW_M5_red
Chevrolet_Camaro2018_pink

Client: Adding a car to database.
flyweight_factory: Reusing existing flyweight.
flyweight: Displaying shared ([ BMW , M5 , red ]) and unique ([ James Doe , CL234IR ]) state.

Client: Adding a car to database.
flyweight_factory: Can't find a flyweight, creating new one.
flyweight: Displaying shared ([ BMW , X1 , red ]) and unique ([ James Doe , CL234IR ]) state.

flyweight_factory: I have 6 flyweights:
BMW_X1_red
Mercedes Benz_C300_black
BMW_X6_white
Mercedes Benz_C500_red
BMW_M5_red
Chevrolet_Camaro2018_pink
--- END OF test_flyweight_basic                       ----------------------

可以看到，像 [ BMW , X1 , red ] 這樣的一個享元，單個實例較大（數十、數百乃至數十K 字節），而引用參考不過是一個指針的大小（通常是 64 bytes on 64-bit OS），那麼最終節省的內存是非常可觀的。

元編程中的 FlyWeight Pattern

上面的示例，已經是舊風格了，C++11 以後我們需要大量地使用智能指針、以及模板語法，而在 C++17 之後更好的原位構造能力允許我們的代碼能夠更加 meaningful。

flyweight_factory

一個想法是，我們認為一個儘可能通用的享元工廠可能是有利於代碼書寫的。所以我們嘗試這樣一個享元工廠模板：

namespace hicc::dp::flyweight::meta {

  template<typename shared_t = shared_state_impl, typename unique_t = unique_state_impl>
  class flyweight {
    std::shared_ptr<shared_t> shared_state_;

    public:
    flyweight(flyweight const &o)
      : shared_state_(std::move(o.shared_state_)) {
      }
    flyweight(shared_t const &o)
      : shared_state_(std::make_shared<shared_t>(o)) {
      }
    ~flyweight() {}
    auto state() const { return shared_state_; }
    auto &state() { return shared_state_; }
    void Operation(const unique_t &unique_state) const {
      std::cout << "flyweight: Displaying shared (" << *shared_state_ << ") and unique (" << unique_state << ") state.\n";
    }
    friend std::ostream &operator<<(std::ostream &os, const flyweight &o) {
      return os << *o.shared_state_;
    }
  };

  template<typename shared_t = shared_state_impl,
                   typename unique_t = unique_state_impl,
                   typename flyweight_t = flyweight<shared_t, unique_t>,
                   typename hasher_t = std::hash<shared_t>>
  class flyweight_factory {
    public:
    flyweight_factory() {}
    explicit flyweight_factory(std::initializer_list<shared_t> args) {
      for (auto const &ss : args) {
        flyweights_.emplace(_hasher(ss), flyweight_t(ss));
      }
    }

    flyweight_t get(shared_t const &shared_state) {
      auto key = _hasher(shared_state);
      if (this->flyweights_.find(key) == this->flyweights_.end()) {
        std::cout << "flyweight_factory: Can't find a flyweight, creating new one.\n";
        this->flyweights_.emplace(key, flyweight_t(shared_state));
      } else {
        std::cout << "flyweight_factory: Reusing existing flyweight.\n";
      }
      return this->flyweights_.at(key);
    }
    void list() const {
      size_t count = this->flyweights_.size();
      std::cout << "\nflyweight_factory: I have " << count << " flyweights:\n";
      for (auto const &pair : this->flyweights_) {
        std::cout << pair.first << " => " << pair.second << "\n";
      }
    }

    private:
    std::unordered_map<std::size_t, flyweight_t> flyweights_;
    hasher_t _hasher{};
  };

} // namespace hicc::dp::flyweight::meta

然後我們就可以以派生類的方式直接使用這個享元工廠了：

class vehicle : public flyweight_factory<shared_state_impl, unique_state_impl> {
  public:
  using flyweight_factory<shared_state_impl, unique_state_impl>::flyweight_factory;

  void AddCarToPoliceDatabase(
    const std::string &plates, const std::string &owner,
    const std::string &brand, const std::string &model, const std::string &color) {
    std::cout << "\nClient: Adding a car to database.\n";
    auto const &flyweight = this->get({brand, model, color});
    flyweight.Operation({owner, plates});
  }
};

其中 using flyweight_factory<shared_state_impl, unique_state_impl>::flyweight_factory; 是 C++17 以後的新語法，它將父類的所有構造函數原樣複製給派生類，從而讓你不必拷貝粘貼代碼然後修改類名。

在 vehicle 模板類中我們使用默認的 flyweight<shared_t, unique_t>，但你可以在 flyweight_factory 的模板參數中修改它以便提供你自己的享元類具體實現。

測試代碼

void test_flyweight_meta() {
    using namespace hicc::dp::flyweight::meta;

    auto factory = std::make_unique<vehicle>(
            std::initializer_list<shared_state_impl>{
                    {"Chevrolet", "Camaro2018", "pink"},
                    {"Mercedes Benz", "C300", "black"},
                    {"Mercedes Benz", "C500", "red"},
                    {"BMW", "M5", "red"},
                    {"BMW", "X6", "white"}});

    factory->list();

    factory->AddCarToPoliceDatabase("CL234IR",
                                    "James Doe",
                                    "BMW",
                                    "M5",
                                    "red");

    factory->AddCarToPoliceDatabase("CL234IR",
                                    "James Doe",
                                    "BMW",
                                    "X1",
                                    "red");
    factory->list();
}

附加

我們使用了稍稍不同的基礎類 shared_state_impl 以及 unique_state_impl：

namespace hicc::dp::flyweight::meta {
  struct shared_state_impl {
    std::string brand_;
    std::string model_;
    std::string color_;

    shared_state_impl(const std::string &brand, const std::string &model, const std::string &color)
      : brand_(brand)
        , model_(model)
        , color_(color) {
      }
    shared_state_impl(shared_state_impl const &o)
      : brand_(o.brand_)
        , model_(o.model_)
        , color_(o.color_) {
      }
    friend std::ostream &operator<<(std::ostream &os, const shared_state_impl &ss) {
      return os << "[ " << ss.brand_ << " , " << ss.model_ << " , " << ss.color_ << " ]";
    }
  };
  struct unique_state_impl {
    std::string owner_;
    std::string plates_;

    unique_state_impl(const std::string &owner, const std::string &plates)
      : owner_(owner)
        , plates_(plates) {
      }

    friend std::ostream &operator<<(std::ostream &os, const unique_state_impl &us) {
      return os << "[ " << us.owner_ << " , " << us.plates_ << " ]";
    }
  };
} // namespace hicc::dp::flyweight::meta

namespace std {
  template<>
  struct hash<hicc::dp::flyweight::meta::shared_state_impl> {
    typedef hicc::dp::flyweight::meta::shared_state_impl argument_type;
    typedef std::size_t result_type;
    result_type operator()(argument_type const &s) const {
      result_type h1(std::hash<std::string>{}(s.brand_));
      hash_combine(h1, s.model_, s.color_);
      return h1;
    }
  };
} // namespace std

這是因為我們在 flyweight_factory 中使用了 std::hash 技術來管理一個享元的鍵值，所以我們必須明確地實現 shared_state_impl 的 std::hash 特化版本。

而在這個特化版本中我們又利用了一個特別的 hash_combine 函數。

hash_combine

這是一個技術性很強的概念，因為它涉及到了一個神奇的幻數（magicnum）0x9e3779b9。

我們在 hicc-cxx/cmdr-cxx 中提供了一個源於 boost::hash_combine 的同名擴展：

namespace std {
  template<typename T, typename... Rest>
  inline void hash_combine(std::size_t &seed, T const &t, Rest &&...rest) {
    std::hash<T> hasher;
    seed ^= 0x9e3779b9 + (seed << 6) + (seed >> 2) + hasher(t);
    int i[] = {0, (hash_combine(seed, std::forward<Rest>(rest)), 0)...};
    (void) (i);
  }

  template<typename T>
  inline void hash_combine(std::size_t &seed, T const &v) {
    std::hash<T> hasher;
    seed ^= 0x9e3779b9 + (seed << 6) + (seed >> 2) + hasher(v);
  }
} // namespace std

它的作用在於計算一系列的對象的 hash 值並組合它們。

關於如何正確地組合一堆 hash 值，較為簡單地方法是：

std::size_t h1 = std::hash<std::string>("hello");
std::size_t h2 = std::hash<std::string>("world");
std::size_t h = h1 | (h2 << 1);

但仍然有更多的探討，其中得到了公認的最佳手段（C++中）是源自於 boost::hash_combine 實現代碼的一個方法：

seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);

就目前已知的學術研究中，這是最佳的。

那麼誰製造了這麼奇幻的一個神經質數(golden ratio)呢，大體可考的原作應該是： A Hash Function for Hash Table Lookup 或 Hash Functions for Hash Table Lookup 。原作者 Bob Jenkins，原發於 DDJ 刊物 1997 年，代碼大約是成形於 1996 年。而這個數嘛，源於這個表達式：$\frac{2^{32}}{\frac{1+\sqrt{5}}{2}}$ （)。

Epilogue

好，雖然不算太盡人意，但我確實實現了一個 C++17 的勉強比較通用的 flyweight_factory 模板類，就將就了吧。

hedzr Blog

@hedzr

Tags

算法 (135)

c++ (99)

設計模式 (50)

c++11 (23)

c++17 (6)

design-pattern (3)

元編程 (2)

虛函數表 (1)

觀察者模式 (1)

Stories

談 C++17 裏的 FlyWeight 模式 - Stories Detail