Aizu Online Judge（AOJ）が提供している「プログラミング応用」（ITP2）の1_C問題をC++で解いてみました。
ITP2では、「プログラミングのための基礎ライブラリを獲得します」とあります。トピック#1では、動的配列とリストを学びます。
問題（1_C: List）
問題はリンク先をご覧ください。
List コンテナとイテレータについて学びます。
List コンテナについて
以下は、cpprefjp 様の記事を参考にさせていただきました。
概略
List は、Vector や Deque とは異なる特徴のコンテナを提供します。
- 先頭でも途中でも末尾でも要素の追加と削除が効率よくできる。
- 可変長で、自動的に領域の拡張が行われる。
- 添え字によるランダムアクセスはできず、シーケンシャルアクセスを行う必要がある。
主なメソッド
よく使われるメソッドを紹介します。
| 名前 | 説明 |
| push_front | 先頭へ要素を追加する。 |
| push_back | 末尾へ要素を追加する。 |
| pop_front | 先頭から要素を削除する。 |
| pop_back | 末尾から要素を削除する。 |
| front | 先頭への参照を取得する。 |
| back | 末尾への参照を取得する。 |
| size | 要素数を返す。 |
| resize | 要素数を変更する。 |
| insert | 要素を挿入する。 |
| erase | 要素を削除する。 |
| empty | コンテナが空なら true を、そうでなければ false を返す。 |
| clear | すべての要素を削除する。 |
紹介したメソッドは、Deque と同じです。ただし、Vector と Deque は途中の要素に挿入したり、削除する操作は速くはありません。これは、影響がある要素以降の要素すべてについて波及的に操作をする必要があるためです。一方、List は、場所に関係なく効率良い挿入と削除ができます。
ただし、List は添え字によるアクセスができず。イテレータを経由してアクセスする必要があります。使い方（コード）は、次のプログラム例で紹介します。
C++ プログラム例（ITP2 1_C）
問題で与えられるクエリに従い、以下の操作を行います。
- クエリ0 insert により、与えられた x を現在位置に挿入する。
- クエリ1 与えられた d に対して、現在位置を変更する。d が負の場合は、前に移動する。
- クエリ2 erase により現在位置の要素を削除する。
- すべてのクエリ処理後に、リストの要素を先頭からすべて出力する。
List は、現在位置と呼んでいる List のイテレータ it で場所を指示して操作を行います。insert の場合、insert された要素を指すイテレータを返します。erase した場合は、erase した次の要素を指すイテレータを返します。問題の制約は、このイテレータの動きを意図していると思われます。
このプログラムでは、コンテナに対するイテレータの操作を学ぶことができます。イテレータに関係するコードの背景色を変更しました。
#include <iostream>
#include <list>
using namespace std;
int iabs(int n) {
if (n < 0) {
n = -n;
}
return n;
}
int main()
{
list<int> L;
int q;
cin >> q;
list<int>::iterator it = L.begin();
for (int i = 0; i < q; ++i) {
int command;
cin >> command;
if (command == 0) {
int x;
cin >> x;
it = L.insert(it, x); // 挿入された要素を指すイテレータを返す。
} else if (command == 1) {
int d;
cin >> d;
for (int j = 0; j < iabs(d); ++j) {
if (d >= 0) {
++it;
} else {
--it;
}
}
} else if (command == 2) {
it = L.erase(it); // 削除された要素の次の要素を指すイテレータを返す。
}
}
for (it = L.begin(); it != L.end(); ++it) {
cout << *it << endl;
}
return 0;
}紹介したプログラムでは、整数の絶対値を返す関数 iabs を独自に実装しています。これは、abs() が、C++03では、整数型に対応していないためです。参考までに C++17 から整数を返す場合にも対応しています。
上記プログラムは、AOJ で「AC（Accepted＝正解）」と判定されました。
最後に
Vector、Deque、List と3種類のコンテナを学びました。それぞれの特徴は以下です。
- Vector は、配列に近いコンテナを提供する。
- Deque は、Vector に近いが、先頭への挿入と削除が効率よくできる。
- List は、添え字によるアクセスができないが、任意の場所への挿入と削除が効率よくできる。
それぞれのコンテナの特徴を活かして使っていきたいと思います。
引き続き、ITP2 の問題を紹介していきます。
