std::vector<const T>は使えないのか？

`std::vector`の要素をconstオブジェクトにした時の挙動がコンパイラごと変わって混乱したのでメモ．

# tl;dr
`std::vector<const T>`はコンパイルが通り問題なく使えるか？

- 規格ではアロケータが扱える型はcv-unqualifiedであることを要求している（N4659 `§20.5.3.5`）
    - つまりアロケータを取るSTLコンテナはconst修飾されたオブジェクトを扱えないはず
- g++（libstdc++）の場合
    - gcc8だと規格通り`std::vector<const T, A>`を実体化するとstatic_assertでコンパイルエラー
    - gcc7だとstd::allocatorを`const T`に対して使うとコンパイルエラー，自前で無理やり`const T`に対しても使えるアロケータを作ればconstオブジェクトを扱えてしまう
- clang（libc++）の場合
    - clang7で`is_trivially_move_constructible_v<T> == false`だとconstオブジェクトを扱えてしまう
- VC++
    - 知らん

つまり，`std::vector<const T, A>`は一部の実装ではコンパイルができてしまうが使うべきではない．

# はじめに
`vector<const T>`のように要素をconstにすることはあまりないと思いますが，constにして試したところコンパイラ依存，バージョン依存でコンパイル結果が変わって混乱したので規格書と標準ライブラリの実装を参照して調べました．[N4659](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/n4659.pdf)（と一部[N3337](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3337.pdf)）を参照しました．本記事で出てくる`§X.Y.Z`はN4659でのセクション番号に対応します．筆者は[C++初心者](https://qiita.com/yumetodo/items/a843bd542106215bbc84)なのでC++初心者以上の方はマサカリをご準備ください．
想定するコードは以下のように`vector::reserve`と`vector::emplace_back`（or `push_back`）を使うものです．

```cpp
vector<const T> v;
v.reserve(2);
v.emplace_back(1);
v.emplace_back(42);
```

# vector requirement
規格を全部は読んでないので漏れがあるかもしれないですが，上のコードがコンパイルできるためには，Tをvectorの要素型，AをAllocatorとして，

- Tが`vector<T, A>`からErasuable（`§26.2.1 Table 83`）
- Tが`vector<T, A>`に対してMoveInsertable（厳密には`*this`に対して）（`§26.3.11.3 第2段落`，vector::reserveの要請）

である必要があります．Erasuable，MoveInsertibleそれぞれの定義は以下の通りです．ただし，`std::vector<T, A>`として`a`を`A`の左辺値，`p`をTのポインタ，`rv`をTの右辺値とします．

- Erasuable：`allocator_traits<A>::destroy(a, p)`がwell-formed（`§26.2.1 (15.6)`）
- MoveInsertible：`allocator_traits<A>::construct(a, p, rv)`がwell-formed（`§26.2.1 (15.3)`）

`std::allocator_traits<A>::destroy(a, p)`は通常`a.destroy(p)`を呼び，`std::allocator_traits<A>::construct(a, p, args...)`は通常`a.construct(p, std::forward<Args>(args)...)` を呼び出します（`§23.10.8.2`）．
つまり，文言的にはアロケータがconstオブジェクトに対応していればvectorの要素をconstにしても問題ないように見えます．

# allocator requirement
上記のようにvectorでconstオブジェクトを扱えるかどうかはアロケータ次第ということがわかりました．なので次にallocatorの仕様`§20.5.3.5`を確認します．
`§20.5.3.5`の`Table 30`を見ると`T, U, C any cv-unqualified object type`と書かれており，`§20.5.3.5 第2段落`には以下のような記述があります．

> Table 30 describes the types manipulated through allocators. Table 31 describes the requirements on allocator types and thus on types used to instantiate allocator_traits.

つまり，アロケータが扱える型は`any cv-unqualified object type`となるため，そもそも規格的にアロケータはconst volatile修飾された型を扱えないようです．
[このstackoverflowの回答](https://stackoverflow.com/questions/6954906/does-c11-allow-vectorconst-t)にあるようにアロケータが扱える型は変遷しており，C++03では型に関する規定はなく，C++11ではnon const，non referenceな型，C++14ではnon constな型，C++17ではcv修飾されていない型のような変遷をしてきているようです．C++11以降ではconstな型はどのみち扱えないです．
この時点で，const修飾された型をアロケータを取るSTLコンテナの要素にできないという結論になります．以下で各コンパイラの対応を見ます．


# gccの場合

## gcc8

```cpp
#include <vector>
int main() {
    std::vector<const int> v;
    return 0;
}
```
上のコードをコンパイルすると問答無用で`static_assert`で以下のようなコンパイルエラーになります（一部のみ抜粋）．

```
/opt/wandbox/gcc-head/include/c++/8.0.1/bits/stl_vector.h:351:21: error: static assertion failed: std::vector must have a non-const, non-volatile value_type
       static_assert(is_same<typename remove_cv<_Tp>::type, _Tp>::value,
```

つまり，規格通りgcc8ではどんなアロケータを使ってもcv修飾された型を要素にすることはできません．また，[このようにcv修飾した型に対する標準アロケータ`std::allocator<T>`はinvalidとなっています](https://github.com/gcc-mirror/gcc/blob/5f22034c713255429d77be72f96fbd54a689a8fc/libstdc%2B%2B-v3/include/bits/allocator.h#L168-L192)．

## gcc7

次にgcc7での挙動を見ます．

### 標準アロケータを使った場合

gcc8の検証の時と同様，以下のコードをコンパイルしてみます．

```cpp
#include <vector>
int main() {
    std::vector<const int> v;
    return 0;
}
```

すると，今度は`static_assert`は出ず，別のエラーがでます（今回も一部のみ抜粋）．

```
/opt/wandbox/gcc-7.1.0/include/c++/7.1.0/ext/new_allocator.h:93:7: error: 'const _Tp* __gnu_cxx::new_allocator<_Tp>::address(__gnu_cxx::new_allocator<_Tp>::const_reference) const [with _Tp = const int; __gnu_cxx::new_allocator<_Tp>::const_pointer = const int*; __gnu_cxx::new_allocator<_Tp>::const_reference = const int&]' cannot be overloaded
       address(const_reference __x) const _GLIBCXX_NOEXCEPT
       ^~~~~~~
/opt/wandbox/gcc-7.1.0/include/c++/7.1.0/ext/new_allocator.h:89:7: error: with '_Tp* __gnu_cxx::new_allocator<_Tp>::address(__gnu_cxx::new_allocator<_Tp>::reference) const [with _Tp = const int; __gnu_cxx::new_allocator<_Tp>::pointer = const int*; __gnu_cxx::new_allocator<_Tp>::reference = const int&]'
       address(reference __x) const _GLIBCXX_NOEXCEPT

・・・中略・・・
/opt/wandbox/gcc-7.1.0/include/c++/7.1.0/ext/new_allocator.h:121:23: error: invalid conversion from 'const void*' to 'void*' [-fpermissive]
      ::operator delete(__p, std::align_val_t(alignof(_Tp)));
      ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
```

少しメッセージが長いですが，標準アロケータの`address`メンバ関数のオーバーロードとoperator deleteの引数で`const void*`から`void*`への変換でコンパイルエラーが出ているようです．
`std::allocator<T>::address`は[C++17で非推奨になった](https://cpprefjp.github.io/reference/memory/allocator/address.html)メンバ関数です．N3337の方を参照すると，標準アロケータは

```cpp
template <class T> class allocator {
・・・中略・・・
    typedef T*        pointer;
    typedef const T*  const_pointer;
    typedef T&        reference;
    typedef const T&  const_reference;
・・・中略・・・
    pointer address(reference x) const noexcept;
    const_pointer address(const_reference x) const noexcept;
・・・中略・・・
};
```

のようになっています．つまり，`T = const U`とした場合，`address`メンバ関数の宣言は同一になり，コンパイルエラーになります．この挙動がcv修飾を許さないという規格を意図して作りこまれたものかわかりませんが，これがgcc7で`std::vector`の要素をconstオブジェクトにできない原因の一つです．`operator delete`でのconstポインタから非constポインタへの変換エラーも意図されたものかわかりませんが同様です．

### カスタムアロケータを使った場合

上記のようにgccでは規格通り標準アロケータがconstな型に対応していないです．
代わりに以下のように規格からは外れてconst対応した自前のアロケータを使った場合はvectorの要素をconstにすることができます（カスタムアロケータは適当に実装しただけです）．ただし，こんなことはするべきではないでしょう．

```cpp
#include <memory>
#include <vector>
#include <type_traits>
#include <iostream>

template <class T>
struct MyAllocator {
    using value_type = T;
    MyAllocator() = default;
    MyAllocator(const MyAllocator&) = default;
    MyAllocator(MyAllocator&&) = default;
    ~MyAllocator() = default;
    MyAllocator& operator=(const MyAllocator&) = default;
    MyAllocator& operator=(MyAllocator&&) = default;
    template <class U>
    MyAllocator(const MyAllocator<U>&) {}

    T* allocate(std::size_t n){ return reinterpret_cast<T*>(std::malloc(sizeof(T) * n)); }
    void deallocate(T* p, std::size_t){ std::free(const_cast<std::add_pointer_t<std::remove_cv_t<T>>>(p)); }
};
template <class T, class U>
bool operator==(const MyAllocator<T>&, const MyAllocator<U>&){ return true; }
template <class T, class U>
bool operator!=(const MyAllocator<T>&, const MyAllocator<U>&){ return false; }

int main () {
    std::vector<const int, MyAllocator<const int>> v;
    v.reserve(1);
    v.emplace_back(42);
    std::cout << v[0] << std::endl;
    return 0;
}
```

# clangの場合

clang7の場合，以下のように`const std::string`を要素とするvectorを使ったコードが問題なくコンパイルでき，動作してしまいます．

```cpp
#include <vector>
#include <string>
#include <iostream>
int main() {
    std::vector<const std::string> v;
    v.reserve(1);
    v.emplace_back("a");
    std::cout << v[0] << std::endl;
    return 0;
}
```

一方，以下のコードをコンパイルするとコンパイルエラーになります．

```cpp
#include <vector>
int main() {
    std::vector<const int> v;
    v.reserve(1);
    return 0;
}
```

出現したコンパイルエラーは以下の通りです（一部抜粋）．

```
/opt/wandbox/clang-head/include/c++/v1/memory:1698:31: error: cannot initialize a parameter of type 'void *' with an lvalue of type 'const int *'
                _VSTD::memcpy(__end2, __begin1, _Np * sizeof(_Tp));
                              ^~~~~~
/opt/wandbox/clang-head/include/c++/v1/vector:898:21: note: in instantiation of function template specialization 'std::__1::allocator_traits<std::__1::allocator<const int> >::__construct_backward<const int>' requested here
    __alloc_traits::__construct_backward(this->__alloc(), this->__begin_, this->__end_, __v.__begin_);
                    ^
/opt/wandbox/clang-head/include/c++/v1/vector:1542:9: note: in instantiation of member function 'std::__1::vector<const int, std::__1::allocator<const int> >::__swap_out_circular_buffer' requested here
        __swap_out_circular_buffer(__v);
        ^
prog.cc:4:7: note: in instantiation of member function 'std::__1::vector<const int, std::__1::allocator<const int> >::reserve' requested here
    v.reserve(1)
```

gccの時と違い`memcpy`で`const void*`から`void*`へ変換できないというコンパイルエラーが出ています．ご存知のとおり`reserve`や`push_back`，`emplace_back`で配列サイズを変えた時に現在のcapacityが足りないと領域を再確保して再確保先に要素をムーブかコピーする必要があります．intの場合はこのコピー操作がmemcpyで最適化されているようです．memcpyによる最適化は[このように実装](https://github.com/llvm-mirror/libcxx/blob/f466f69333e472d871a2a4e9055c9c90b16207ad/include/memory#L1670-L1699)され，`is_trivially_move_constructible_v<T>`がtrueであればmemcpyによる最適化（バイトレベルでのメモリコピー）が行われます．`std::vector<const T>`は内部的には`cosnt T`のポインタを保持することになるため，memcpyの方が適用されると上のようにconstポインタを非constポインタに暗黙にキャストできないことによるコンパイルエラーが出現します．そのため，`is_trivially_move_constructible_v<const T>`がfalseになるような型（例えば`std::string`など）であればconstにして`std::vector`の要素にできてしまいます．
ちなみに，上で書いたようにgccの場合は`std::allocator<const T>`はちゃんとinvalidでしたが，clangの場合は[このように`const T`に対して部分特殊化](https://github.com/llvm-mirror/libcxx/blob/f466f69333e472d871a2a4e9055c9c90b16207ad/include/memory#L1869-L1968)されおり，gccの時に起きた`address`メンバ関数の重複が回避されています． つまり標準アロケータがconstオブジェクトを扱えるように独自拡張されています．そのため，clangでは一部の型でconst修飾したものがstd::vectorの要素にできてしまいます．

# まとめ

- 規格ではアロケータのテンプレート引数はcv-unqualifiedな型であることを要求している
    - つまりアロケータを取るSTLコンテナはconst修飾されたオブジェクトを扱えないはず
- g++（libstdc++）の場合
    - gcc8: 規格通り`vector<const T, A>`を実体化するとstatic_assertでコンパイルエラー
    - gcc7: 規格に忠実に`std::allocator`を実装しているので`std::allocator`がconstオブジェクトを扱えない．ただ自前で`const T`に対しても使えるアロケータを作れば使えてしまう
- clang（libc++）の場合
    - clang7で`is_trivially_move_constructible_v<T> == false`だとconstオブジェクトを扱えてしまう

`std::vector<const T, A>`はコンパイルできたとしても使わないようにしましょう．