素因数分解
以下のような素因数分解ライブラリをよく見かける
template<typename T>
std::map<T,T> prime_factor(T n){
std::map<T,T> res;
for (T i=2;i*i<=n;i++){
while( n%i == 0){
++res[i];
n/=i;
}
}
if (n!=1) res[n] = 1;
return res;
}
しかしここで疑問なのが、存在しない参照を行っていることである。またコンパイラなり処理系に依存してしまうような未定義動作にも見えなくもない。
せっかくなのでC++の規格を読んで確認してみることにした
参照したのはC++14 (C++1y) ISO/IEC 14882:2014 N4140の23.4.4.3 map element access
以下が規格からの抜粋である
T& operator[](const key_type& x);
1 Effects: If there is no key equivalent to x in the map, inserts value_type(x, T()) into the map.
2 Requires: key_type shall be CopyInsertable and mapped_type shall be DefaultInsertable into *this.
3 Returns: A reference to the mapped_type corresponding to x in *this.
4 Complexity: Logarithmic.
規格を読んだのは初めてだが、4点に分けて明快に実装されているべきことが書いてある。
存在しないkeyが参照された場合の動作は"Effect"の部分にかかれている。keyとしてx,valueとしてTのデフォルトコンストラクタが呼ばれる。
int やlong longでどうなるのかはちょっとわからなかったがDefaultConstructibleでなおかつクラス型でない場合は、ゼロ初期化されるらしい（C++ reference）、おそらく規格なのだろうが規格のどこに書いてあるのかはよくわからなかった。
そしてReturnsの項目によれば、*thisのkeyに対応する参照が返ることになっているとわかる。（これは当たり前だが）
計算量は$O(\log n)$（平衡二分木なので）
まとめると、基本的には存在しないkeyを参照した場合、0あるいはデフォルトコンストラクタで生成されたものが勝手に入ってくれる。
そのため、カウンターのようなものを実装する場合（すなわちvalueがintやlonglongな場合）は、keyの存在を確認せずにdict[key]++として大抵（規格通りに実装された全て？）の処理系で正しく動くことが分かった。。(なお本当にcount目的だったらunordered_mapを使うべきかもしれない)
結局解決していない初期化について(T()と書かれた部分について、int型ではどのように動作すると規格化されているか)に詳しい方などからのコメントをお待ちしています。