Subscribed unsubscribe Subscribe Subscribe

vectorを使ってはいけない

Effective STL 第18項より.

vectorSTLのコンテナとして悪い点は2つしかない.第1に,STLのコンテナではない.第2に,boolの値が格納されない.この2つを除けば,異議を唱える理由はない.(中略) vectorは疑似コンテナであり,実際にbool型の値を格納しているのではなく,スペースの節約を目的としたパック表現のbool型の値を格納しているためである.

ま,まじですか.STL使いには常識なんだろうけど,知らなかった.
effective STLでは,以下のような(コンテナであれば当然コンパイルが通るような)コードを例にとり,vectorがコンテナの要件を満たしていないことを説明している.

vector<bool> v;
bool *pb = &v[0];//vector<bool>::operator[]が返す値のアドレスでbool*を初期化したいが,コンパイルできない

パックした値のアドレスを取ろうとしているわけで,そりゃ確かに無理な話ではある.実装がどうなっているのかというと,型Tに対してvector::operator[]は通常const T&またはT&を返すけど,boolに対してはテンプレートの部分特殊化によって,以下のようにclass referenceへの参照を返す.

// 規格書23.2.5より
// http://www.kuzbass.ru:8086/docs/isocpp/lib-containers.html
namespace std {
    template <class Allocator> class vector<bool, Allocator> {
    public:
    //  types:
    typedef bool const_reference;
    //  bit reference:
    class reference {
        friend class vector;
        reference();
    public:
        ~reference();
        operator bool() const;
        reference& operator=(const bool x);
        reference& operator=(const reference& x);
        void flip();              //  flips the bit
    };

    reference       operator[](size_type n);
    const_reference operator[](size_type n) const;
};

なので,先のコードだとvector::reference*でbool*を初期化できないというコンパイルエラーを出す.さらに,boolをautoに変えると,事態はコンパイルエラーから実行時エラーに悪化する.

vector<bool> v;
auto *pb = &v[0];//これはコンパイルが通るが,期待する動作をしない

結果どういう動作になるのかというと,VCによる実装では_ITERATOR_DEBUG_LEVELが定義されているかどうかで挙動は変わる.こんな感じ.

const _Vbase *_Getptr() const
{	// get pointer to base word
 #if _ITERATOR_DEBUG_LEVEL == 2
    if (this->_Getcont() == 0
        || this->_Myptr == 0
        || 0 <= this->_Valid(0))
        {	// report error
            _DEBUG_ERROR("vector<bool> iterator not dereferencable");
            _SCL_SECURE_OUT_OF_RANGE;
        }

 #elif _ITERATOR_DEBUG_LEVEL == 1
    _SCL_SECURE_VALIDATE(this->_Getcont() != 0 && this->_Myptr != 0);
    _SCL_SECURE_VALIDATE_RANGE(this->_Valid(0) < 0);
 #endif /* _ITERATOR_DEBUG_LEVEL */

    return (this->_Myptr);
}

結局

こういう部分特殊化を行っているのはvectorだけ*1STLコンテナとして取り扱えない上に,計算コストが増えるというコストを払ってまでメモリ空間を節約したいというケースを除いて,boolのシーケンスコンテナが欲しいときはdequeあたりを使いましょう.C++こわい.

*1:そうなった歴史的経緯はeffective STLで触れられている