std::vector をがんばって高速に resize する - Qiita
あらまし プロファイラとにらめっこしながら気合を入れて最適化していくと、最終的に上位に std::vector<char>::resize() が残った、という経験が度々ある。 該当ケースは大抵 std::vector<char> を一時バッファとして利用しており、頻繁に resize() が呼ばれ、サイズは数十～数百 MB 規模に及ぶ、といった感じである。std::vector の resize() は新規に追加される要素に対してはコンストラクタを呼ぶが、組み込み型の場合はゼロクリアがなされる。大きなメモリ領域へのゼロクリアは重い処理であるため、プロファイル上位に残ることになるのだが、一時バッファは基本的にゼロクリアは不要であり、純粋に時間の無駄である。この無駄をなんとかしたい。 根本的な話として、こういう状況では std::vector<char> は使うべきではないと思う。mallo
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) 結局消す, 入れる場所を探
【C++】関数を引数に渡す色々な方法【STL テンプレート 関数ポインタ】
std::functionやテンプレート、関数ポインタを活用する複数の方法を紹介します。後半ではそれぞれの方法のメリットとデメリット、注意点等を説明します。 std::function テンプレート 関数ポインタ どれを使うべきか std::function std::functionクラスのテンプレート引数に、引数として渡したい関数のシグネチャの一部（引数型と戻り値型）を記述します（例: int(int)）。 int call(std::function<int(int)> fn) { return fn(3); } auto fn = [](int v) { return v * 2; }; call(fn); // 6 // int gn(int v) { return v * 3; }; call(gn); // 9 // #include <ctype.h> // int isa
自作クラスをムーブする - Qiita
ユーザー定義のクラスにmove constructorを追加するための方法についてまとめます。 既存の型にstd::move使うと便利なので、自作の型に対しても定義したい、という方向けです。 先に結論をまとめておくと、注意するべきは以下の3点です： ユーザー定義のコピーコンストラクタやデストラクタがあるとデフォルトのムーブコンストラクタは作られない ムーブされた残り滓a = std::move(b)のbのデストラクタは呼ばれる noexcept付けないとムーブの恩恵が得られなくなる場合がある ムーブコンストラクタはいつ勝手に作られるの？ unique_ptrやvectorの様な既存の型を複数個組合せた構造体 struct MyStruct{ std::unique_ptr<MyStruct> p; std::vector<int> v; }; において期待されるムーブコンストラクタは、 個
右辺値参照・ムーブセマンティクス [N2118] - cpprefjp C++日本語リファレンス
概要 ムーブセマンティクスはコピーコストの削減を主な目的としており、また所有権の移動を実現する。 右辺値参照はムーブ元のオブジェクト（右辺値）を束縛するための言語機能である。 右辺値（Rvalues）と左辺値（Lvalues）について 誤解を恐れずに言えば、右辺値とは名前をもたない一時的なオブジェクトである。 また、左辺値とは明示的に実態のある名前付きオブジェクトである。 struct Foo{} ; int f() { return 0 ; } int main() { int i = 0; i; // 名前付きオブジェクトは左辺値 0; // リテラル値は右辺値 Foo x ; x; // 名前付きオブジェクトは左辺値 Foo(); // コンストラクタの戻り値は右辺値 f(); // 関数の戻り値は右辺値 } 右辺値参照は、右辺値のみを束縛する参照である。 C++11からは、型Tに対
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; } // 少
/proc/cpuinfo: C++のムーブと完全転送を知る
社内勉強会、今期（と言ってももうあと1ヶ月もないですが）は、数理最適化勉強会と、Effective Modern C++輪読会をしています。この記事は、後者のEffective Modern C++輪読会で、『Effective Modern C++』5章の一部を輪読した時の資料を流用したものです。 C++11と言えば、昔のC++(03)から色々あって多くの機能が追加されとても便利になったバージョンです。さらに、C++14は11では間に合わなかった・忘れていた色々な便利なものを補填したもので、Effective Modern C++輪読会は、『Effective Modern C++』を教科書にしながらこのC++11/14について学ぶ会になっています。 時は既に2016年、gccもclangもMSVC++も概ねC++14が使えるようになっており、もはやC++14が使えないコンパイラにはC+
C++のmt19937は環境非依存だがdistributionは環境依存 - Qiita
C++11の乱数、mt19937はデフォルトのシード値まで決まっているのに、uniform_int_distributionの結果が環境依存で使い勝手が悪い。http://t.co/xdUwvgJCHzhttp://t.co/6wpL2c9hbz — kusanoさん@がんばらない (@kusano_k) 2015, 7月 1 常に同じ乱数を使いたいという状況がある。例えば、テストケースをランダムに生成してテストしているときに「123番目の結果がおかしい」と共有できると便利だし、論文の実験プログラムなどは再現性が重要なので同じプログラムを他の人のところで動かしたら厳密に同じ結果が出てほしい。 Cのrand()はこの条件を満たさない。srand()に同じ値を与えて初期化すれば、環境が同じならば常に同じ値が返ってくるが、別の環境では値が異なる。 #include <iostream> #inc
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
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
std::valarrayの使い方 - Qiita
How to redirect cin and cout to files?