Green with White Lines

Size: px

Start display at page:

Download "Green with White Lines"

けんじたけくま
4 years ago
Views:

1 各種コンテナの実装と性能 Qt #4 kikairoya

2 About 宮崎県都城市から来ました本職 : 精密機械設計組込機器開発 C++ とか出来ます Qt わかりません

3 Abstruct STL コンテナと Qt コンテナの比較データ構造パフォーマンス安全性インタフェースおまけで Boost コンテナも

4 STL Containers vector deque list/forward_list set/multiset map/multimap array unordered_set/unordered_multiset unordered_map/unordered_multimap

5 Qt Containers QVector QList QLinkedList QMap/QMultiMap QSet QHash/QMultiHash

6 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

7 Major Difference STL Container CoW しない全ての操作が例外安全の基本保証を満たす Qt Container CoW を行う例外安全に関しての規定が無い

8 std::vector QVector boost::container::vector 要素を連続的に格納するいわゆる可変長配列各要素のルックアップは定数時間末尾に対する挿入削除は償却定数時間 Stroustrup 曰くコンテナが必要な場合特に理由が無ければ vector を使おうと std::vector<bool> トラップに注意

9 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

10 QList boost::container::stable_vector 間接ベクタ list である必要はないけど T のコピーが重い時に sizeof(t) <= sizeof(t *) の場合は QVector と同じように振る舞う

11 std::deque boost::container::deque 要素をポインタを介して半連続的に格納イメージ的には間接リングバッファあるいはページコンテナ各要素のルックアップは定数時間 (2 段間接参照 ) 先頭末尾に対する挿入削除は定数時間ほとんどの操作は vector のほうが微妙に速い

12 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

13 std::array boost::array 固定長配列 T[N] の代わり initializer_list のある C++0x では組み込みの配列は全て std::array に置き換え可能

14 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)

15 std::list QLinkedList boost::container::list 双方向リンクリスト中間への挿入時に要素を動かしたくない時に 10kB 程度のコンテナなら vector のほうが速いそのコードリンクリストを使うけどきっとベクタで必要十分 boost::container::stable_vector も検討しましょう

16 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

17 std::forward_list boost::container::slist 単方向リンクリスト特殊用途通常は list を使いましょうインタフェースが少々特殊

18 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

19 std::map QMap boost::container::map いわゆるディクショナリハッシュとは違う ( 使い方は一緒 ) 要素は常に Key でソートされているほとんどの操作が O(log N) 使えるなら unordered_map/qhash を使おう

20 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

21 std::unordered_map QHash boost::unordered::unordered_map こっちが本当のハッシュコンテナルックアップは平均的に定数時間ハッシュ関数の用意が面倒 STL の実装によっては hash_map という名前で独自に用意されていることも

22 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

23 boost::container::flat_map ソート済み vector の wrapper 挿入削除時に要素の移動が発生してもよければ flat_map を検討しましょう

24 std::set boost::container::set 二分木 ( 多くは赤黒木 ) コンテナ正直使い道がソート済みベクタで大体事足りる

25 std::unordered_set QSet boost::unordered::unorderd_set std::set のハッシュテーブル版使い道が

26 boost::container::flat_set ソート済み vector で実装された set やっぱり使い道が

27 で結局どれ使えばいいの? Java 形式のイテレータが不要なら STL コンテナを使いましょう例外安全に関する規定パフォーマンス特性に関する規定が Qt コンテナには欠けている CoW はマルチコアでスケールしない Boost 内部にも STL コンテナの実装があります必要に応じてアロケータを指定できます

28 で結局どれ使えばいいの? 辞書的に使いたいなら( unordered_)map<key, T> 基本は vector<t> 末尾以外への挿入削除が多いなら deque<t> 要素がでかい(256 B 以上 ) なら list<t> または boost::container::stable_vector<t> 挿入削除時にイテレータ参照を壊したくないなら list<t> 10kB 程度のコンテナなら何も考えずに vector<t>

29 実装の話参照実装 libstdc Qt Boost 1.47 参考文献オライリーいろいろ C++ In-Depth Series

30 std::vector template <typename T> class vector { T *start; T *finish; T *end_of_storage; /* */ }; 要素の先頭要素の終端ストレージの終端を指すポインタを保持サイズの拡張は 2倍になるように行われる最良のメモリ効率 vector<bool> トラップに注意

31 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 * であることを要求しているクソコードをあぶりだせる

32 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 の可変長構造体で実装されている

33 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 に近い

34 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. 案外優秀な子

35 std::deque boost::container::deque template <typename T> struct deque_iterator { T *cur, *first, *last; T **node; }; ページを管理する有効なページ範囲は [ first, last) node ( ) はマップ後述の要素を指している ( array<t *>::iterator の役割 )

36 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 の中央部分から使い前後に伸長する

37 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 等で複雑なコードに

38 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; }; }; 参照カウントのためにおかしなデータ構造になっている何をやっているのか正直よくわからない

39 std::array boost::array template < typename T, size_t N > class array { T data_[n]; /* */ }; ただの固定長配列 C++0x では完全に組み込み配列を駆逐可能固定長なのでいろいろ制限は多い

40 map, set, hash Red-Black Tree とかハッシュとかよくわからんので勘弁してくださいむしろ誰か代わりに語ってください

41 まとめコンテナの種類大杉例外安全とマルチコアのパフォーマンスを気にしないかつ Java 形式の Iterator が要るなら QList をそうでなければ std::vector をまず検討する基本は vector です deque や set, list は本当に必要な時だけ使う自前での再実装だけは絶対にやめよう

スライド 1

スライド 1 今此処にある C++ ~ テンプレートと STL~ テンプレートの解説コンテナイテレータアルゴリズムアジェンダテンプレートとは型を外部から変更可能にした構文通常の構文 int max(int a, int b){ return a > b? a : b; テンプレートを使った構文 template T max(t a, T b){ return a > b?