各種コンテナの実装と性能 Qt #4 勉強会福岡 @ kikairoya
About Twitter: @kikairoya 宮崎県都城市から来ました 本職 : 精密機械設計 組込機器開発 C++ とか出来ます Qt わかりません
Abstruct STL コンテナと Qt コンテナの比較 データ構造 パフォーマンス 安全性 インタフェース おまけで Boost コンテナも
STL Containers vector deque list/forward_list set/multiset map/multimap array unordered_set/unordered_multiset unordered_map/unordered_multimap
Qt Containers QVector QList QLinkedList QMap/QMultiMap QSet QHash/QMultiHash
Boost Containers vector/stable_vector deque list/slist set/multiset/flat_set/flat_multiset map/mutlimap/flat_map/flat_multiap array unordered_set/unordered_multiset unordered_map/unordered_multimap
Major Difference STL Container CoW しない 全ての操作が例外安全の基本保証を満たす Qt Container CoW を行う 例外安全に関しての規定が無い
std::vector QVector boost::container::vector 要素を連続的に格納するいわゆる 可変長配列 各要素のルックアップは定数時間 末尾に対する挿入 削除は償却定数時間 Stroustrup 曰く コンテナが必要な場合 特に理由が無ければ vector を使おう と std::vector<bool> トラップに注意
std::vector QVector boost::container::vector Operation Complexity Exception Safe Copy / Assign O(N) Strong Guarantee Range Copy / Assign O(N) Strong Guarantee push_back amortized O(1) Strong if T's ctor does not throw or Basic Guarantee insert(pos,...) O((N-pos)) Strong if T's ctor does not throw or Basic Guarantee pop_back O(1) No-fail erase O((N-pos)) No-fail if T's ctor does not throw or Basic Guarantee indexed access ( op[], at ) O(1) No-fail
QList boost::container::stable_vector 間接ベクタ list である必要はないけど T のコピーが重い時に sizeof(t) <= sizeof(t *) の場合は QVector と同じように振る舞う
std::deque boost::container::deque 要素をポインタを介して半連続的に格納 イメージ的には間接リングバッファ あるいはページコンテナ 各要素のルックアップは定数時間 (2 段間接参照 ) 先頭 末尾に対する挿入 削除は定数時間 ほとんどの操作は vector のほうが微妙に速い
std::deque boost::container::deque Operation Complexity Exception Safe Copy / Assign O(N) Strong Guarantee Range Copy / Assign O(N) Strong Guarantee push_front/push_back O(1) Strong if T's ctor does not throw or Basic Guarantee insert(pos,...) O(N) Strong if T's ctor does not throw or Basic Guarantee pop_front/pop_back O(1) No-fail erase O(N) No-fail if T's ctor does not throw or Basic Guarantee indexed access ( op[], at ) O(1) No-fail
std::array boost::array 固定長配列 T[N] の代わり initializer_list のある C++0x では組み込みの配列は全て std::array に置き換え可能
std::array boost::array Operation Complexity Exception Safe Copy / Assign O(N) Basic Guarantee Range Copy / Assign O(N) Basic Guarantee push_front/push_back N/A N/A insert(pos,...) N/A N/A pop_front/pop_back N/A N/A erase N/A N/A indexed access ( op[], at ) O(1) O(1)
std::list QLinkedList boost::container::list 双方向リンクリスト 中間への挿入時に要素を動かしたくない時に 10kB 程度のコンテナなら vector のほうが速い そのコードリンクリストを使うけどきっとベクタで必要十分 boost::container::stable_vector も検討しましょう
std::list QLinkedList boost::container::list Operation Complexity Exception Safe Copy / Assign O(N) Strong Guarantee Range Copy / Assign O(N) Strong Guarantee push_front/push_back O(1) Strong Guarantee insert(pos,...) O(1) Strong Guarantee pop_front/pop_back O(1) No-fail erase O(1) No-fail indexed access ( op[], at ) N/A N/A
std::forward_list boost::container::slist 単方向リンクリスト 特殊用途 通常は list を使いましょう インタフェースが少々特殊
std::forward_list boost::container::slist Operation Complexity Exception Safe Copy / Assign O(N) Strong Guarantee Range Copy / Assign O(N) Strong Guarantee push_front O(1) Strong Guarantee insert_after(pos,...) O(1) Strong Guarantee pop_front O(1) No-fail erase_after O(1) No-fail indexed access ( op[], at ) N/A N/A
std::map QMap boost::container::map いわゆるディクショナリ ハッシュ とは違う ( 使い方は一緒 ) 要素は常に Key でソートされている ほとんどの操作が O(log N) 使えるなら unordered_map/qhash を使おう
std::map QMap boost::container::map Operation Complexity Exception Safe Copy / Assign O(N) Strong Guarantee Range Copy / Assign O(N log N) Strong Guarantee insert O(log N) Strong Guarantee erase(key) O(log N) No-fail erase(pos) O(1) No-fail indexed access ( op[], at ) O(log N) Strong Guarantee
std::unordered_map QHash boost::unordered::unordered_map こっちが本当の ハッシュコンテナ ルックアップは平均的に定数時間 ハッシュ関数の用意が面倒 STL の実装によっては hash_map という名前で独自に用意されていることも
std::unordered_map QHash boost::unordered::unordered_map Operation Complexity Exception Safe Copy / Assign O(N), worst O(N^2) Strong Guarantee Range Copy / Assign O(N), worst O(N^2) Strong Guarantee insert O(1), worst O(N) Strong Guarantee erase O(1), worst O(N) No-fail indexed access ( op[], at ) O(1), worst O(N) N/A
boost::container::flat_map ソート済み vector の wrapper 挿入 削除時に要素の移動が発生してもよければ flat_map を検討しましょう
std::set boost::container::set 二分木 ( 多くは赤黒木 ) コンテナ 正直使い道が ソート済みベクタで大体事足りる
std::unordered_set QSet boost::unordered::unorderd_set std::set のハッシュテーブル版 使い道が
boost::container::flat_set ソート済み vector で実装された set やっぱり使い道が
で 結局どれ使えばいいの? Java 形式のイテレータが不要なら STL コンテナを使いましょう 例外安全に関する規定 パフォーマンス特性に関する規定が Qt コンテナには欠けている CoW はマルチコアでスケールしない Boost 内部にも STL コンテナの実装があります 必要に応じてアロケータを指定できます
で 結局どれ使えばいいの? 辞書的に使いたいなら( unordered_)map<key, T> 基本は vector<t> 末尾以外への挿入 削除が多いなら deque<t> 要素がでかい(256 B 以上 ) なら list<t> または boost::container::stable_vector<t> 挿入 削除時にイテレータ 参照を壊したくないなら list<t> 10kB 程度のコンテナなら何も考えずに vector<t>
実装の話 参照実装 libstdc++ 4.5.3 Qt 4.7.3 Boost 1.47 参考文献 オライリーいろいろ C++ In-Depth Series
std::vector template <typename T> class vector { T *start; T *finish; T *end_of_storage; /* */ }; 要素の先頭 要素の終端 ストレージの終端を指すポインタを保持 サイズの拡張は 2倍になるように行われる 最良のメモリ効率 vector<bool> トラップに注意
boost::container::vector template <typename T> class vector { T *start; size_t size; size_t capacity; }; std::vector と同じ vector<bool> トラップが無い VC++ で使うと vector<t>::iterator が T * であることを要求しているクソコードをあぶりだせる
QVector tempate <typename T> struct QVectorData { QAtomicIntRef ref; int alloc, size; uint sharable: 1; uint capacity: 1; T array[1]; /* */ }; template <typename T> class QVector { QVectorData<T> *d; /* */ }; Qt の可変長配列コンテナ C の 可変長構造体 で実装されている
boost::container::stable_vector template <typename T> struct node_type { void *up; T value; }; template <typename T> class stable_vector { vector<t> impl; /* */ }; vector と違い iterator が複雑 使い勝手は deque に近い
QList struct QListData { QBasicAtomicInt ref; int alloc, begin, end; bool sharable; void *array[1]; /* */ }; template <typename T> class QList { QListData *p; /* */ }; Data::array の型が T から void * に変わっている以外は QVector とほぼ同じ For most purposes, QList is the right class to use. 案外優秀な子
std::deque boost::container::deque template <typename T> struct deque_iterator { T *cur, *first, *last; T **node; }; ページ を管理する 有効なページ範囲は [ first, last) node ( ) は マップ後述 の要素を指している ( array<t *>::iterator の役割 )
std::deque boost::container::deque template <typename T> class deque { T **map; size_t map_size; iterator start, finish; /*...*/ }; map の マップ の先頭 ( array<t*, map_size>) の役割 [start, finish) は使用中のページ領域 [start, finish) は map の中央部分から使い 前後に伸長する
std::list boost::container::list template <typename T> struct list_node { list_node *next, prev; T data; }; template <typename T> struct list { list_node *list; }; 典型的な双方向リンクリスト 実際は code bloat を抑えるための thin wrapper idiom 等で複雑なコードに
QLinkedList struct QLinkedListData { QLinkedListData *n, *p; QBasicAtomicInt ref; int size; bool sharable; }; template <typename T> struct QLinkedListNode { QLinkedListNode *n, *p; T t; }; template <typename T> class QLinkedList { union { QLinkedListData *d; QLinkedListNode<T> *e; }; }; 参照カウントのためにおかしなデータ構造になっている 何をやっているのか正直よくわからない
std::array boost::array template < typename T, size_t N > class array { T data_[n]; /* */ }; ただの固定長配列 C++0x では完全に組み込み配列を駆逐可能 固定長なのでいろいろ制限は多い
map, set, hash Red-Black Tree とかハッシュとかよくわからんので勘弁してください むしろ誰か代わりに語ってください
まとめ コンテナの種類大杉 例外安全とマルチコアのパフォーマンスを気にしない かつ Java 形式の Iterator が要るなら QList を そうでなければ std::vector をまず検討する 基本は vector です deque や set, list は本当に必要な時だけ使う 自前での再実装だけは絶対にやめよう