unordered_map について - mayoko’s diary
unordered_map で辛い思いをしたので twitter でわーわー言ってたらいろいろ勉強になったのでメモします。 まとめ 基本的にチェイン法っていうのでやってるっぽい vector< list< T > > みたいのをイメージするとわかりやすい 詳細 まとめで書いたように, 基本的には vector< list< T > > というのが全部説明している気がします。 find() は平均計算量 O(1), 最悪計算量 O(n) find() は, 基本的にはハッシュ値で vector にランダムアクセスするだけで目的のものが見つかるので O(1) だが, ハッシュ値がかぶっているものがあると, vector の要素のリストを線形探索しないといけない。なので最悪 O(n) insert(), delete() も平均計算量 O(1), 最悪計算量 O(n) 結局消す, 入れる場所を探
自作クラスをムーブする - Qiita
ユーザー定義のクラスにmove constructorを追加するための方法についてまとめます。 既存の型にstd::move使うと便利なので、自作の型に対しても定義したい、という方向けです。 先に結論をまとめておくと、注意するべきは以下の3点です： ユーザー定義のコピーコンストラクタやデストラクタがあるとデフォルトのムーブコンストラクタは作られない ムーブされた残り滓a = std::move(b)のbのデストラクタは呼ばれる noexcept付けないとムーブの恩恵が得られなくなる場合がある ムーブコンストラクタはいつ勝手に作られるの？ unique_ptrやvectorの様な既存の型を複数個組合せた構造体 において期待されるムーブコンストラクタは、 個々の要素p, vのムーブコンストラクタをそれぞれ呼び出すようなものでしょう。 以下の5つの条件を満す場合、デフォルトのムーブコンストラクタ
右辺値参照・ムーブセマンティクス [N2118] - cpprefjp C++日本語リファレンス
このページはC++11に採用された言語機能の変更を解説しています。 のちのC++規格でさらに変更される場合があるため関連項目を参照してください。 概要 ムーブセマンティクスはコピーコストの削減を主な目的としており、また所有権の移動を実現する。 右辺値参照はムーブ元のオブジェクト（右辺値）を束縛するための言語機能である。 右辺値（Rvalues）と左辺値（Lvalues）について 誤解を恐れずに言えば、右辺値とは名前をもたない一時的なオブジェクトである。 また、左辺値とは明示的に実態のある名前付きオブジェクトである。 struct Foo{} ; int f() { return 0 ; } int main() { int i = 0; i; // 名前付きオブジェクトは左辺値 0; // リテラル値は右辺値 Foo x ; x; // 名前付きオブジェクトは左辺値 Foo(); // コ
Google、STLのmap/setと互換性のあるコンテナをBツリーで実装した「C++ B-Tree」を公開 | OSDN Magazine
Googleは2月1日、mapやsetといったコンテナをBツリーで実装したC++テンプレートライブラリ「C++ B-Tree」のリリースを発表した。STLのmapやset、multimap、multisetとほぼ互換性のあるBツリー実装で、STLのmapやsetなどよりも消費メモリが少なく、またキー検索などの処理速度が向上しているという。 C++ B-TreeはB木（Bツリー）構造を使って実装されたC++向けコンテナライブラリ。STL（Standard Template Library）のmapおよびset、multimap、multisetと同様の機能を持つ「btree_map」および「btree_set」、「btree_multimap」、「btree_multiset」といったコンテナを提供する。 STLのコンテナは赤黒木（Red Black Tree）を用いて実装されることが多い。
C++11で、chronoライブラリを使って時間を計測する - minus9d's diary
C++11で新しく加わったchronoライブラリを使うと、簡単に経過時間が計測できる。もう環境依存のコードを書かなくてよくなるなら嬉しい。 サンプルコードは以下。シンプルなのですぐわかると思う。 #include <iostream> #include <chrono> int main() { auto start = std::chrono::system_clock::now(); // 重い処理 long long j = 0; for(int i = 1; i <= 100000000; ++i) { j += i; } auto end = std::chrono::system_clock::now(); // 経過時間をミリ秒単位で表示 auto diff = end - start; std::cout << "elapsed time = " << std::chron
C++11 固定長配列クラス std::array 入門
C++11 固定長配列クラス std::array とは std::array は C++11 で追加された固定長配列のコンテナクラスだ。 通常配列では、std::vector の size() や back() などの便利な機能が使えない。 それらを使いたいけど、サイズは固定でいいので vector を使うほどでもない。ってときは std::array の出番だ。 データ構造 array は vector や list のようなデータ構造を持たず、通常配列と同じように要素のためにだけメモリを消費する。 その分、vector に比べるとメモリ効率がいいのだが、要素数が多い場合はその効果は無視できるほどだ。 array の交換においては、中身のデータを交換するしかなく O(N) の処理時間を要する。 vector 等であればデータ領域へのポインタを交換するだけなので O(1) の処理時間で済
shared_ptrの使い方を知りたかったからいろいろ試してみた - uhiaha888’s diary
タイトルのとおりです。 基本的な使用方法 まず基本的な使い方。 #include "stdafx.h" #include <memory> #include <iostream> class Hoge { public: Hoge(){} ~Hoge(){ std::cout << "Hogeのデストラクタだよ" << std::endl; } int number_; }; int _tmain(int argc, _TCHAR* argv[]) { { std::shared_ptr<Hoge> hoge1(new Hoge); // 初期化 hoge1->number_ = 30; { std::shared_ptr<Hoge> hoge2 = hoge1; std::cout << "hoge1->number_ : " << hoge1->number_ << std::endl
std::swapで配列をスワップする
C++のstd::swapを使うと std::swap(a, b) のようにして、変数aとbの値を入れ替えることが出来る。 これは配列に対しても適用出来る。例えば、以下のようにして配列a[]と配列b[]をスワップ出来る。 #include <iostream> using namespace std; void dump(int arr[], int sz) { for (int i = 0; i < sz; i++) cout << arr[i] << " "; cout << endl; } int main(int argc, char **argv) { int a[] = {1,2,3}; int b[] = {4,5,6}; swap(a, b); dump(a, 3); // 4 5 6 dump(b, 3); // 1 2 3 return 0; } また、行列（二次元配列
生配列よりもstd::arrayを使った方が良い理由 - ぷろみん
概要 生配列を使う人がstd::arrayを使うきっかけになれば良いなと思います。 パフォーマンス 最適化をかければstd::arrayは生配列と全く同じアセンブリを吐き出す事が知られています。 つまり、パフォーマンスに差はありません。 アルゴリズム アルゴリズムに関しては生配列にも適応できるので問題無いでしょう。 std::array<int, 10> a; std::fill(a.begin(), a.end(), 10); int b[10]; std::fill(std::begin(b), std::end(b), 10); forのイテレーション イテレーションに関してはどれも割と難有りですね。 range based forが圧倒的にシンプルです。 生配列のサイズを取得するのにtemplate関数を作らなければいけないのが面倒です。 マクロは個人的にはやめた方が良いと思います
C++11スマートポインタで避けるべき過ち Top10 | POSTD
(注：2017/10/25、いただいたフィードバックを元に翻訳を修正いたしました。修正内容については、 こちら を参照ください。) 私は新しいC++11のスマートポインタをとても気に入っています。自分でメモリを管理するのが嫌だと感じる多くの仲間たちにとって、これはいろいろな面で天の助けでした。私の場合、このおかげで新人にC++を教えるのがずっと楽になりました。 しかし、C++11のスマートポインタを幅広く使っていた2年ちょっとの間で、使い方を誤ると、プログラムの効率が落ちたりクラッシュして壊れたりするという事態に何度も遭遇しました。参照用に、以下に例を載せました。 まずはこれらの”過ち”を、簡単なAircraftクラスを例に取って見てみましょう。 class Aircraft { private: string m_model; public: int m_flyCount; weak_p
シンプルな配列クラスを使って「右辺値参照」と「ムーブセマンティクス」を知る - Qiita
C++11 の新しい機能に「右辺値参照」と「ムーブセマンティクス」があります。 ググればこれらに関して解説されてるサイトが結構ありますが、一般的には理解しづらいものとして扱われてるみたいです。 かくいう自分もよくわかりませんでした……。 ですので、今回は至ってシンプルな配列クラスを使って、これらが何を意味するのかを知ろうかと思います。 従来は「コピー」 まずは、「右辺値参照」と「ムーブセマンティクス」を使わないコードを見てみます。 # include <iostream> using namespace std; struct Array { typedef int ValueType; ValueType *p; int length; // コンストラクタ Array(int _length) : p(new ValueType[_length]) , length(_length)
C++0x の右辺値参照がこんなに難しいわけがない。 - C++でゲームプログラミング
C++0xのアレです。 これに関してはさんざん解説がされているとは思いますが、自分がイマイチ理解していなかったのでまとめてみました。 概念や細かい仕様なんかは書いてないのでありからず…。 あとテスト用のコンパイラは、gcc-4.5.0 です。 ☆参照渡し C++ では、型名に & を付けることでオブジェクトのアドレスを受け取り、値の参照を行うことが出来ます。 int n = 10; int& ref = n; // int* ref = &n; を行っているイメージ ref = 3; // ref は n を指しているので、代入すれば n も変わる ここで重要なのは、参照渡しは値のコピーを行わない事です。 まぁこれに関しては、ポインタ渡しと同じですね。 関数の引数を参照で受け取るのは、無駄なコピーを行わない為です。 void hoge(std::string& str){} std::st
「std::vector」観察記録 ～慣れ親しんだ可変長配列の仕組みとふるまいを検証してみた
#ifndef NOVICE_VECTOR_H__ #define NOVICE_VECTOR_H__ template<typename T> class novice_vector { private: T* data_; // 要素格納領域 size_t size_; // 要素数 size_t capacity_; // 容量（格納可能な要素数） public: novice_vector() : data_(nullptr), size_(0), capacity_(0) {} ~novice_vector() { delete[] data_; } size_t size() const { return size_; } size_t capacity() const { return capacity_; } void clear() { size_ = 0; } // 少
n2930: Range-based for loopについて
n2930: Range-Based For Loop Wording (Without Concepts) 今回、フランクフルト会議でconceptが廃止されたことにより、conceptに依存している機能は、すべてconceptに依存しないように変更しなければならなくなった。Range-based forは、conceptあってこその機能なのだ。concept mapがあるからこそ、既存の型にも、容易にRange-based forを適用できるようになるはずだったのだ。それが、conceptがない今、どうするのか。 答え：ADLを使う。 Range-based forは以下のような構文になっている。 for ( for-range-declaration : expression ) statement これは、コンパイラによって、以下のように変換される。 { auto && __ran
std::unordered_map のキーに独自の型を使用する - Qiita
C++11 で追加された std::unordered_map は、連想配列を扱うことができる。 以前からある std::map では、キーとして扱えることができるのは 順序関係が定義されたオブジェクトのみである。一方、 std::unordered_map では順序関係が定義されていキーを使うことができ、純粋な連想配列（ハッシュテーブル）として使うことができる。 ただし、 std::unordered_map のキーはハッシュ値へ変換できる必要がある。多くの標準型のように std::hash() でハッシュ値への変換が定義されている型はそのままキーに使うことができるが、自分で定義した型など変換が定義されていない型をキーとして使用する場合はハッシュ計算を行う関数を自分で用意する必要がある。 このハッシュ関数を定義するには、 std::hash() を特殊化する方法と、関数オブジェクトを作成
mapとunordered_mapの違いについてまとめておく - yasuhisa's blog
NLPだとstd::mapとtr1::unordered_mapなら後者を使うことになることが多いと思うけど、あれこれ混乱してきたのでメモる。NLPerなら押さえておくべき常識のはず。。。 それぞれの特徴 データ構造 std::map tr1::unordered_map 実装 赤黒木 ハッシュテーブル find log n Average case: O(1), Worset case: O(n) insert log n Average case: O(1), Worset case: O(n) delete log n Average case: O(1), Worset case: O(n) メリット キーでソート済みなことが保障されているので、ある範囲でiterationさせたいとき、deleteするなどの操作を効率的に行うことができる バケット数を最初にきちんと設定しておけば大
やねうらおが本当に必要だったもの
range-based forはコンピューター将棋で使えるのか？ | やねうら王 公式サイト やねうらおが、range-based forが使えないとこぼしている。しかしその利用例をみるに、そもそもrange-based forを使うべきではない。 range-based forは、イテレーターというコンセプト（まだコンセプト機能はC++にないが）に従っている。イテレーターはポインター操作をモデルとしている。 イテレーターは要素群の中のある要素を指していて、operator *で要素を参照できる。 イテレーターの指す要素は、operator ++で次の要素に移動できる。 イテレーターはhalf-openとなっていて、要素群の最後の要素のひとつ次の、何も指していない状態のイテレーターが存在する。これを番兵のように使い要素の端に到達したことを判定する 一方、やねうらおのコードは、本来イテレータ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
How to redirect cin and cout to files?
C++のmt19937は環境非依存だがdistributionは環境依存 - Qiita
C++ std::vector同士の連結方法 - Qiita
