C++0x の std::vector
これは「 vector の確保しているメモリ領域を、その大きさに見合ったサイズまで縮小する」関数で、
典型的な使い方は、以下のような感じになります：
// std::vector に格納される要素数の見当がつけられない // が、「上限」は分かる。このとき余計な領域の再確保を避けたい std::size_t const limit = 〜〜; // vector に格納される要素の上限 std::vector<T> vec; // まず上限までメモリ領域を確保する vec.reserve( limit ); // vec に格納していく // ... // 格納終了。しかし、 // このままだと巨大なメモリ領域を占有してしまうので、 // vec の確保している領域を「 size() に fit するよう切り詰める」。 vec.shrink_to_fit();
これ以外の使い方としては、縮小した後にメモリ領域を節約するために呼ぶ、というのもありますが、
vector を縮小する状況って意外と少ないので、大部分は reserve と組み合わせることになるでしょう。
というのは、 std::vector に関して言うなら、要素を追加する前に reserve しておくのは とても大事で、
そうしない場合、何度もメモリ領域の再確保とデータの移動が行われてしまうからです。*1
というか、 std::vector を使う場合は、明確であろうと なんとなくであろうと、
格納するデータの数の見積が立っていないと、とてつもなく非効率的になり得ます。
std::vector は、格納するデータを、連続するメモリ領域に格納するので、
非常に大きな要素数の場合は、連続領域が確保できなかったり、
仮に確保できたとしても、キャッシュヒット率などで問題が起きやすいからです。*2
サイズ上限の見積が立てられない場合は、 std::vector ではなく std::deque を使うべきで、
こいつは、連続領域の伸長や、それに伴なう要素の再配置を、一切行いません。
事実、少なくない場合では、 std::vector よりも std::deque の方が効率的だったりします。*3
なので、そのことを知ってなお std::deque ではなく std::vector を使う場合には、
必然的に「予め reserve しておき、後で必要に応じて shrink_to_fit する」という使い方が基本になります。
「vector の確保している領域を切り詰める」という説明から抱くであろう印象とは違い、
この shrink_to_fit は、 vector の力を最大限使いこなすのに必要なのです。*4
さて、この大事な大事な shrink_to_fit が、何故 C++0x になるまでメンバ関数に無かったか。
それは、 C++98/03 の範疇では、一行の簡単なコードで shrink_to_fit を行なうことが可能だったからで、
そのコードは、以下のようになります：
template<class T> void shrink_to_fit( std::vector<T>& v ) { std::vector<T>(v).swap(v); }
このコードは一見非効率的に見えるかもしれませんが、その処理内容は、
「新しい領域を確保した上で、 v の中身を全てコピーする」
というものであり、実際は push_back 等に伴なう領域の再確保と同程度のコストしかかかりません。
では何故、 C++0x ではメンバ関数として追加されたかというと、 Move Semantics に対応する為。
上のコードは v の各要素を「コピー」していますが、本来的には move で十分です。
しかし、
std::vector<T>( std::move(v) ).swap(v);
では、 vector 全体に対する move が「配列領域をすげ替える」という意味なので、ダメ。
「新しい領域を確保した上で、 v の中身を全て move する」という処理を行なうには、
template<typename T> inline void shrink_to_fit( std::vector<T>& v ) { std::vector<T> temp; temp.reserve( v.size() ); for( T& x : v ) { temp.push_back( std::move(x) ); } v.swap(temp); }
このように愚直に書けばいいわけですが、毎回書くのは面倒ですし、もっと上手い方法があるかもしれません。
というわけで、 C++0x の std::vector には shrink_to_fit が用意されたのです。
