Scalaには興味深いコレクション-Streamがあります。 コンテナ。最初のアクセス時に要素が計算される（そしてその後保存される）リストです：

クラスStreamは、必要な場合にのみ要素が評価される遅延リストを実装します。

C ++で似たようなものを実装したかった。

目的

標準のアルゴリズムで使用できるコンテナを取得して、アクセス時にその要素を生成できるようにします。





例からわかるように、要素生成関数は各要素に対して1回だけ呼び出され、受け取った値はコンテナに保存され、再計算されません。

制限事項

次のようなことをしたいとします：

 auto iter = --list.end();
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

終了前の要素を取得するには、関数によって生成されたすべての要素をバイパスする必要があり、これは無限です（上記の例の場合）。 したがって、遅延リストの反復子は単方向-ForwardIteratorになります。 同様の状況は、リスト内の要素の数を取得するとき、および最後の要素（pop_back）を削除するときです。 したがって、コンテナにはこれらのメソッドはありません。



簡単にするために、私は任意の場所への挿入と任意の要素の削除を実装していません。 何らかの機能によって要素のシーケンスを生成でき、挿入/削除時にこのシーケンスに違反するという理由だけのためです。 同じ理由で、要素は変更できません。 しかし、これは慣例です。

どうしたの？

結果は、遅延リストを生成する要素とファンクターの両方を追加できるリストになり、そのリストに要素とファンクターを含めることができます。 最初の要素（pop_front）またはすべての要素（clear）を削除できます。 要素はリストの最初または最後に挿入されます。



リストイテレータは単方向であり、リストアイテムの変更は許可されません。

 template< typename T, typename Allocator = std::allocator<T> > class list;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

記事の最後にリポジトリへのリンクがあり、ユニットテストで実装を取得できます。

テンプレートパラメータ。

T-保管アイテムのタイプ



アロケーター-要素を配置するために使用されるアロケーター。

内部タイプ

種類	説明
value_type	T
self_type	独自のタイプ
func_type	アイテムの生成に使用されるファンクターのタイプ。 ファンクターはself_typeオブジェクトを返します。
イテレータ	定数順反復子
const_iterator	定数順反復子

方法

方法	説明
push_front	先頭への挿入
push_back	最後に挿入
空っぽ	コンテナが空かどうかを確認する
クリア	すべてのアイテムを削除
pop_front	最初の要素を削除

push_frontおよびpush_backメソッドは、要素、保存された要素の値、またはself_type型の別のオブジェクトを生成するファンクターを受け入れます。

コンストラクター

署名	説明
list();	空のコンテナを作成します
template<typename ... Args> explicit list(Args&&... args)	コンテナを作成し、転送された要素をそれに入れます。 次のタイプの値を転送できます。 value_type func_type self_type

仕組み

内部では、2つの標準コンテナが使用されます。std::値を格納するリストとstd ::ファンクタを格納するマップです。 ファンクターは遅延リスト、つまり self_type。 これにより、必要に応じて一度に複数の要素を一度に計算でき、次に、次の値がない場合を心配する必要がありません-シーケンスが終了しました。この場合、空のコンテナを返すことができます。



新しい要素を追加すると、すべてが簡単になります-すぐに内部リストに追加されます。



ファンクターを追加するとき、追加された要素に関連付けられたファンクターがあるかどうかがチェックされます（push_back）。 ファンクターがない場合、転送されたファンクターがマップに追加され、前の要素へのポインターがキーとして使用されます。 最初、空のコンテナ、または既に関連付けられたファンクターがある要素の後に追加する場合、operator（）ファンクタメソッドが単に呼び出され、結果のコンテナからの値が適切な場所（先頭または末尾）に挿入され、新しいファンクタがマップに追加されます。それらは返されたコンテナにあります。



リストに「値-ファンクター」のペアを格納することは可能ですが、作業の過程でファンクターの数は計算された要素の数よりもかなり少なくなり、ペアを格納する場合のメモリコストは高くなります。

繰り返しますが、ファンクターの数はそれほど多くないと想定しているため、mapを使用するかunordered_mapを使用するかに大きな違いはありません。 唯一のことは、マップを使用すると、メモリコストがわずかに少なくなるということです。



反復子がインクリメントされると、現在の要素のファンクターがチェックされます（チェックされている場合）。それによって返される値がコンテナーに追加され、ファンクターが削除されます。 その後、反復子は内部リストにインクリメントされます。 ファンクターが存在しないか、空のコンテナーを返した場合は、内部リストの次の要素に移動します。

なんでこんなこと？

Scalaの言語講義で発表されたWater Pouringタスクは、そのようなリストを実装するように促しました。 一番下の行は次のとおりです。一定の容積のグラスがいくつかあり、そこからグラスを満たすことができるタップ（グラスを完全に満たすことができます）、グラスの内容物を注ぐことができるシンクがあります。 あるグラスから別のグラスに水を入れ、空にし、注ぐには、グラスの1つに一定量の水を入れる必要があります。 解決策は、そのような状態を取得するための一連のアクションです。



たとえば、3リットルと5リットルのグラスが2枚あり、4リットルを取得したいとします。





各グラスの現在の水の量を条件として考慮します。 各状態から、可能な操作のいずれかを適用することにより、可能な状態の新しいセットを取得できます：fill、pour、pour。 状態の各セットから、新しいセットを取得できます。 循環しないように、受信した状態を個別に保存し、新しい状態のセットを受信すると破棄します。





状態の各セットで、目的の状態（目的の水位を持つグラス）があるかどうかを確認します。



現在の状態に影響を与えるための可能なオプションが必要です。 各水移動オプションは、imoveインターフェイスを継承します。

 class imove { public: virtual state operator()(const state& cur) const = 0; virtual std::unique_ptr<imove> clone() const = 0; virtual std::string to_string() const = 0; virtual ~imove() {} };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

to_string



メソッドは、画面に情報を表示するためにto_string



必要です。



このタスクでは、次のタイプの移動が可能です。









また、新しい状態に関する情報、つまり状態とそれに至る一連の動きを保存する必要があります。 path



クラスがこれを担当します。

 class path { public: path(const state& initial_state); path(const path& that); void extend(imove_ptr move); const state& end_state() const; std::string to_string() const; bool empty() const; private: std::list<imove_ptr> _history; state _end_state; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして実際には、遅延リストと上記のヘルパークラスを使用して解決策を見つけるクラス：

 typedef std::list<path> paths_list; class water_pouring { public: water_pouring(std::initializer_list<unsigned> capacities); path solve(unsigned target); private: typedef lazy::list<paths_list> list_of_paths_type; list_of_paths_type extend(const paths_list& paths); const std::vector<unsigned> _capacities; const std::vector<imove_ptr> _posible_moves; const state _initial; std::set<state> _explored_states; list_of_paths_type _paths; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このクラスには2つのパブリックメソッドがあります-メガネの容量を取得するコンストラクターと、目的の状態を達成するためのパスを返すメソッドです。



プライベート拡張メソッドは、遅延リストアイテムを生成するために使用されます。



メガネの容量、可能な動きのセット、初期状態、すでに「見つかった」状態、および実際に怠withな状態のリストとそれらの受信履歴を保存します。





water_pouring::extend



メソッド：

 water_pouring::list_of_paths_type water_pouring::extend(const paths_list& paths) { paths_list next; for (auto& cur_path: paths) { for (auto move: _posible_moves) { state next_state = (*move)(cur_path.end_state()); if (_explored_states.find(next_state) == _explored_states.end()) { path new_path(cur_path); new_path.extend(move); next.push_back(new_path); _explored_states.insert(next_state); } } } if (next.empty()) return list_of_paths_type(); return list_of_paths_type(next, std::bind(&water_pouring::extend, this, next)); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

water_pouring::solve



：

 path water_pouring::solve(unsigned target) { paths_list::const_iterator solution; auto it = std::find_if( _paths.begin(), _paths.end(), [target, &solution](const paths_list& paths) -> bool { solution = std::find_if( paths.begin(), paths.end(), [target](const path& p) -> bool { auto it = std::find( p.end_state().begin(), p.end_state().end(), target); return it != p.end_state().end(); }); return solution != paths.end(); }); if (it != _paths.end()) return *solution; return path(state({0})); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

実際に、解決策を見つけるには、std :: find_if関数を使用し、述語として、必要な状態へのパスを調べるラムダ関数を使用します。 ラムダは、リンクを介してソリューションをキャプチャし、ソリューションが見つかった場合に反復子が指すソリューションのリストを通過しないようにします。



その結果、プログラムは次のソリューションを表示します。

 fill(1) pour(1, 0) empty(0) pour(1, 0) fill(1) pour(1, 0) --> (3, 4)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

「怠lazな」リストが役立つ別のタスクを思い付くことができませんでした。 誰かがこのアイデアを気に入ってくれるといいのですが。

参照資料

• ソースパッケージlazy_listのダウンロード
• C ++水注入ソリューションのソースコード
• Scala水を注ぐソースコード
• Scalaでの関数型プログラミングの原則の講義コースでは、注水タスクがレビューされました。
• Catchフレームワークを使用した単体テストの場合