[C++] std::vector<bool>は特殊化されている

※修正・追記1 (2022年3月16日 14:25)

@yaito3014 さんのご指摘

std::vector<bool> is a possibly space-efficient specialization of std::vector for the type bool.

は「std::vector<bool> は空間効率が良いような特殊化[1]である可能性がある」というよりは「std::vector<bool> は空間効率が良いような可能性のある特殊化である」であり、クラステンプレートstd::vectorがboolに対して(部分)特殊化されている事自体に疑いはないのでは、と思います。

特殊化されている可能性がある

という記述では 「std::vector<bool> がクラステンプレートstd::vector の特殊化ではない」ケースを含むようなものになってしまいます。

に従い記事のタイトル及び誤訳箇所を修正。

要約

1. std::vector<bool>::operator[]を使用した際に、error: cannot bind non-const lvalue reference of type 'bool&' to an rvalue of type 'bool'というコンパイルエラーが発生した。

2. std::vector<bool> - cppreference.comによると、標準ライブラリではメモリ効率向上のためにstd::vector<bool>は特殊化されている可能性がある。
   std::vector<bool> - cppreference.comによると、std::vector<bool>は空間効率が良いような可能性のある特殊化をされている。 (修正・追記1)
   そのため、

   • std::vector<bool>`は配列のように連続して格納されているとは限らない。
   • std::vector<bool>のoperator[]はbool&の代わりにその要素にアクセスするためのクラスを返す。

3. 上のコンパイルエラーはstd::vector<bool>::operator[]の返り値の型がbool&でないのが原因であった。

問題例

VectorWrapper<T>クラス

例として、次のようなstd::vector<T>のラッパークラス VectorWrapper<T> を考える。
このクラスは、operator[]をオーバーライドすることで、配列のようにindexを指定して値を得たり代入したりする機能を実装している。

#include <iostream>
#include <vector>

// std::vector<T>のラッパークラス
template <typename T>
class VectorWrapper {
    std::vector<T> v;
}

public:
    VectorWrapper(int size) : v(size) {}
    inline const T& operator[](size_t index) const { 
        return  v[index];
    }
    inline T& operator[](size_t index) {
        return v[index];
    }
};

上で定義したVectorWrapper<T>の型Tをint型として以下のようなコードをコンパイル&実行する。

int main() {
    VectorWrapper<int> vwInt(10);
    std::cout << "vwInt[2]の値: " << vwInt[2] << std::endl;
    std::cout << "vwInt[2] = 3; を実行" << std::endl;
    vwInt[2] = 3;
    std::cout << "vwInt[2]の値: " << vwInt[2] << std::endl;
}

上のコードではVectorWarrperは配列と同じように振る舞うことが期待されるが、もちろん、問題なく出力される。

vwInt[2]の値: 0
vwInt[2] = 3; を実行
vwInt[2]の値: 3

VectorWrapper<bool>でコンパイルエラー

次は，T = boolとして場合に同様のコードをコンパイルする。

int main() {
    VectorWrapper<bool> vwBool(10);
    std::cout << "vwBool[2]の値: " << vwInt[2] << std::endl;
    std::cout << "vwBool[2] = 3; を実行" << std::endl;
    vwBool[2] = 3; \\ error!
    std::cout << "vwBool[2]の値: " << vwInt[2] << std::endl;
}

上のコードをコンパイルすると以下のようなエラーが発生してしまう。

error: cannot bind non-const lvalue reference of type 'bool&' to an rvalue of type 'bool'
15 |         return v[index];

原因

std::vectorのリファレンスを参照すると、std::vector<T, Allocator>::operator[]はreference型を返すこととなっている。referenceはvalue_type&すなわちT&で定義されているので、一番上のコードではstd::vector<int>::operator[]でint&を返した。ここまでは想定通りである。

ところが、std::vector<bool>のリファレンスを参照すると、

std::vector<bool> is a possibly space-efficient specialization of std::vector for the type bool.

とあり、標準ライブラリではメモリ効率向上のためにの可能性があるstd::vector<bool>は特殊化をされている可能性があるようである。
とあり、標準ライブラリにおいて、std::vector<bool>は空間効率が良いような可能性のある特殊化をされているようである。(※修正・追記1)

さらに、

・ Does not necessarily store its elements as a contiguous array.
・ Exposes class std::vector<bool>::reference as a method of accessing individual bits. In particular, objects of this class are returned by operator[] by value.

とある。つまり、

• std::vector<bool>は配列のように連続して格納されているとは限らない。
• std::vector<bool>のoperator[]はbool&の代わりにその要素にアクセスするためのクラスを返す。

c++ - Non const lvalue references - Stack Overflowを見ると、上のコードでは，std::vector<bool>のoperator[]の返り値の型がboolにアクセスするためのクラスであるためboolに型変換した一時オブジェクトが生成されるが、C++は一時オブジェクトへの非constな参照を許していないためエラーになるようである。

まとめ

• 標準ライブラリではメモリ効率向上のためにstd::vector<bool>は特殊化されている可能性がある。
• std::vector<bool>`は空間効率が良いような可能性のある特殊化をされている。 (※修正・追記1)
• std::vector<bool>`は配列のように連続して格納されているとは限らない。
• std::vector<bool>のoperator[]はbool&の代わりにその要素にアクセスするためのクラスを返す。

参考

• std::vector - cppreference.com
• std::vector<bool> - cppreference.com
• c++ - Non const lvalue references - Stack Overflow
• テンプレートの特殊化 | Programming Place Plus　C++編【言語解説】　第２３章