shrink-to-fit の幻想

C++

C++03 には shrink-to-fit というイディオムがあります。

std::vector<int> v;
//... たくさんの push_back と、たくさんの v に対する削除
//その結果、v のサイズは小さいが、容量は大きい。
std::vector<int>(v).swap (v);

C++11 では、この動作を行う shrink_to_fit というメンバ関数が basic_string, deque, vector に追加されました。


ただ、その辺を詳しく調べてみると、ちょっと以外な仕様があったので記事にしてみました。

何もしない shrink-to-fit

shrink_to_fit メンバ関数には「〜という動作を行わなければならない」といった規定はありません。

代わりに以下のような Remark があるだけです。

shrink_to_fit は、capacity() を size() に縮小させるという、強制力の無いリクエストである。[Note: 縮小を強制しないのは、実装依存の最適化を許容するためである]

shrink_to_fitメンバ関数_§23.3.6.3¶6

つまり、何もしない shrink-to-fit であっても、仕様として正しい実装になります。


なぜこのようなことを許しているのかというと、Note にあるように、実装依存の最適化を許すためです。
極端な例で言うと、メモリを 4KB 単位でアロケートするような環境である場合、4KB以下のサイズに縮めるように要求されても無駄になってしまいます。そのため、何もしないという実装を許可しているのです。*1

手動 shrink-to-fit

ではもし、必ず再アロケートさせたいとしたらどうすればいいでしょうか。
単純には、最初に紹介した

std::vector<int>(v).swap (v);

という方法で良さそうですが、C++11 ではムーブセマンティクスが導入されたので、これだとコピーのコストが無駄になってしまうことがあります。


なので move_iterator を使って

std::vector<int>(
    std::make_move_iterator(v.begin()),
    std::make_move_iterator(v.end())).swap(v);

と書けばいいと思うかもしれませんが、これだと各要素をムーブしている途中に例外が投げられたとき、以前の状態に戻せません。


ということで、例外が発生しそうならコピーを、そうでないならムーブを使います。

template<class Iterator, class R = typename std::conditional<
    !std::is_nothrow_move_constructible<
        typename std::iterator_traits<Iterator>::value_type>::value &&
    std::is_copy_constructible<
        typename std::iterator_traits<Iterator>::value_type>::value,
    Iterator, std::move_iterator<Iterator>>::type>
R make_move_if_noexcept_iterator(Iterator it) {
    return R(it);
}

std::vector<int>(
    make_move_if_noexcept_iterator(v.begin()),
    make_move_if_noexcept_iterator(v.end())).swap(v);

簡単ですね（白目 *2


まあただ、大抵は shrink_to_fit だけ使っておけば事足ります。
この話は、「もし C++11 が shrink_to_fit メンバ関数を用意していなかったらどうなっていたか」という感じで理解すればいいと思います。

basic_string の shrink-to-fit

実は、C++03 でも C++11 でも、basic_string::reserve は shrink-to-fit の効果を持っています。

reserve() を呼び出した後、capacity() は引数の値以上になる。[Note: capacity() より小さい値 x で reserve(x) と呼び出した場合、これは強制力の無い shrink リクエストである。同様に x が size() 以下の値である場合、これは強制力の無い shrink-to-fit リクエストである]

basic_string::reserveメンバ関数_§21.4.4¶12

もちろん vector や deque は持っていません。basic_string のみの仕様です。なぜこうなっているのかは分かりませんでした。


.

*1:via: c++ - Why is shrink_to_fit non-binding? - Stack Overflow の回答

*2:この実装は http://gcc.gnu.org/viewcvs/trunk/libstdc%2B%2B-v3/include/bits/stl_iterator.h?view=markup の __make_move_if_noexcept_iterator 関数を参考に作りました