まえがき
どうも、超ウィザード級C++erいなむ先生です（）
この記事は、C++ Advent Calendar 2016の1日目の記事です。
2日目はAgateさんの、ヘッダとソースでファイルを分ける 応用編です。
もちろん基本編があるようですので、合わせてどうぞ。
C++のつまずきポイント解説その１はこちらです。
C++のつまずきポイント解説その１
std::map
std::mapがわからない諸兄のために、軽く解説しよう。
std::mapは辞書であるとよく言われる。
検索ワード（別にワードでなくて数字でもいい）に対して値を返すからである。
mapの宣言は次のようにする。
std::map<std::string,int> m;
ひとつ目のテンプレートパラメータはKeyである。
ふたつ目のテンプレートパラメータはValueである。
Keyを指定するとValueが得られる。
例えば、名前と給与をmapに登録しておいて、
名前から給与を検索する場合を考える。
std::map<std::string,int> salary;
salary["John"] = 1400;
salary["Tom"] = 1000;
salary["Harry"] = 0;
int a = salary["John"]; // 1400
int b = salary["Tom"]; // 1000
int c = salary["Harry"]; // 0
mapの値の検索はvectorやarrayの検索と比べて高速である。
具体的には内部構造が赤黒木かなんかで実装されている気がするので。
要素数Nのmapの検索に要する時間計算量は O( logN )になるような気がする。
要素が自動で生成されることを理解する
[]演算子で存在しない要素にアクセスすると、自動的に要素が追加される！
#include <iostream>
#include <map>
using namespace std;
int main()
{
std::map<int,int> m;
cout << m.size() << endl; // 当然 0
cout << m[1] << endl; // 要素は存在しないがアクセスしている
cout << m.size() << endl; // 自動で要素が追加されているので 1
for (auto&& x : m) {
std::cout << x.first << " => " << x.second << std::endl;
}
return 0;
}
operator[]でアクセスするようなコードを書くと、気づかないうちに要素が量産されていることがある。
この仕様は競技プログラミングでは非常に便利である...
mapの要素の型宣言はautoを用いる
上記のコードでもrange-based forを用いる際に auto&& を用いた。
これを自分で書く場合に起こり得る問題がある。
map内部ではキーと値はstd::pairになっていますから。
std::map<std::string, int> m;
// ...
for ( const std::pair<std::string, int>& p : m ) {
// ...
}
このコードは意図したとおりに動くし、一見して間違いは見当たらない。
しかし問題はあるのである、おわかりだろうか？
わからない方が多いと思われる。
std::mapの内部で用いられているstd::pairのキーの要素型はconstなのである。
よって、正しくはconst std::pair<const std::string, int>&と書くべきなのである。
コンパイラはstd::<const std::string, int>オブジェクトをstd::pair<std::string, int>へ変換する手段を見つけ出そうと躍起になって頑張るだろう。
おそらく、コンパイラはpにバインドするために一時オブジェクトを作る。
一時オブジェクトはm内のオブジェクトをそれぞれコピーして作成され、pの参照を、この一時オブジェクトへバインドすることで実現されるはずだ。
明らかに、mの要素をpにバインドしたいだけなのに、このようなことが起こり得るのである。
このようなことを避けるために、推論できる型を自力で書くことは避けなければならない。
vectorの要素を参照するときはメモリの再配置に気をつける
まずはこれを見ていただきたい
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v = {1,2};
int& a = v[0];
cout << a << endl;
for(size_t i{3}; i<10;++i)
v.push_back(i);
cout << a << endl;
}
output
1
0
v[0]を参照する変数aの値が1のはずなのに、いつの間にか0になっている...
いや、いつの間にかではない！
2つの出力の間にあるのは7回のpush_backである、これのせいに違いない。
結論を言うと、vectorの要素追加によって、メモリの場所が移動したせいである。
vectorに新たな要素を追加する場合、領域が足りなくなったらメモリの再配置が起こるため、要素を参照する場合は気をつける必要がある。
要素数とリザーブ領域
要素を追加したとき、vectorが確保した領域が足りなくなった場合には、メモリを再配置して元のデータを移動する。
メモリの再配置は決して軽いとはいえないため、要素を格納している領域とは別に要素を追加した時のために余剰の領域を確保する機能が備わっている。
要素サイズ＋ 未使用サイズ ＝ リザーブ領域
である。
size()
要素サイズはメンバ関数size()で取得できる。
capacity()
リザーブされたサイズはメンバ関数capacity()で取得できる。容量を超えない範囲では要素を追加してもメモリの再配置が起こらない。
shrink_to_fit()
使われていないリザーブ領域を開放して、リザーブ領域を要素サイズぴったりにしてくれる（ように要請する）メンバ関数shrink_to_fit()がある。
ここで、「要請する」と書いたのは、規格上ではリザーブ領域を切り詰める保証がされていないからである（どのくらい切り詰めるのかは実装依存、したがって何もしないshrink_to_fitの実装があったとしても規格上は合法）。
resize()
サイズを指定して要素をデフォルト値で埋めるにはresize(size_t N)を使いましょう。
reserve()
サイズを指定してリザーブ領域を確保するにはreserve(size_t N)を使いましょう。
Nが現在の要素サイズよりも少ない場合は何も起こりません。
ところで、容量はどのように確保されるのでしょうか？
以下のコードでその詳細がわかります。
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v = {};
auto print = [&v]{
auto size = v.size();
auto capacity = v.capacity();
cout << "size = " << size
<< ", capacity = " << capacity
<< ", capacity - size = " << capacity << " - " << size << " = " << capacity - size << endl;
};
v.push_back(1);
print();
v.push_back(2);
print();
v.push_back(3);
print();
v.push_back(4);v.push_back(5);
print();
v.shrink_to_fit();
print();
}
output
size = 1, capacity = 1, capacity - size = 1 - 1 = 0
size = 2, capacity = 2, capacity - size = 2 - 2 = 0
size = 3, capacity = 4, capacity - size = 4 - 3 = 1
size = 5, capacity = 8, capacity - size = 8 - 5 = 3
size = 5, capacity = 5, capacity - size = 5 - 5 = 0
この挙動を見ると、容量の確保戦略がわかります。
容量が1,2,4,8となっています。
容量が足りなくなったときに新しく確保する容量を倍々にしていく戦略です。
これがメジャーなC++コンパイラ（gcc,clangなど）の実装です。
MSVCは知らんな！
メモリの再配置が頻繁に起こるような場合は予めリザーブする方が速くなります。
#include <iostream>
#include <vector>
#include "time_elapsed.hpp"
using namespace std;
int main()
{
CRANBERRIES_TIME_ELAPSED_NANO(
vector<int> v;
// reserve しない
for (int i{}; i< 1000; ++i) v.push_back(i);
);
CRANBERRIES_TIME_ELAPSED_NANO(
vector<int> v;
v.reserve(1000); // 予めリザーブする
for (int i{}; i< 1000; ++i) v.push_back(i);
);
}
output
81927[nano sec]
32919[nano sec]
-O2オプション
28569[nano sec]
5055[nano sec]
やはり違いがでますね（）
条件演算子を理解する
条件演算子を知らない諸兄のために、軽く解説しよう。
operator ? : は式の一種である。
3項を引数に取る演算子はC++にこれ一つしかないので、3項演算子と呼ばれることが多い。
しかし、正式名称は条件式であり、演算子の名称は条件演算子である。
条件演算子の文法は次のようなものだ
cond ? a : b;
condは暗黙にbool値に変換される。
condの式が評価され、完全に副作用が完了してから次に移行する。
condがtrueなら、aが、falseならbが評価され条件式の結果になる。
例えば、a,bの内で大きい方の値を得たいならば
int a = 3;
int b = 4;
int max = a < b ? b : a;
cout << max << endl;
のようにする
if文より記述量が少ないので個人的に好きです
演算子の優先順位
よくある間違い
int a = 3;
int b = 4;
cout << (a < b) ? b : a << endl; // Oooops!
C++の演算子優先順位により、
operator<<は優先順位7。
operator ? :は優先順位15。
operator<<の方が優先順位が高く、
条件演算子の呼び出しより先に左シフトが呼び出され、結果コンパイルエラーになる（優先順位については下記コラムを参照のこと）。
正解：条件演算子の全体を()で囲む
int a = 3;
int b = 4;
cout << ( a < b ? b : a ) << endl; // 4
コラム：演算子の優先順位
| 演算子の説明 | operator |
|---|---|
| Group 1 precedence, no associativity | |
| スコープ解決 | :: |
| Group 2 precedence, left to right associativity | |
| オブジェクトからメンバーへのアクセス | . |
| ポインターからメンバーへのアクセス | -> |
| 配列添字 | [ ] |
| 関数呼び出し | ( ) |
| 後置インクリメント | ++ |
| 後置デクリメント | –– |
| 型名 | typeid( ) |
| const 型変換 | const_cast |
| 動的型変換 | dynamic_cast |
| 再解釈型変換 | reinterpret_cast |
| 静的型変換 | static_cast |
| Group 3 precedence, right to left associativity | |
| オブジェクトまたは型のサイズ | sizeof |
| 前置インクリメント | ++ |
| 前置デクリメント | –– |
| 1 の補数 | ~ |
| 論理 NOT | ! |
| 単項マイナス符号 | - |
| 単項プラス | + |
| アドレス取得 | & |
| 参照剥がし | * |
| 動的割当 | new |
| オブジェクトの破棄 | delete |
| Cスタイルキャスト | (Type) |
| Group 4 precedence, left to right associativity | |
| オブジェクトからメンバーへのポインターへのアクセス | .* or –>* |
| ポインターからメンバーのポインタへのアクセス | ->* |
| Group 5 precedence, left to right associativity | |
| 乗算 | * |
| 除算 | / |
| 剰余 | % |
| Group 6 precedence, left to right associativity | |
| 加算 | + |
| 減算 | – |
| Group 7 precedence, left to right associativity | |
| 左ビットシフト | << |
| 右ビットシフト | >> |
| Group 8 precedence, left to right associativity | |
| より小さい | < |
| より大きい | > |
| 以下 | <= |
| 以上 | >= |
| Group 9 precedence, left to right associativity | |
| 等価比較 | == |
| 非等値 | != |
| Group 10 precedence left to right associativity | |
| ビットごとの AND | & |
| Group 11 precedence, left to right associativity | |
| ビットごとの排他的 OR | ^ |
| Group 12 precedence, left to right associativity | |
| ビットごとの包括的 OR | ｜ |
| Group 13 precedence, left to right associativity | |
| 論理 AND | && |
| Group 14 precedence, left to right associativity | |
| 論理 OR | ｜｜ |
| Group 15 precedence, right to left associativity | |
| 条件 | ? : |
| Group 16 precedence, right to left associativity | |
| 代入 | = |
| 乗算代入 | *= |
| 除算代入 | /= |
| 剰余代入 | %= |
| 加算代入 | += |
| 減算代入 | –= |
| 左シフト代入 | <<= |
| 右シフト代入 | >>= |
| ビットごとの AND 代入 | &= |
| ビットごとの包括的 OR 代入 | ｜= |
| ビットごとの排他的 OR 代入 | ^= |
| Group 17 precedence, right to left associativity | |
| throw 式 | throw |
| Group 18 precedence, left to right associativity | |
| コンマ | , |
型とvalue category
型とvalue categoryはaとbにおいて一致していなければならない。
一致していない場合には複雑なルールにおいて型やvalue categoryをすり合わせようとコンパイラが苦心する。
詳細については述べず、肝要だと思われる幾つかの例を挙げるに留める。
cond ? a : b
と書いたとき、aとbの型が一致していなければならない。
異なる型を持つ式を書いた場合は暗黙の型変換によって型のすり合わせが行われ、すりあわせることができなければコンパイルエラーになる。
例えば
decltype( true ? 4.0f : 4.0 ) // double
decltype( true ? 4 : 4.0 ) // double
decltype( true ? "const char *" : std::string{} ) // std::string
のようになる。
CV修飾が一致していない場合には、両方の型のCV修飾を合わせたものにすり合わせる。
int a{};
int const b{};
decltype( true ? a : b ) // int const&
ここで、aとbは両方lvalueなので条件演算子の結果もlvalueになる。
このことから、次のように書くこともできる。
int a{3};
int b{4};
( a < b ? a : b ) = 2; // a = 2
型やvalue categoryの不一致で変換が起こった場合は条件式の結果はprvalueになると思っていいです。
a,bをthrow式にすることもできます。
a,bのどちらかがthrow式（両方ではない）の場合、条件式の結果はC++11では他方の型のprvalueになりますが、C++14では他方の型のvalue categoryが評価されます。
a,bの両方がvoidであれば、条件式の結果はvoidのprvalueになりますが、これにa,bが両方throw式である場合も含まれます。
次のように使うことができます（？）。
a = std::exp(a) == std::numeric_limits<double>::infinity()
? throw std::overflow_error{"overflow"}
: std::exp(a);
通常、a,bの片方をvoid、他方をvoidでない型と評価される式にすることはできない。
これができるのはthrow式のときのみである。
条件式のネスト
左から右に評価される。
条件を順番にチェックして値を返す場合に有用である。
例えば、僕が研究している区間演算の掛け算では
区間 X = [a,b], Y = [c,d] に対して
X×Yを次のように計算する
| b < 0 | a < 0 < b | 0 < a | |
|---|---|---|---|
| d < 0 | [bd, ac] | [bc, ac] | [bc, ad] |
| c < 0 < d | [ad, ac] | [min(ad, bc), max(ac, bd)] | [bc, bd] |
| 0 < c | [ad, bc] | [ad, bd] | [ac, bd] |
if文を使えばいいのだけれど、どのコントロールブロックにおいても区間が返るので、条件式が使える。
擬似コードは以下のようになるだろう。
その１：線形パターン
cond ? a : b におけるbに条件式を入れ子にするパターン。
条件が順番にチェックされていき合致したところで値が返る。
return b < 0 && d < 0 ? [bd, ac]
: b < 0 && c < 0 < d ? [ad, ac]
: b < 0 && 0 < c ? [ad, bc]
: 0 < a && d < 0 ? [bc, ad]
: 0 < a && c < 0 < d ? [bc, bd]
: 0 < a && 0 < c ? [ac, bd]
: a < 0 < b && d < 0 ? [bc, ac]
: a < 0 < b && 0 < c ? [ad, bd]
: [min(ad, bc), max(ac, bd)] ;
その２：入れ子パターン
ifブロックにifブロックが記述されているものを条件演算子でエミュレートするとこうなる。
return b < 0
? d < 0 ? [bd, ac]
: 0 < c ? [ad, bc]
: [ad, ac]
: 0 < a
? d < 0 ? [bc, ad]
: 0 < c ? [ac, bd]
: [bc, bd]
:
d < 0 ? [bc, ac]
: 0 < c ? [ad, bd]
: [min(ad, bc), max(ac, bd)] ;
控えめに言ってもキモいコードですね、ハイ
実際書いたコードは魔黒を駆使しててアレなので、興味があれば見てください
置いときます
区間演算の掛け算の実装
便利な機能を知っておく
C++の標準ライブラリは一見ややこしかったりしますが、知っておかないと車輪の再開発をしてしまいます。
結果として、バグって時間を無駄にしたり、パフォーマンスの低い関数を作ったりしがちです。
ここでは、よくある処理を行う際に便利な関数やクラスを紹介します。
文字列を分割(split)する
文字列のsplit関数はC++にはありません！！
そういった機能を自作している記事をまま見かけます。
ここでは、デリミタを正規表現で指定できるようにしましょう。
<regex>に用意されているsregex_token_iteratorを使います。
以下、適当実装です。
#include <iostream>
#include <string>
#include <regex>
#include <vector>
#include <utility>
std::vector<std::string> split_impl( std::string&& s, std::regex&& r ) {
return { std::sregex_token_iterator{ s.begin(), s.end(), r, -1 }, std::sregex_token_iterator{} };
}
auto split( std::string s, std::string pattern ){
return split_impl( std::move(s), std::regex{pattern} );
}
int main()
{
for (
auto&& e :
split( "123,456,789", "," )
){
std::cout << e << std::endl;
}
return 0;
}
アルゴリズム系
アルゴリズムに関してはヘッダに色々とありますので、自分で書く必要はほぼないというスタンスで一度、cpprefjp-algorithmなどを見て標準で提供される関数の組み合わせで処理を実現できないかを検討しましょう。
nth_element とか覚えておいたら稀に便利かも。
#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
std::vector<int> v = {5, 10, 4, 7, 1, 9, 8, 6, 2};
// 4番目に小さい値より小さい値を前に集める
std::nth_element(v.begin(), v.begin() + 3, v.end());
for( auto const& e : v) {
std::cout << e << std::endl;
}
}
2
1
4
5
10
9
8
6
7
あとね、<numeric>ヘッダにも便利な関数があってね。
cpprefjp-numeric見たら分かるけど、accumulateとかiotaがあるよね。
iota使ってる？？
連続したシーケンスが作れるよ。
#include <numeric>
#include <iostream>
#include <array>
int main()
{
std::array<int, 10> arr;
std::iota(ar.begin(), ar.end(), 0);
for (int x : arr) {
std::cout << x << std::endl;
}
}
0
1
2
3
4
5
6
7
8
9
時間が無い
この辺で執筆時間が足りなくなった。
スマポとか書きたいことがまだあるけど、またの機会に。
跋文
間違いや質問、ご意見等は
コメントしていただくか
いなむ先生 | Twitter
までご一報ください
できるだけすみやかに対応させていただきます
実行時間計測に使ったコードはこれです
time_elapsed.hpp
All text is available under the CC0 1.0 Universal license.