コンテナアダプタ

コンテナを利用したクラス

コンテナアダプタは、内部にSTLコンテナを持つクラスです。

コンテナアダプタは要素の順序が重要なクラスで、特定の条件に従ってデータが出し入れされます。

stack

stackクラスは、データを入れた順とは逆から取り出されます。
(後に入れたものから先に出される、後入れ先出し)
「1、2、3」の順に入力した場合、「3、2、1」の順に取り出されます。

「stack」は「積み上げる」という意味で、データを上に重ねていくイメージです。
積み上げたデータから値を取り出すには、上から順に取り出す必要があります。

queue

queueクラスは、データを入れた順に取り出されます。
(先に入れたものから先に出される、先入れ先出し)
「1、2、3」の順に入力した場合、「1、2、3」の順に取り出されます。

「queue」は「列」という意味で、順番待ちの列のイメージです。
データは列の後ろに並べていき、取り出しは列の先頭から行います。

priority_queueクラス

priority_queueクラスは、あらかじめ指定した優先順位に従ってデータが取り出されます。
デフォルトでは降順です。

priority_queueクラスについて

自作クラスを格納する

priority_queueクラスでユーザー定義クラスを使用するには<演算子をオーバーロードする必要があります。

class C
{
	int x;
	int y;
public:
	C(int a, int b) : x(a), y(b) {}

	//xが同値ならyで比較する
	bool operator <(const C& r) const
	{
		if (this->x < r.x) {
			return true;
		}
		else  if (this->x > r.x) {
			return false;
		}
		return (this->y < r.y);
	}
};

これはデフォルトの比較関数として<演算子による比較を行うstd::lessが使用されているためです。
比較関数を変更した場合はそれに対応する演算子のオーバーロードが必要になります。

優先順位の変更

priority_queueクラスはデフォルトでは降順で要素が取り出されます。
優先順位の変更はテンプレート仮引数で比較関数を指定します。

//std::greaterで比較
std::priority_queue<
	int,
	std::vector<int>,
	std::greater<int>> q;

q.push(3);
q.push(1);
q.push(7);

while (!q.empty())
{
	std::cout << q.top() << ", ";
	q.pop();
}

1, 3, 7

テンプレート仮引数の第三引数が比較関数の指定です。
上記の例では昇順で比較するstd::greaterを使用しています。
これは>演算子による比較を行いますので、自作クラスを使用する場合は>演算子のオーバーロードが必要です。

優先順位を任意に指定する例です。

#include <iostream>
#include <queue>
#include <functional>

struct S
{
    int x;
    int y;

    //大小比較関数(降順)
    static bool comparer(S l, S r)
    {
        if (l.x < r.x) {
            return true;
        }
        else  if (l.x > r.x) {
            return false;
        }
        return (l.y < r.y);
    }
};

int main()
{
    {
        //静的メンバ関数をstd::functionに格納
        std::function<bool(S, S)> comparer = S::comparer;
        //autoでも可
        //auto comparer = S::comparer;

        std::priority_queue<
            S,
            std::vector<S>,
            decltype(comparer)> q(comparer); //コンストラクタに関数オブジェクトを指定する
        q.push({ 1, 5 });
        q.push({ 3, 4 });
        q.push({ 1, 3 });

        while (!q.empty())
        {
            const S& t = q.top();
            std::cout << t.x << ", " << t.y << std::endl;
            q.pop();
        }
    }
    std::cout << std::endl;
    {
        //大小比較関数(昇順)をラムダ式で定義
        auto comparer = [](S l, S r) {
            if (l.x > r.x) {
                return true;
            }
            else  if (l.x < r.x) {
                return false;
            }
            return (l.y > r.y);
        };

        std::priority_queue<
            S,
            std::vector<S>,
            decltype(comparer)> q(comparer); //コンストラクタに関数オブジェクトを指定する
        q.push({ 1, 5 });
        q.push({ 3, 4 });
        q.push({ 1, 3 });

        while (!q.empty())
        {
            const S& t = q.top();
            std::cout << t.x << ", " << t.y << std::endl;
            q.pop();
        }
    }
}

3, 4
1, 5
1, 3

1, 3
1, 5
3, 4

テンプレート仮引数の第三引数はデータ型の指定なので、decltypeを使用して関数オブジェクトのデータ型を指定します。
実際に呼び出す関数はpriority_queueのコンストラクタに指定します。

メンバ関数一覧

コンテナアダプタで共通するメンバ関数の対応一覧です。

vectorクラスと共通の関数は当該ページを参照してください。
以下は、上記のページでは説明していない関数について説明します。

std::vector<int> vec;

//全て同じデータ型
std::vector<int>::iterator it1;
auto it2 = vec.begin();
decltype(vec)::iterator it3;

top関数

top関数は、トップ要素にアクセスします。

#include <iostream>
#include <stack>
#include <queue>

int main()
{
	std::stack<int> stack;
	stack.push(3);
	stack.push(2);
	stack.push(1);
	std::cout << stack.top() << std::endl;

	std::priority_queue<int> pqueue;
	pqueue.push(3);
	pqueue.push(2);
	pqueue.push(1);
	std::cout << pqueue.top() << std::endl;

	std::cin.get();
}

1
3

トップ要素は、stackクラスの場合は最後に入れたデータです。
priority_queueクラスの場合は最も優先順位の高い要素です。
デフォルトでは降順に並べられるので、要素中の最も大きい値です。

要素アクセスなので値の取り出しだけではなく代入もできます。
(要素への参照が返される)

std::stack<int> stack;
stack.push(3);
stack.push(2);
stack.push(1);

stack.top() = 10;
std::cout << stack.top() << std::endl;

10

なお、この関数は単純な要素アクセスであって要素の取り出しではありません。
つまり要素を削除する機能はありません。

front関数

back関数

front関数は、先頭要素にアクセスします。
back関数は、末尾要素にアクセスします。

std::queue<int> queue;
queue.push(3);
queue.push(2);
queue.push(1);

std::cout << queue.front() << std::endl;
std::cout << queue.back() << std::endl;

3
1

queueクラスは先入れ先出しなので、先頭要素は最初に入れたデータです。
末尾要素は最後に入れたデータです。

この関数も要素を削除する機能はありません。

pop関数

push関数

pop関数は、トップ要素を削除します。
push関数は、要素を追加します。

#include <iostream>
#include <stack>
#include <queue>

int main()
{
	std::stack<int> stack;
	stack.push(3);
	stack.push(2);
	stack.push(1);

	while (!stack.empty()) {
		std::cout << stack.top() << " ";
		stack.pop();
	}
	//1 2 3

	std::cout << std::endl;

	std::queue<int> queue;
	queue.push(3);
	queue.push(2);
	queue.push(1);

	while (!queue.empty()) {
		std::cout << queue.front() << " ";
		queue.pop();
	}
	//3 2 1

	std::cout << std::endl;

	std::priority_queue<int> pqueue;
	pqueue.push(3);
	pqueue.push(2);
	pqueue.push(1);
	pqueue.push(4);

	while (!pqueue.empty()) {
		std::cout << pqueue.top() << " ";
		pqueue.pop();
	}
	//4 3 2 1

	std::cout << std::endl;

	std::cin.get();
}

これらの関数の戻り値はありません。

pop関数はtop関数で得られる要素を削除します。
コンテナアダプタは、要素を追加/削除する位置は固定なので「位置を指定して挿入/削除」といった機能は提供されていません。