データコンテナとアルゴリズム

1
第5章
データコンテナとアルゴリズム
5.1 データコンテナの類型
Qt では以下のデータコンテナが用意されています。これらのコンテナクラスの上では
Java スタイルや STL スタイルの反復子を使うことができ、また、<QtAlgorithms>や
STL で用意されている一般アルゴリズムを用いて格納されたデータを処理することがで
きます。
QList<T> 最も一般的に利用されるコンテナクラスで、与えられた型 T の値のリストを
格納します。QList は内部的には配列を使って実装されており、インデックスを
使ってアイテムに対する高速なアクセスをすることができます。データアイテムは
QList::append() または QList::prepend() を用いてリストの末端に追加する
か、QList::insert() を使って中間に挿入することができます。QList は他のコ
ンテナクラス以上に、実行ファイル内でのコード量が小さくなるよう高度に最適化
が施されています。
QLinkedList<T> QList に似たコンテナクラスですが、データアイテムにアクセスする
際、整数のインデックスの代わりに反復子を使うようになっており、巨大なリスト
の中間へ挿入するような場合には QList よりも良好なパフォーマンスを得ること
ができます。また、QList ではアイテムの挿入や削除をおこなうと反復子が不正に
なってしまう場合があるのに対し、QLinkedList では指し示されるアイテムが存
在するかぎり反復子は有効なままです。
QVector<T> メモリ上の隣接した位置に、指定された型の値からなる配列を用意します。
ただし、ベクタの先頭もしくは中間へデータアイテムを挿入すると、メモリ上の
位置を一つずらす必要のあるアイテムが多数生じるため、処理が非常に遅くなり
ます。
QStack<T> QVector のサブクラスで、
「ラストイン・ファーストアウト」(LIFO) を実現
します。QVector にて用意されているインターフェースに加え、push(), pop(),
top() を使うことができます。
QQueue<T> QList のサブクラスで、「ファーストイン・ファーストアウト」(FIFO) を
実現します。QList にて用意されているインターフェースに加え、enqueue(),
dequeue(), head() を使うことができます。
QSet<T> 高速に検索をおこなうことのできる、シングルバリューの数学的集合を用意で
第 5 章 データコンテナとアルゴリズム
2
きます。
QMap<Key, T> Key 型のキーと T 型のバリューを結びつける辞書 (連想配列) を用意し
ます。通常、1 つの鍵に対して 1 つのバリューが関連付けられます。QMap は鍵の
順にデータを格納しますが、データの順序がさしたる問題でなければ、QHash を
使ったほうが高速です。
QMultiMap<Key, T> QMap のサブクラスで、マルチバリューのマップ、すなわち 1 つの
キーを複数のバリューに関連付けることのできるマップを用意できます。
QHash<Key, T> QMap とほとんど同じ API が用意されており、とても高速に検索をお
こなうことができます。QHash では恣意的な順序でデータが格納されます。
QMultiHash<Key, T> QHash のサブクラスで、マルチバリューのハッシュを用意でき
ます。
このほか、コンテナクラスとして利用できるわけではありませんが、類するクラスとし
て QByteArray と QString を挙げることができます。
QByteArray ナル文字を含んだ生のバイト列や、伝統的なナル終止の文字列を格納でき、
旧来の char *を使って操作をおこなうよりも遥かに便利に扱うことができます。
QString Unicode でエンコードされた文字列を格納し、扱うことができます。QString
は 16 ビットの QChar から構成され、それぞれの QChar には Unicode 4.0 の文字
が一文字づつ格納されます。
5.2 クラスのインターフェース
この節ではコンテナに類するクラスの代表として QList と QMap を取り上げ、そのイン
ターフェースのうちで主なものについて紹介します。
完全な一覧については Qt のリファレンスマニュアルを参照してください。
5.2.1 QList
void QList::append ( const T & value )
QList & QList::operator<< ( const T & value )
QList & QList::operator<< ( const QList & other )
append() と operator<<は、リストの末尾に値を追加します。operator<<では
別のリストをマージすることもできます。
T QList::value ( int i ) const
T QList::value ( int i, const T & defaultValue ) const
リスト中にある i 番目のインデックスで示される値を返します。もし i が範囲外
の値であれば、デフォルトの値が返されます。i の値が範囲内にあることが保証さ
れているのなら、代わりに at() を用いたほうが高速です。
T & QList::operator[] ( int i )
const T & QList::operator[] ( int i ) const
5.2 クラスのインターフェース
const T & QList::at ( int i ) const
リスト中にある i 番目のインデックスで示される値を返します。i の値はリストの
範囲内 (0 <= i < size()) になければなりません。
int QList::size () const
bool QList::isEmpty () const
size() はリストに含まれるデータアイテムの数を返します。リストがデータアイ
テムを 1 つも含んでいない場合、isEmpty() は真を返します。
QDataStream & operator<< ( QDataStream & out, const QList<T> & list )
QDataStream & operator>> ( QDataStream & in, QList<T> & list
これらのオーバーロード関数は便宜的に用意されているもので、データストリーム
とリストの間でデータを簡単に読み書きできるようになっています。
5.2.2 QMap
iterator QMap::insert ( const Key & key, const T & value )
iterator QMap::insertMulti ( const Key & key, const T & value )
key と value からなるデータアイテムをマップに追加します。キーに対応するバ
リューが既に登録されていた場合、insert() では古いバリューが新しいバリュー
で上書きされます*1 。insertMulti() では新しいバリューが追加登録され、キー
とバリューの関係は一対多となります。なお、引数として返される iterator は後
述する STL スタイルの反復子です。
const T QMap::value ( const Key & key ) const
const T QMap::value ( const Key & key, const T & defaultValue ) const
T & QMap::operator[] ( const Key & key )
const T QMap::operator[] ( const Key & key ) const
キーに関連付けられているバリューを返します。もしキーに対応するバリューが
マップ内になければ、デフォルト値が返されます。キーに対応するバリューが複数
ある場合には、一番最後に追加されたものが返されます。なお、対応する全てのバ
リューを取得するには values() を使います。
int QMap::size () const
bool QMap::isEmpty () const
size() はマップ中に格納されるキーとバリューのペア数を返します。isEmpty()
はマップ中にデータエントリが 1 つもない場合、真を返します。
QDataStream & operator<< ( QDataStream & out, const QMap<Key, T> & map )
*1
キーに対応するバリューが insertMulti() によって複数登録されていたような場合には、一番最後に登
録されたバリューが置き換わります。
3
第 5 章 データコンテナとアルゴリズム
4
QDataStream & operator>> ( QDataStream & in, QMap<Key, T> & map )
これらのオーバーロード関数は便宜的に用意されているもので、データストリーム
とマップの間でデータを簡単に読み書きできるようになっています。
QList<Key> QMap::keys () const
QList<Key> QMap::keys ( const T & value ) const
QList<T> QMap::values () const
QList<T> QMap::values ( const Key & key ) const
keys() はマップ中にある全てのキー、あるいは指定したバリューを持つキーの全
てを抽出し、QList<Key>の形で返します。キーがマップ内に複数ある場合には、
その全てについてリスト中に含まれます。
values() はマップ中にある全てのバリュー、あるいは指定したキーに関連付けら
れているバリューの全てを抽出し、QList<T>の形で返します。insertMulti() で
追加されたバリューに関しても、その全てが列挙されリストに含まれます。
5.3 foreach キーワード
Qt のコンテナクラス上では foreach キーワードを利用し、コンテナに含まれる要素
ごとにループを回すことができます。これは C++ 言語に対する Qt の独自追加機能で、
標準 C++ プリプロセッサを用いて実装されています。foreach の文法は以下のように
なっています。
foreach (variable, container)
statement;
foreach を使って QList<int>を反復する方法を以下に示します。
1
#include <QtCore>
2
3
int main(int argc, char *argv[])
4
{
5
QList<int> list;
6
list << 300 << 400 << 250 << 600;
7
8
int sum = 0;
9
foreach(int n, list){
sum += n;
10
11
}
12
qDebug("sum: %d", sum);
13
return 0;
14
15
}
5.4 Java スタイルの反復子
5
foreach はシーケンシャルコンテナだけでなく、連想コンテナでも利用することがで
きます。
1
#include <QtCore>
2
3
int main(int argc, char *argv[])
4
{
5
QMap<QString, QString> map;
6
map.insert("Japan", QString::fromLocal8Bit("日本"));
7
map.insert("Norway", QString::fromLocal8Bit("諾威"));
8
9
foreach (QString s, map.keys()){
10
qDebug() << s << map.value(s);
}
11
12
return 0;
13
14
}
5.4 Java スタイルの反復子
それぞれのコンテナクラスに対応した Java スタイルの反復子としては、以下のような
ものが用意されています。
コンテナ
読み出し専用の反復子
読み書き可能な反復子
QList<T>, QQueue<T>
QListIterator<T>
QMutableListIterator<T>
QLinkedList<T>
QLinkedListIterator<T>
QMutableLinkedListIterator<T>
QVectorIterator<T>
QMutableVectorIterator<T>
QSetIterator<T>
N/A
QMapIterator<Key, T>
QMutableMapIterator<Key, T>
QHashIterator<Key, T>
QMutableHashIterator<Key, T>
QVector<T>,
QStack<T>
QSet<T>
QMap<Key, T>,
QMultiMap<Key, T>
QHash<Key, T>,
QMultiHash<Key, T>
5.4.1 QListIterator
#include <QtCore>
int main(int argc, char *argv[])
{
QVector<QString> list;
list << ‘‘Alpha’’ << ‘‘Beta’’ << ‘‘Gamma’’ << ‘‘Delta’’;
第 5 章 データコンテナとアルゴリズム
6
QVectorIterator<QString> i(list);
//i.toFront();
while (i.hasNext()) {
qDebug() << i.next();
}
i.toBack();
while (i.hasPrevious()) {
qDebug() << i.previous();
}
i.toFront();
if(i.findNext(‘‘Alpha’’)) {
qDebug() << i.previous();
}
i.toBack();
if(i.findPrevious(‘‘Omega’’)) {
qDebug() << i.next();
}
return 0;
}
5.4.2 QMapIterator
5.5 STL スタイルの反復子
5.6 <QtAlgorithm>