• 検索結果がありません。

Green with White Lines

N/A
N/A
Info
ダウンロード
Protected

Academic year: 2021

シェア "Green with White Lines"

Copied!
41
0
0

読み込み中.... (全文を見る)

今ダウンロードする ( 41 ページ )

全文

(1)

各種コンテナの実装と性能

Qt 勉強会 福岡#4 @ kikairoya

(2)

About

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

(3)

Abstruct

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

(4)

STL Containers

● vector ● deque ● list/forward_list ● set/multiset ● map/multimap ● array

(5)

Qt Containers

● QVector ● QList ● QLinkedList ● ● QMap/QMultiMap ●

(6)

Boost Containers

● vector/stable_vector ● deque ● list/slist ● set/multiset/flat_set/flat_multiset ● map/mutlimap/flat_map/flat_multiap ● array

(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

(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

(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

(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

(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

(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

(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

(23)

boost::container::flat_map

● ソート済み vector の wrapper

● 挿入・削除時に要素の移動が発生してもよければ

(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>

(29)

実装の話

● 参照実装 – libstdc++ 4.5.3 – Qt 4.7.3 – Boost 1.47 ● 参考文献 – オライリーいろいろ

(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 { ● 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 { ● 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> ● 典型的な双方向リンク リスト ● 実際は 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 { ● 参照カウントのために おかしなデータ構造に なっている ● 何をやっているのか正 直よくわからない

(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 です

参照

今ダウンロードする ( PDF - 41 ページ - 309.51 KB )

関連したドキュメント

線形論理の誕生

前章 / 節からの流れで、計算可能な関数のもつ性質を抽象的に捉えることから始めよう。話を 単純にするために、以下では次のような型のプログラム を考える。 は部分関数 (

π(n−1) and such that t−n #=π(i)−i, for any 1≤i &lt

In the literature it is usually studied in one of several different contexts, for example in the game of Wythoff Nim, in connection with Beatty sequences and with so-called

自己双対多様体のツイスター空間

実際, クラス C の多様体については, ここでは 詳細には述べないが, 代数 reduction をはじめ類似のいくつかの方法を 組み合わせてその構造を組織的に研究することができる

We study the solvability of the fractional order inhomogeneous Cauchy problem Dαtu(t) =Au(t) +f(t), t &gt;0, 1&lt

We include applications to elliptic operators with Dirichlet, Neumann or Robin type boundary conditions on L p -spaces and on the space of continuous

u(t)∈C(t), for all t∈[0, T

In [13], some topological properties of solutions set for (FOSPD) problem in the convex case are established, and in [15], the compactness of the solutions set is obtained in

Numerical Blow-Up Time for a Semilinear Parabolic Equation with Nonlinear Boundary Conditions

We obtain some conditions under which the positive solution for semidiscretizations of the semilinear equation u t u xx − ax, tfu, 0 &lt; x &lt; 1, t ∈ 0, T, with boundary conditions

Consequently, for T1,T1 ∈Π(D1) such thatT2⊆T1 and T2 ⊆T1, we have T1D1T1

In this section we consider the submodular flow problem, the independent flow problem and the polymatroidal flow problem, which we call neoflow problems.. We discuss the equivalence

* , [9] 1. x S x S., x S. x S x / S. 1,. A B, x A x B. A B B A., A B.. 2 A, B, A B B A, A = B. N: Z: Q: R: A, B, A B = {x : x A x B},

しかし , 特性関数 を使った証明には複素解析や Fourier 解析の知識が多少必要となってくるため , ここではより初等的な道 具のみで証明を実行できる Stein の方法