yohhoyの日記

技術的メモをしていきたい日記

swap(T, U)とis_swappable_with<T, U>とvector<bool>

C++17標準ライブラリには「型が異なる変数間での値交換(swap)」可能か否かを判定するメタ関数std::is_(nothrow_)swappable_with<T, U>が存在する。一般的には値交換操作は同一型変数間(swap(T&, T&))で行われるが、プロキシ型(proxy)のような特殊ケースにおいて異型変数間での値交換(swap(T, U))が必要となるため。*1

// <type_traits>ヘッダ
namespace std {
  template <class T, class U>
  struct is_swappable_with;

  template <class T, class U>
  struct is_nothrow_swappable_with;
}

C++17 20.5.3.2/p5 Exampleを一部転用したコード例:

#include <type_traits>
#include <utility>

namespace N {
  struct A { int m; };
  struct Proxy { A* a; };
  Proxy proxy(A& a) { return Proxy{ &a }; }
  void swap(A& x, Proxy p) {
    std::swap(x.m, p.a->m);
  }
  void swap(Proxy p, A& x) { swap(x, p); }
}

N::A a1 = { 1 }, a2 = { 2 };
auto p2 = N::proxy(a2);

// N::A& と N::Proxy 間で値交換可能
static_assert(std::is_swappable_with_v<N::A&, N::Proxy>);

swap(a1, p2);  // OK
assert(a1.m == 2 && a2.m == 1);

std::vector<bool>コンテナ

(一部で悪名高い)std::vector<bool>コンテナクラスはこのようなプロキシ型を利用する。同コンテナはbool値のビット単位管理によりメモリを効率的に利用できるが*2、その代償としてbool型要素への参照bool&を直接返せないため、要素への添字アクセスv[0]などはプロキシ型vector<bool>::referenceを返す実装となっている。

#include <vector>
#include <utility>

std::vector<bool> v{ true };
bool b = false;

static_assert(
  std::is_swappable_with_v<std::vector<bool>::reference, bool&>
);  // OK?

swap(v[0], b);  // OK?

上記コードはvector<bool>プロキシ型とbool型変数が値交換可能であることを期待するが、C++17現在の標準ライブラリ仕様では該当コードの動作を保証しないGCC/libstdc++*3、Clang/libc++*4ではコンパイル&実行可能だが、MSVC 19.16ではコンパイルエラーとなる。*5

この問題は P0022R2, 3.1 Proxy Iterator problems にて言及されている。

For all its problems, vector<bool> works surprisingly well in practice, despite the fact that fairly trivial code such as below is not portable.

std::vector<bool> v{true, false, true};
auto i = v.begin();
bool b = false;
using std::swap;
swap(*i, b);  // Not guaranteed to work.

Because of the fact that this code is underspecified, it is impossible to say with certainty which algorithms work with vector<bool>. That fact that many do is due largely to the efforts of implementors and to the fact that bool is a trivial, copyable type that hides many of the nastier problems with proxy references. For more interesting proxy reference types, the problems are impossible to hide.

関連URL

*1:本記事は nakameguro_feature.cpp vol.17 勉強会で取り上げられた疑問がきっかけ。

*2:一般的なC++処理系では、1バイト中に8個の bool 値を詰め込むことで消費メモリサイズを節約できる。

*3:https://github.com/gcc-mirror/gcc/commit/5345c53733c161a7781dd55559a4e1458751da1d

*4:https://github.com/llvm-mirror/libcxx/blob/bc8d3f97eb5c958007f2713238472e0c1c8fe02c/include/__bit_reference#L75-L93

*5:https://gcc.godbolt.org/z/Ts_vLF