C++STL:STLにおけるコンテナアダプタstackとqueueのシミュレーション

目次

コンテナアダプタ

とは

stack

stackのドキュメントの説明-(cplusplusから)

stackの実装

queue

queueのドキュメントの説明-(cplusplusから)

queueの実装

コンテナアダプタとは
これまでシミュレーションで実装されていたvector,string,listなどはコンテナでしたが,今回実装するstackとqueueはコンテナアダプタでしたが,コンテナアダプタとは何でしょうか.アダプタは実は変換装置で、このようなものは生活の中で非常によく見られます.例えばUSBインタフェースをType-cインタフェースに変えると、携帯電話でUディスクを使ったり、三脚プラグで二脚プラグを回したりして、より多くのコンセントを使いやすくなります.アダプタの役割は、デバイスを交換することなく、デバイスを他のシーンに適用したり、別の機能を持ったりすることです.STLでは、stackとqueueは従来のデータ構造のスタックとキューであり、私たちは彼の下位層が何であるかに関心を持っていません.私たちは彼が後進先出と先進先出の特徴を持っていることを保証するだけでいいからです.この特徴はvectorを使用してもlistを使用しても実現できます.そうであれば、いっそアダプタとして使用します.新しいコンテナを作成する必要はなく、既存のコンテナで直接彼の特性を実現すればよく、このコンテナには多くの選択肢があります.
stack
stackのドキュメントの紹介-(cplusplusから)

stackは、後進先出操作を有するコンテキスト環境に特化したコンテナアダプタであり、削除はコンテナの一端からのみ要素の挿入と抽出操作を行うことができる.

stackは、コンテナアダプタとして実装され、コンテナアダプタは、特定のクラスをその下位としてカプセル化し、その要素にアクセスするための特定のメンバー関数のセットを提供し、特定のクラスをその下位とし、要素特定のコンテナの末尾(すなわちスタックトップ)が押し込まれ、ポップアップされる.

stackの最下位コンテナは、任意の標準的なコンテナクラステンプレートまたは他の特定のコンテナクラスであってもよい.これらのコンテナクラスは、empty:空判定操作back:末尾要素操作push_を取得するback:末尾挿入要素操作pop_back:末尾削除要素アクション

標準コンテナvector、deque、listはこれらの要件に合致し、デフォルトではstackに特定の下位コンテナが指定されていない場合はdequeがデフォルトで使用されます.

stackの実装
stackの実装は実はスタックの実装であり,既存のコードを多重化した上でstlの特性を増加させるだけでよいが,以下は前のデータ構造の章で実現したスタックの実装である.
ライブラリでデフォルトで選択されているコンテナはdequeです

#include

namespace lee
{
     
	/*
		STL          deque，  deque        ，                               ，
		            ，       。 vector    ，        ，     ，     ，           1.5  2 （    ）
		vector      deque ，         ，             
	*/

	template<class T, class Container = std::deque<T>>
	class stack
	{
     
	public:
		void push(const T& val)
		{
     
			_con.push_back(val);
		}

		void pop()
		{
     
			_con.pop_back();
		}

		T& top() 
		{
     
			return _con.back();
		}

		const T& top() const
		{
     
			return _con.back();
		}

		size_t size() const
		{
     
			return _con.size();
		}

		bool empty() const
		{
     
			return _con.empty();
		}

	private:
		Container _con;
	};
}

queue
Queueのドキュメントの説明-(cplusplusから)

キューは、FIFOコンテキスト(先進先出)で動作するためのコンテナアダプタで、コンテナの一端から要素を挿入し、他端から要素を抽出します.

キューはコンテナアダプタとして実装され、コンテナアダプタは特定のコンテナクラスをその下位コンテナクラスとしてカプセル化し、queueはその要素にアクセスするための特定のメンバー関数のセットを提供する.要素はキューの最後からキューに入り、キューの先頭からキューから出ます.

底部容器は、標準容器クラステンプレートの1つであってもよいし、他の専門的に設計された容器クラスであってもよい.この下位コンテナは、少なくとも以下の操作をサポートする必要があります:empty:キューが空sizeであるかどうかを検出します:キュー内の有効な要素の個数frontを返します:キューヘッダ要素の参照backを返します:キューテール要素の参照push_を返しますback:キューの末尾にキューpop_を挿入front:キューヘッダにキュー

を出る

標準コンテナクラスdequeおよびlistは、これらの要件を満たしている.デフォルトでは、queueインスタンス化にコンテナクラスが指定されていない場合は、標準コンテナdequeが使用されます.

Queueの実装
キューの実装
ライブラリでデフォルトで選択されているコンテナはdequeです

#include

namespace lee
{
     
	/*
	STL queue      deque，  deque list           O（1），  deque     ，  list            ，            .
	deque              ，              ，       ，                    ，        
	*/
	
	template<class T, class Container = std::deque<T>>
	class queue
	{
     
	public:
		void push(const T& val)
		{
     
			_con.push_back(val);
		}

		void pop()
		{
     
			_con.pop_front();
		}

		T& front()
		{
     
			return _con.front();
		}

		const T& front() const
		{
     
			return _con.front();
		}

		T& back()
		{
     
			return _con.back();
		}

		const T& back() const
		{
     
			return _con.back();
		}

		size_t size() const
		{
     
			return _con.size();
		}

		bool empty() const
		{
     
			return _con.empty();
		}

	private:
		Container _con;
	};
}