PythonistaのためのC++記法入門: それC++ではどう書くの3の続き。今回は競プロでよく用いられるようなデータ構造。
queue / stack / deque
基本はpush(値)してデータを格納、pop()でデータを取り出す。
Pythonとは異なりpop()した値を他の変数に代入することはできない（auto val = q.pop();とはできない）。
アクセスできる位置に制約がある代わりに非常に高速なアクセスが可能。
FIFO型かLIFO型かによって先頭の定義が変わり、それにより先頭へのアクセス方法がfront()もしくはtop()となる。この先頭要素へのアクセスが非常に高速であるのがこれらのコンテナの特徴。Dequeは両端および中間要素へのアクセスが可能だが中間要素へのアクセスは高速ではない。
PythonではQueue / Stack単体に該当するものはなく、これらをまとめたDequeが利用できる。そのためここではまずC++での利用法から書いていく。
Queue
FIFO(First In First Out)型のデータ構造。最初にpushした値から順にpopされる。
C++ではこう書く
queue<型> 変数名で宣言でき、ここで指定したデータ型を格納するqueueが作られる。
front()でqueueにおける先頭、すなわち最も古くpushされてまだ残っている要素へのアクセスが可能であり、pop()でその要素がqueueから削除される。
queueの先頭からみた反対方向の末尾、すなわち最後にpushされた要素へもback()でアクセスが可能。しかしその要素を削除することはできない。
// 宣言
queue<int> q;
// 要素の追加
q.push(0);
q.push(1);
// 先頭要素へのアクセス
cout << q.front() << endl; // 0 が出力される
// 末尾要素へのアクセス
cout << q.back() << endl; // 1 が出力される
// 要素の削除
q.pop(); // queueから0が削除される
cout << q.front() << endl; // 1 が出力される
// 要素数チェック
cout << q.size() << endl; // 1 が出力される
// queueが空であるかのチェック
if (q.empty()){cout << "Empty" << endl;}
else {cout << "Not Empty" << endl;} // Not Emptyが出力される
priority_queue
それまでに格納した値のうち最大のものを優先的に取り出すqueueがpriority_queueである。使い方はqueueとほぼ同じだが、最大値を取り出すときにtop()を使うことに注意。front()は使えない。
C++ではこう書く
// 宣言
priority_queue<int> pq;
// 値を格納していく
pq.push(10);
pq.push(1);
pq.push(1000);
pq.push(40);
// topは現時点での最大値を返す
cout << pq.top() << endl; // 1000が出力される
pq.pop(); // 最大値である1000が削除される
cout << pq.top() << endl; // 40が出力される
Stack
LIFO(Last In First Out)型のデータ構造。最後にpushした値からpopされる。
C++ではこう書く
stack<型> 変数名で宣言でき、ここで指定したデータ型を格納するstackが作られる。stackにおける先頭とは最後にpushした要素であり、queueとは反対となるので注意。
top()で先頭要素にアクセスできる。queueとは異なり末尾要素（この場合最も古くpushされた要素）にアクセスする方法はない。
// 宣言
stack<string> stk;
// 要素の追加
stk.push("John");
stk.push("Mary");
// 要素へのアクセス（先頭、つまり最後にpushされた要素へのアクセス）
cout << stk.top() << endl; // Mary が出力される
// 要素の削除
stk.pop(); // 最後にpushされたMaryが削除される
cout << stk.top() << endl; // John が出力される
// 要素数チェック
cout << stk.size() << endl; // 1 が出力される
// queueが空であるかのチェック
if (stk.empty()){cout << "Empty" << endl;}
else {cout << "Not Empty" << endl;} // Not Emptyが出力される
Deque
Double-ended queueの略。queueとstackを合わせたようなもの。両端、すなわち先頭と末尾へのアクセスが高速であるコンテナ。インデックスを利用した中間の要素へのアクセスも可能だが、速度面でvectorに劣る。
C++ではこう書く
deque<型> 変数名で宣言でき、ここで指定したデータ型を格納するdequeが作られる。
push_front(値) / push_back(値)で値を先頭 / 末尾へ格納し、
pop_front() / pop_back()で値を先頭 / 末尾から削除、
front() / back()で先頭 / 末尾の値へアクセス、
さらにat(i)または変数名[i]でi番目の値へアクセスする。at(i)で存在しない要素へアクセスしようとするとエラーとなる。
insert()で任意の位置への要素の追加が可能だが、listのinsertと比べると実行速度は遅い。
// 宣言
deque<string> deq;
// 要素の追加
deq.push_front("John"); // ["John"]
deq.push_back("Mary"); // ["John", "Mary"]
deq.push_front("Helen"); // ["Helen", "John", "Mary"]
// 末尾要素へのアクセス（backmost要素へのアクセス）
cout << deq.back() << endl; // Mary が出力される
// 先頭要素へのアクセス（frontmost要素へのアクセス）
cout << deq.front() << endl; // Helen が出力される
// 要素の削除
deq.pop_front(); // ["John", "Mary"]
cout << deq.front() << endl; // John が出力される
deq.pop_back(); // ["John"]
cout << deq.back() << endl; // John が出力される
// インデックスによるアクセス
cout << deq.at(0) << endl; // John が出力される
cout << deq[0] << endl; // John が出力される
deq.at(0) = "JOHN"; // 書き換えも可能
cout << deq.at(0) << endl; // JOHN が出力される
// 要素数チェック
cout << deq.size() << endl; // 1 が出力される
// queueが空であるかのチェック
if (deq.empty()){cout << "Empty" << endl;}
else {cout << "Not Empty" << endl;} // Not Emptyが出力される
Pythonではこう書いた
Pythonでもcollections.dequeで実装されている（が個人的に利用したことはない）。
利用可能なメソッドの名前がC++とは微妙に異なる。
appendleft(値) / append(値)で値を先頭 / 末尾へ格納し、
popleft() / pop()で値を先頭 / 末尾から削除、
変数名[0] / 変数名[-1]で先頭 / 末尾の値へアクセス、
変数名[i]でi番目の値へアクセスする。存在しない要素へアクセスしようとするとエラーとなる。
他にも値が何番目に格納されているかを返すindexや格納順をずらすrotateなどのメソッドが用意されている。
from collections import deque
# 定義
deq = deque()
# 要素の追加
deq.append("John") # deque(['John'])
deq.append("Mary") # deque(['John', 'Mary'])
deq.appendleft("Helen") # deque(['Helen', 'John', 'Mary'])
# 末尾要素へのアクセス（backmost要素へのアクセス）
deq[-1] # 'Mary' が出力される
# 先頭要素へのアクセス（frontmost要素へのアクセス）
deq[0] # 'Helen' が出力される
# 要素の削除
_ = deq.popleft() # deque(['John', 'Mary'])
deq[0] # 'John' が出力される
_ = deq.pop() # deque(['John'])
deq[-1] # 'John' が出力される
# インデックスによるアクセス
deq[0] # 'John' が出力される
# 要素数チェック
len(deq) # 1 が出力される
# queueが空であるかのチェック
if len(deq) == 0:
print("Empty")
else:
print("Not Empty")
# Not Emptyが出力される
まとめ
| C++ | Python | |
|---|---|---|
| 宣言 / 定義 | deque<型> deq; | deq = collections.deque() |
| 先頭に要素を追加 | deq.push_front(); | deq.appendleft() |
| 先頭の要素を削除 | deq.pop_front(); | deq.popleft() |
| 先頭要素へのアクセス | deq.front(); | deq[0] |
| 末尾に要素を追加 | deq.push_back(); | deq.append() |
| 末尾の要素を削除 | deq.pop_back(); | deq.pop() |
| 末尾要素へのアクセス | deq.back(); | deq[-1] |
| 任意要素へのアクセス(1) 1 | deq.at(i); | deq[i] |
| 任意要素へのアクセス(2) | deq[i]; 2 | 同上 |
| 要素を任意位置に挿入 3 | deq.insert(位置, 要素); | deq.insert(位置, 要素) |
| 任意要素の削除 | deq.erase(位置); 4 | deq.remove(要素) |
| 要素数を取得 | deq.size(); | len(deq) |
| 全要素を削除 | deq.clear(); | deq.clear() |