「std::deque」の版間の差分

2015年11月8日 (日) 14:51時点における最新版

std::deque とは、Dobule Ended Queue の略です。双方向キュー、両端キューなどと呼ばれるデータ構造のSTL コンテナです。dequeは、FIFOとFIFOの両方に対応したデータ構造です。先頭や末尾の挿入や削除の頻度が高い場合は、std::dequeを使用します。

読み方

std::deque

えすてぃーでぃー でっく

double ended queue

だぶる えんでっど きゅー

概要

発音は、「デキュー」ではありません。

std::dequeの特徴をいくつか挙げます。

• 先頭や一番後ろに要素を追加できます。
• .at や operator[] による添字でのアクセスが可能です。

std::deque を利用するシーン

コンテナは、それぞれ特徴があります。メモリの効率が良い、検索スピードが速い、先頭や末尾への挿入や削除が速い、途中への挿入や削除が速い、などの違いがあります。

先頭や末尾の挿入や削除の頻度が高い場合は、std::dequeを使用します。

どのコンテナを利用すべきかは、コンテナをご参照ください。

要素の追加

push_front 

最初に要素を追加

push_back 

一番後ろに要素を追加

要素の削除

pop_front 

最初の要素を削除

pop_back 

一番後ろの要素を削除

デックのシンプルな例 deque1.cpp の例

ソースコード deque1.cpp

/*
 * deque1.cpp
 * Copyright (C) 2014 kaoru <kaoru@bsd>
 */
 
#include <iostream>
#include <deque>
using namespace std;
 
template<typename T> void
print(deque<T>& d) {
        for(auto x: d) {
                cout << x << " ";
        }
        cout << endl;
}
int
main(int argc, char const* argv[])
{
        deque<int> d1;
 
        d1.push_back(1);
        d1.push_back(2);
        d1.push_back(3);
        d1.push_back(4);
        d1.push_front(0);
        print<int>(d1); // 0 1 2 3 4
 
        d1.pop_back();
        d1.pop_front();
        print<int>(d1); // 1 2 3
 
        d1.front() = 0;
        d1.back() = 9999;
        print<int>(d1); // 0 2 9999
 
        return 0;
}

コンパイル

g++49 -std=c++11 -I/usr/local/lib/gcc49/include/c++/ \
-Wl,-rpath=/usr/local/lib/gcc49  deque1.cpp -o deque1

実行例

% ./deque1
0 1 2 3 4
1 2 3
0 2 9999

atを使用した要素アクセスの例 deque_at1.cpp

atを使用してアクセスする場合、境界チェックが行われます。 存在しない要素にアクセスしようとすると std::out_of_range の例外がスローされます。operator[] を使用した場合には、例外は、スローされません。

ソースコード deque_at1.cpp

/*
 * deque1.cpp
 * Copyright (C) 2014 kaoru <kaoru@bsd>
 */
 
#include <iostream>
#include <deque>
#include <stdexcept>    // std::out_of_range
using namespace std;
 
int
main(int argc, char const* argv[])
{
        deque<int> d1;
 
        d1.push_back(1);
        d1.push_back(2);
        d1.push_back(3);
        d1.push_back(4);
 
        try {
                cout << d1.at(0) << endl;
                cout << d1.at(1) << endl;
                cout << d1.at(2) << endl;
                cout << d1.at(3) << endl;
        } catch (out_of_range e) {
                cerr << e.what() << endl;
        }
 
        try {
                cout << d1.at(4) << endl;       // This is out of range
        } catch (out_of_range e) {
                cerr << e.what() << endl;
        }
 
        return 0;
}

コンパイル

c++  deque_at1.cpp -o deque_at1

実行例

% ./deque_at1
1
2
3
4
deque::_M_range_check: __n (which is 4)>= this->size() (which is 4)

operator[]を使用した例 deque_at2.cpp

ソースコード deque_at2.cpp

/*
 * deque1.cpp
 * Copyright (C) 2014 kaoru <kaoru@bsd>
 */
 
#include <iostream>
#include <deque>
#include <stdexcept>    // std::out_of_range
using namespace std;
 
int
main(int argc, char const* argv[])
{
        deque<int> d1;
 
        d1.push_back(1);
        d1.push_back(2);
        d1.push_back(3);
        d1.push_back(4);
 
        try {
                cout << d1[0] << endl;
                cout << d1[1] << endl;
                cout << d1[2] << endl;
                cout << d1[3] << endl;
        } catch (out_of_range e) {
                cerr << e.what() << endl;
        }
 
        try {
                cout << d1[4] << endl;  // 存在しないが例外とならない
                cout << d1[5] << endl;  // 存在しないが例外とならない
        } catch (out_of_range e) {
                cerr << e.what() << endl;
        }
 
        return 0;
}

コンパイル

c++  deque_at2.cpp -o deque_at2

実行例

添字の 0 から 3 までは、存在している要素なので、問題ありません。 添字 4, 5 は、存在しないのですが、 0 が返ってきています。

% ./deque_at2
1
2
3
4
0
0

関連項目

• コンテナ