C++中的Bitsets与Valarrays详解

### C++ 中的 Bitsets 与 Valarrays 详解 #### 1. Bitsets 概述 Bitsets 是固定大小的位或布尔值数组，在管理标志集合时非常有用，变量可以表示任意标志组合。与 C 和旧 C++ 程序中使用 `long` 类型数组并通过位运算符（如 `&`、`|` 和 `~`）进行操作不同，`bitset` 类具有诸多优势，它可以包含任意数量的位，并提供了额外的操作，例如可以单独赋值位，还能以 0 和 1 的序列读写 `bitset`。 需要注意的是，`bitset` 中的位数是模板参数，无法更改。如果需要可变数量的位或布尔值容器，可以使用 `vector<bool>`。 `bitset` 类在 `<bitset>` 头文件中定义： ```cpp #include <bitset> namespace std { template <size_t Bits> class bitset; } ``` 这里的模板参数是无符号整数值，不同模板参数的 `bitset` 是不同类型，只有位数相同的 `bitset` 才能进行比较和组合。 #### 2. C++11 对 Bitsets 的改进 C++98 已经规定了 `bitset` 的大部分特性，C++11 在此基础上增加了以下重要特性： - 可以使用字符串字面量初始化 `bitset`。 - 支持与 `unsigned long long` 类型的数值进行转换，引入了 `to_ullong()` 方法。 - 在与字符串进行转换时，可以指定表示置位和未置位的字符。 - 提供了 `all()` 成员函数，用于检查所有位是否都被置位。 - 为在无序容器中使用 `bitset` 提供了默认哈希函数。 #### 3. Bitsets 的使用示例 ##### 3.1 将 Bitsets 用作标志集合 以下示例展示了如何使用 `bitset` 管理一组标志，每个标志的值由枚举类型定义，枚举类型的值作为 `bitset` 中位的位置。这里的位表示颜色，每个枚举值定义一种颜色，通过 `bitset` 可以管理可能包含任意颜色组合的变量。 ```cpp // contadapt/bitset1.cpp #include <bitset> #include <iostream> using namespace std; int main() { // 枚举类型，每个位代表一种颜色 enum Color { red, yellow, green, blue, white, black, ..., numColors }; // 为所有位/颜色创建 bitset bitset<numColors> usedColors; // 设置两种颜色的位 usedColors.set(red); usedColors.set(blue); // 打印一些 bitset 数据 cout << "bitfield of used colors: " << usedColors << endl; cout << "number of used colors: " << usedColors.count() << endl; cout << "bitfield of unused colors: " << ~usedColors << endl; // 如果有任何颜色被使用 if (usedColors.any()) { // 遍历所有颜色 for (int c = 0; c < numColors; ++c) { // 如果当前颜色被使用 if (usedColors[(Color)c]) { ... } } } } ``` ##### 3.2 使用 Bitsets 进行二进制表示的输入输出 `bitset` 的一个实用特性是能够将整数值转换为位序列，反之亦然，只需创建一个临时 `bitset` 即可实现。 ```cpp // contadapt/bitset2.cpp #include <bitset> #include <iostream> #include <string> #include <limits> using namespace std; int main() { // 以二进制表示打印一些数字 cout << "267 as binary short: " << bitset<numeric_limits<unsigned short>::digits>(267) << endl; cout << "267 as binary long: " << bitset<numeric_limits<unsigned long>::digits>(267) << endl; cout << "10,000,000 with 24 bits: " << bitset<24>(1e7) << endl; // 将二进制表示写入字符串 string s = bitset<42>(12345678).to_string(); cout << "12,345,678 with 42 bits: " << s << endl; // 将二进制表示转换为整数 cout << "\"1000101011\" as number: " << bitset<100>("1000101011").to_ullong() << endl; } ``` 该程序可能的输出如下： ```plaintext 267 as binary short: 0000000100001011 267 as binary long: 00000000000000000000000100001011 10,000,000 with 24 bits: 100110001001011010000000 12,345,678 with 42 bits: 000000000000000000101111000110000101001110 "1000101011" as number: 555 ``` #### 4. Bitset 类的详细操作 ##### 4.1 创建、复制和销毁操作 `bitset` 定义了一些特殊的构造函数，但没有定义特殊的复制构造函数、赋值运算符或析构函数，因此 `bitset` 的赋值和复制采用默认的按位复制操作。 - `bitset<bits>::bitset ()`：默认构造函数，创建一个所有位初始化为零的 `bitset`。 ```cpp bitset<50> flags; // flags: 0000...000000，即 50 个未置位的位 ``` - `bitset<bits>::bitset (unsigned long long value)`：根据整数值 `value` 的位初始化 `bitset`，如果 `value` 的位数太少，前导位位置初始化为零。在 C++11 之前，`value` 的类型是 `unsigned long`。 ```cpp bitset<50> flags(7); // flags: 0000...000111 ``` - `explicit bitset<bits>::bitset (const string& str)` 及相关重载形式：通过字符串 `str` 或其子字符串初始化 `bitset`，字符串或子字符串只能包含字符 `'0'` 和 `'1'` 或指定的零和一字符。 ```cpp bitset<50> flags(string("1010101")); // flags: 0000...0001010101 bitset<50> flags(string("1111000"),2,3); // flags: 0000...0000000110 ``` - `explicit bitset<bits>::bitset (const charT* str)` 及相关重载形式：通过字符序列 `str` 初始化 `bitset`，同样要求字符串或子字符串只能包含特定字符。 ```cpp bitset<50> flags("1010101"); // flags: 0000...0001010101 ``` ##### 4.2 非操作操作 - `size_t bitset<bits>::size () const`：返回位数。 - `size_t bitset<bits>::count () const`：返回置位的位数（值为 1 的位）。 - `bool bitset<bits>::all () const`：检查所有位是否都被置位，C++11 新增。 - `bool bitset<bits>::any () const`：检查是否有任何位被置位。 - `bool bitset<bits>::none () const`：检查是否没有位被置位。 - `bool bitset<bits>::test (size_t idx) const`：检查位置 `idx` 的位是否被置位，若 `idx >= size()` 则抛出 `out_of_range` 异常。 - `bool bitset<bits>::operator == (const bitset<bits>& bits) const`：检查 `*this` 和 `bits` 的所有位是否具有相同的值。 - `bool bitset<bits>::operator != (const bitset<bits>& bits) const`：检查 `*this` 和 `bits` 是否有任何位具有不同的值。 ##### 4.3 操作操作 - `bitset<bits>& bitset<bits>::set ()`：将所有位设置为 `true`，返回修改后的 `bitset`。 - `bitset<bits>& bitset<bits>::set (size_t idx)`：将位置 `idx` 的位设置为 `true`，若 `idx >= size()` 则抛出 `out_of_range` 异常。 - `bitset<bits>& bitset<bits>::set (size_t idx, bool value)`：根据 `value` 设置位置 `idx` 的位，C++11 之前 `value` 类型为 `int`。 - `bitset<bits>& bitset<bits>::reset ()`：将所有位重置为 `false`（赋值为 0），返回修改后的 `bitset`。 - `bitset<bits>& bitset<bits>::reset (size_t idx)`：将位置 `idx` 的位重置为 `false`，若 `idx >= size()` 则抛出 `out_of_range` 异常。 - `bitset<bits>& bitset<bits>::flip ()`：翻转所有位（将未置位的位设置为置位，反之亦然），返回修改后的 `bitset`。 - `bitset<bits>& bitset<bits>::flip (size_t idx)`：翻转位置 `idx` 的位，若 `idx >= size()` 则抛出 `out_of_range` 异常。 - `bitset<bits>& bitset<bits>::operator ^= (const bitset<bits>& bits)`：按位异或运算符，翻转 `bits` 中置位的所有位的值，其他位保持不变。 - `bitset<bits>& bitset<bits>::operator |= (const bitset<bits>& bits)`：按位或运算符，设置 `bits` 中置位的所有位，其他位保持不变。 - `bitset<bits>& bitset<bits>::operator &= (const bitset<bits>& bits)`：按位与运算符，重置 `bits` 中未置位的所有位，其他位保持不变。 - `bitset<bits>& bitset<bits>::operator <<= (size_t num)`：将所有位向左移动 `num` 个位置，最低的 `num` 位设置为 `false`。 - `bitset<bits>& bitset<bits>::operator >>= (size_t num)`：将所有位向右移动 `num` 个位置，最高的 `num` 位设置为 `false`。 ##### 4.4 使用运算符 `[]` 访问 - `bitset<bits>::reference bitset<bits>::operator [ ] (size_t idx)`：对于非常量 `bitset`，使用代理类型使返回值可作为可修改的值（左值）。 - `bool bitset<bits>::operator [ ] (size_t idx) const`：对于常量 `bitset`，返回位置 `idx` 的位。 当对非常量 `bitset` 调用 `operator []` 时，返回一个 `bitset<>::reference` 类型的特殊临时对象，该对象作为代理允许对通过 `operator []` 访问的位进行某些修改，具体操作如下： 1. `reference& operator= (bool)`：根据传入的值设置位。 2. `reference& operator= (const reference&)`：根据另一个引用设置位。 3. `reference& flip ()`：翻转位的值。 4. `operator bool () const`：自动将值转换为布尔值。 5. `bool operator~ () const`：返回位的补码（翻转后的值）。 示例代码如下： ```cpp bitset<50> flags; ... flags[42] = true; // 设置位 42 flags[13] = flags[42]; // 将位 42 的值赋给位 13 flags[42].flip(); // 翻转位 42 的值 if (flags[13]) { // 如果位 13 被置位 flags[10] = ~flags[42]; // 则将位 42 的补码赋给位 10 } ``` ##### 4.5 创建新的修改后的 Bitsets - `bitset<bits> bitset<bits>::operator ~ () const`：返回一个所有位相对于 `*this` 翻转的新 `bitset`。 - `bitset<bits> bitset<bits>::operator << (size_t num) const`：返回一个所有位向左移动 `num` 个位置的新 `bitset`。 - `bitset<bits> bitset<bits>::operator >> (size_t num) const`：返回一个所有位向右移动 `num` 个位置的新 `bitset`。 - `bitset<bits> operator & (const bitset<bits>& bits1, const bitset<bits>& bits2)`：返回 `bits1` 和 `bits2` 的按位与运算结果。 - `bitset<bits> operator | (const bitset<bits>& bits1, const bitset<bits>& bits2)`：返回 `bits1` 和 `bits2` 的按位或运算结果。 - `bitset<bits> operator ^ (const bitset<bits>& bits1, const bitset<bits>& bits2)`：返回 `bits1` 和 `bits2` 的按位异或运算结果。 ##### 4.6 类型转换操作 - `unsigned long bitset<bits>::to_ulong () const`：返回 `bitset` 的位所表示的整数值，若该整数值无法用 `unsigned long` 表示，则抛出 `overflow_error` 异常。 - `unsigned long long bitset<bits>::to_ullong () const`：返回 `bitset` 的位所表示的整数值，若该整数值无法用 `unsigned long long` 表示，则抛出 `overflow_error` 异常，C++11 新增。 - `string bitset<bits>::to_string () const` 及相关重载形式：返回一个包含 `bitset` 值的二进制表示的字符串，未置位的位用 `'0'` 表示，置位的位用 `'1'` 表示。 ##### 4.7 输入/输出操作 - `istream& operator >> (istream& strm, bitset<bits>& bits)`：从输入流 `strm` 中读取一个 `bitset` 作为字符序列 `'0'` 和 `'1'`，读取直到满足以下条件之一：最多读取 `bits` 个字符、输入流到达文件末尾、下一个字符既不是 `'0'` 也不是 `'1'`。 - `ostream& operator << (ostream& strm, const bitset<bits>& bits)`：将 `bits` 转换为包含二进制表示的字符串并写入输出流 `strm`。 ##### 4.8 哈希支持 自 C++11 起，`bitset<>` 类为哈希函数提供了特化： ```cpp namespace std { template <size_t N> struct hash<bitset<N> >; } ``` #### 5. Valarrays 概述 自 C++98 起，C++ 标准库提供了 `valarray<>` 类用于处理数值数组。`valarray` 是数学概念中线性值序列的表示，它是一维的，但通过特殊的计算索引技术和强大的子集功能可以实现更高维度的错觉，因此可作为向量和矩阵运算以及处理多项式方程组的基础，具有较好的性能。 不过，`valarray` 类的设计并不完善，在使用时常常需要进行一些不便且耗时的类型转换。未来，由于其他更优秀的开发成果，`valarray` 在 C++ 标准库中的重要性尚不确定，例如 Blitz 系统就是一个性能更优的选择。 #### 6. C++11 对 Valarrays 的改进 C++98 规定了 `valarray` 类的大部分特性，C++11 新增了以下重要特性： - 支持移动语义，提供了移动构造函数和移动赋值运算符。 - 提供了 `swap()` 函数。 - 可以使用初始化列表初始化 `valarray` 或为其分配新值。 - 提供了 `begin()` 和 `end()` 用于迭代 `valarray` 的元素。 - 运算符 `[]` 现在返回常量引用而不是副本。 #### 7. 了解 Valarrays ##### 7.1 基本概念 `valarray` 是一维数组，元素从 0 开始顺序编号，它能够对一个或多个值数组中的所有或部分值进行数值处理。例如，可以处理 `z = a*x*x + b*x + c` 这样的语句，其中 `a`、`b`、`c`、`x` 和 `z` 是包含数百个数值的数组，使用 `valarray` 不仅表示简单，而且处理性能良好，因为类提供了一些优化，避免了在处理整个语句时创建临时对象。此外，特殊的接口和辅助类还提供了处理特定子集或进行多维处理的能力，有助于实现向量和矩阵运算及相关类。 标准保证 `valarray` 是无别名的，即非常量 `valarray` 的任何值都通过唯一路径访问，因此对这些值的操作可以更好地进行优化。 ##### 7.2 头文件 `valarray` 在 `<valarray>` 头文件中声明，具体类如下： ```cpp #include <valarray> namespace std { template<typename T> class valarray; // 类型为 T 的数值数组 class slice; // 从 valarray 中切片 template<typename T> class slice_array; class gslice; // 广义切片 template<typename T> class gslice_array; template<typename T> class mask_array; // 掩码 valarray template<typename T> class indirect_array; // 间接 valarray } ``` 这些类的含义如下： - `valarray` 是管理数值数组的核心类。 - `slice` 和 `gslice` 用于定义类似于 BLAS 的切片作为 `valarray` 的子集。 - `slice_array`、`gslice_array`、`mask_array` 和 `indirect_array` 是内部辅助类，用于存储临时值或数据，不能直接在编程接口中使用，而是通过某些 `valarray` 操作间接创建。 所有类都针对元素类型进行了模板化，原则上元素类型可以是任何数据类型，但根据 `valarray` 的性质，应该是数值数据类型。 ##### 7.3 创建 Valarrays 创建 `valarray` 时，通常将元素数量作为参数传递： ```cpp std::valarray<int> va1(10); // 包含十个值为 0 的 int 类型的 valarray std::valarray<float> va2(5.7,10); // 包含十个值为 5.7 的 float 类型的 valarray ``` 如果只传递一个参数，则该参数用作大小，元素通过其类型的默认构造函数初始化，基本数据类型的元素初始化为 0。如果传递第二个值，则第一个值用作元素的初始值，第二个值指定元素的数量，注意传递两个参数的顺序与 C++ 标准库的其他类不同。 自 C++11 起，也可以使用初始化列表初始化 `valarray`： ```cpp std::valarray<int> va3 = { 3, 6, 18, 3, 22 }; ``` 在 C++11 之前，需要使用普通的 C 风格数组： ```cpp int array[] = { 3, 6, 18, 3, 22 }; std::valarray<int> va3(array,sizeof(array)/sizeof(array[0])); std::valarray<int> va4(array+1,3); ``` `valarray` 会创建传递值的副本，因此可以传递临时数据进行初始化。 ##### 7.4 Valarray 操作 - **下标运算符**：用于访问 `valarray` 的元素，第一个元素的索引为 0。 ```cpp va[0] = 3 * va[1] + va[2]; ``` - **普通数值运算符**：包括加法、减法、乘法、取模、取反、位运算符、比较运算符和逻辑运算符，以及所有赋值运算符。这些运算符对 `valarray` 中每个被处理的元素进行调用，操作结果是一个与操作数具有相同元素数量的 `valarray`，包含元素级计算的结果。 ```cpp va1 = va2 * va3; // 等价于 va1[0] = va2[0] * va3[0]; va1[1] = va2[1] * va3[1]; ... ``` 如果组合的 `valarray` 元素数量不同，结果是未定义的。当然，这些操作仅在元素类型支持时可用，操作的具体含义取决于元素操作的含义。 对于二元操作，其中一个操作数可以是元素类型的单个值，此时该单个值与作为另一个操作数的 `valarray` 的每个元素进行组合。 ```cpp va1 = 4 * va2; // 等价于 va1[0] = 4 * va2[0]; va1[1] = 4 * va2[1]; ... ``` 需要注意的是，单个值的类型必须与 `valarray` 的元素类型完全匹配。 比较运算符的返回值是一个与操作数具有相同元素数量的 `bool` 类型的新 `valarray`，每个值是单个比较的结果。因此，不能使用运算符 `<` 对 `valarray` 进行排序，也不能在使用运算符 `==` 进行相等性测试的 STL 容器中使用它们。 以下是一个简单使用 `valarray` 的示例程序： ```cpp // num/valarray1.cpp #include <iostream> #include <valarray> using namespace std; // 打印 valarray template <typename T> void printValarray (const valarray<T>& va) { for (int i=0; i<va.size(); i++) { cout << va[i] << ' '; } cout << endl; } int main() { // 定义两个包含十个元素的 valarray valarray<double> va1(10), va2(10); // 为第一个 valarray 分配值 0.0, 1.1, ..., 9.9 for (int i=0; i<10; i++) { va1[i] = i * 1.1; } // 为第二个 valarray 的所有元素分配 -1 va2 = -1; // 打印两个 valarray printValarray(va1); printValarray(va2); // 打印第一个 valarray 的最小值、最大值和总和 cout << "min(): " << va1.min() << endl; cout << "max(): " << va1.max() << endl; cout << "sum(): " << va1.sum() << endl; // 将第一个 valarray 的值赋给第二个 valarray va2 = va1; // 移除第一个 valarray 的所有元素 va1.resize(0); // 再次打印两个 valarray printValarray(va1); printValarray(va2); } ``` 该程序的输出如下： ```plaintext 0 1.1 2.2 3.3 4.4 5.5 6.6 7.7 8.8 9.9 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 min(): 0 max(): 9.9 sum(): 49 ```