C++ STLのパフォーマンスの向上 5選
-
2021年10月21日
はじめまして、『ポケコロ』クライアント開発のYです。
今回はC++を使う上で必要不可欠となっているSTL（Standard Template Library）の簡単かつ強力な5つのパフォーマンスの向上方法を紹介しようと思います。
STLのvectorやmapを１回でも使ったことがある方なら簡単に理解できる内容で構成したので、みなさんのコーディングライフに役に立ったら嬉しいです。
1.コンテナのサイズが０かどうかを調べるとき！
任意のコンテナcontainerAのsize()を調べる方法はみなさんがご存知の通り２つあります.
①.size()を使う
if(containerA.size() == 0)
{
・・・・・・
}
②.empty()を使う
if(containerA.empty())
{
・・・・・・
}
上記の２つの例は本質的には変わらないのですが、結論から言うとempty()を使った方が好ましいです。
理由は単純です。empty()は全てのコンテナに対して定数時間処理ですが、size()の場合,一部のlistの実装には線形時間がかかります。
どのような場合でもsize()==0を調べる代わりにempty()を呼び出せば間違いありません。
2.単一要素メンバ関数より範囲メンバ関数を使おう
vector<int> vecA; vector<int> vecB;
vecAの中に10個の要素が入っているとします。
そして、半分から後ろの要素をvecBに入れたいです。
非常に多くの方法がありますが、代表的な方法３つを見てみましょう。
①.assign()を使う
vecB.assign(vecA.begin() + vecA.size()/2, vecA.end());
②copy()を使う
copy(vecA.begin() + vecA.size()/2, vecA.end(), back_inserter(vecB));
③for文を使ってpushする
for( vector<int>::const_iterator iter = vecA.begin() + vecA.size()/2; iter != vecA.end(); ++iter)
{
vecB.push_back(*iter);
}
上記の３つの例は本質的に変わらないのですが、効率を考えると１番を使うべきです。
その理由は大きく２つあります。
1つ目は範囲メンバ関数を使った方が作業量が少なく、意図が分かりやすいためです。
2つ目は範囲メンバ関数を使った方がパフォーマンスが向上するためです。
（1番の場合については明確な事実なので詳しい説明は省略します。２番の場合は色々な理由がありますが、今回は適切な理由を1つを挙げます）
まず③はループを使ってpushしています。確かにループが終了した時「vecB.size()」は5になりますが、「vecB.capacity()」は8になります。
つまり、不必要なメモリブロックが３つ(「capacity() – size()」)も割り当てられています。
ここで、こう思う方がいるはずです。
”②は①とコード量もほぼ一緒で分かりやすくてループも使ってないだろう?”
しかし、copyの中にはループがあります。つまり、capacity()は同じく8になります。
3.不必要な割り当てを避けるために！
vectorの場合、reallocと等しい処理が行われて、最大サイズを超えない限りデータをいくら入れても自動的にサイズが大きくなリます。
そしてほとんどの実装で容量の倍数サイズでメモリブロックを割り当てます。
例えば
vector<int> vecA; for(int i =0; i < 10; ++i) vecA.push_back(i);
この場合、vecA.size()は10になるが、vecA.capacity()は16になリます。
続いて120個の要素をpushすると
for(int i =0; i < 120; ++i) vecA.push_back(i);
vecA.size()は130になるが、vecA.capacity()は256になります。
(※256個の要素をpushするとcapacityは256になります。したがって、capacityは2のn乗に割り当てられることが分かります。)
つまり、不必要な136個のメモリブロックを占有することになります。
この問題を解決する方法はreverseです。
vector<int> vecA;
vecA.reverse(130);
for(int i =0; i < 130; ++i)
{
vecA.push_back(i);
}
こうすることで、size()とcapacity()のサイズを等しくすることができます。
(※resizeの場合、resizeの数より実際のサイズが大きかったらコンテナの末から要素を破棄するので注意する必要があります。)
4.eraseしても残るcapacity
早速コードを見てみましょう.
vector<int> vecA;
for(int i =0; i < 10; ++i)
{
vecA.push_back(i);
vecA.clear();
}
突然ですが、問題です！
vecAのsize()及びcapacity()のサイズは何でしょうか?
答えはsize()は0、capacity()は10です。
つまり、capacityのサイズが減っていないということです。
この場合はswapを用いることでcapacityを解消することができます。
vector<int> vecA;
for(int i =0; i < 10; ++i)
{
vecA.push_back(i);
vecA.clear();
vector<int>(vecA).swap(vecA);
}
こうすることで、余分な容量を削除することができます。
vector<int>(vecA)は、vecAのコピーである一時vetorを作成します。コピーが行われるときコピーコンストラクタが働き、「コピー対象に必要なメモリだけ」を割り当てるため、この一時vectorは無駄なメモリのない容量となるのがこのswap方式の原理です。
(※C++11からは上記の問題を解決するため「shirink_to_fit()」という関数を提供している)
5.map::operator[]とmap::insertどちらを使った方が良いか?
デフォルト生成及びint型から生成と代入をサポートするCIntクラスがあるとします。
class CInt
{
public:
CInt();
CInt(int inNo){}
CInt& operator=(int inNo);
・・・・・・
}
int型の値からCIntへのmapを作成し、新しい要素を入れてみましょう。
大きく２つの方法があります。
①直接挿入する
mapA<int, CInt> mapA; mapA[0] = 10;
②.insert()を使って追加する
mapA<int, CInt> mapA; mapA.insert(pair<int, CInt>(0,CInt(10)));
上記の２つの例は本質的に変わりませんが、①の方がコードも短くて良さそうに見えるのではないでしょうか?
①の場合
typedef map<int, CInt> mapB; pair<mapB::iterator, bool> result = mapA.insert(mapB::value_type(1, CInt())); result.first->second = 10;
上記のステートメントと機能的に等価です。
見た目としては前者の方魅力的ですが言うまでもなく、後者の方が圧倒的に効率的だと言うことがわかります。
最後に
C++STL使用するとき簡単にパフォーマンスを向上させる５つの方法を紹介しました。
本記事がみなさんのコーディングに役立つことを祈っています。
そしてこれからも『ポケコロ』を愛してくださいm(･ω･m)
また、ココネでは一緒に働く仲間を募集中です。
ご興味のある方は、以下のリンクからぜひご応募ください。
