C++ イテレータインクリメント時の前値、後置の違い
C++ではforループなどでイテレータのインクリメントをする際、前値形式(例: ++itr)と後置形式(例: itr++)のどちらの方法でインクリメントしても計算結果は同じになりますが、多くの場合 わずかですが前値形式(++itr)の方が後置形式(itr++)より高速に動作します。
理由はイテレータがclassとして定義されている場合、後置形式では
内部でインクリメント前のイテレータ一時オブジェクトとしてをコピーしておき
インクリメント後にコピーしておいた一時オブジェクトを返す
というような実装になっていることが多いからです。
int型やポインタ型などの組み込み型の場合、インクリメントの際の前値と後置にパフォーマンスの差は無いはずですが、C++では特に理由が無い場合インクリメントには前値形式を採用する習慣をつけることをおすすめします。
例としていろいろなコンテナのイテレータclassの後置インクリメントの実装を見てみましょう。
VC10 std::vector
_Myiter operator++(int) { // postincrement _Myiter _Tmp = *this; ++*this; return (_Tmp); }
VC10 std::list (上のvectorと全く同じ)
// VC10 std::list iterator _Myiter operator++(int) { // postincrement _Myiter _Tmp = *this; ++*this; return (_Tmp); }
GCC 4.2.1 std::list
_Self operator++(int) { Self __tmp = *this; _M_node = _M_node->_M_next; return __tmp; }
boost1.53.0 boost::container::vector
vector_iterator operator++(int) { pointer tmp = this->m_ptr; ++*this; return vector_iterator(tmp); }
Qt 4.8 QList
inline iterator operator++(int) { Node *n = i; ++i; return n; }
このようにいろいろな実装で同じように一時オブジェクトを作成しているのがわかります。
では実際にどれほどの差があるでしょうか。
以下の方法でベンチマークをとってみました。
1000000個の要素を持ったコンテナを作成し、すべてをfor文でまわしたときの経過時間を前置形式と後置形式でそれぞれ計測。その計測を100回行ったときの平均値を計算する。
その結果は
std::vectorでは 前置形式 6086[μs] 後置形式 8411[μs]
std::listでは 前置形式 6383[μs] 後置形式 9247[μs]
となりました。
どちらも1000000回実行して2〜3[ms]と、ほんのわずかではありますが実際にパフォーマンスに差があることがわかりました。
計測に使用したPCは
MacBook Air (11-inch and 13-inch, Mid 2011)
1.6 GHz Core i5
4 GB 1333MHz DDR3
コンパイラはclang 3.1
計測には以下のコードを用いました。
#include <iostream> #include <chrono> #include <vector> #include <list> int main() { std::vector<int> container; const int NUM = 1000000; for( int i = 0; i < NUM; ++i ) { container.push_back(i); } const auto end_itr = container.end(); { const auto start = std::chrono::system_clock::now(); for( auto itr = container.begin(); itr != end_itr; ++itr ) { /* do nothing */ } const auto stop = std::chrono::system_clock::now(); const auto duration = std::chrono::duration_cast<std::chrono::microseconds>( stop - start ); std::cout << "++itr : " << duration.count() << " us" << std::endl; } { const auto start = std::chrono::system_clock::now(); for( auto itr = container.begin(); itr != end_itr; itr++ ) { /* do nothing */ } const auto stop = std::chrono::system_clock::now(); const auto duration = std::chrono::duration_cast<std::chrono::microseconds>( stop - start ); std::cout << "itr++ : " << duration.count() << " us" << std::endl; } return 0; }
参考
あんちょこ:前置インクリメントと後置インクリメントの違い
ひらせチャンネル - [C++] イテレータにご注意!
std::chronoによる処理時間測定 - fjnlの生存記録のような何か