浅谈valarray

valarray是C++中很冷门的容器之一。尽管冷门，其实挺有意思的。 # valarray是什么？ [cppreference.com](https://zh.cppreference.com/)是这么介绍valarray的: > **std::valarray** 是表示并操作值数组的类。它支持逐元素数学运算与多种形式的广义下标运算符、切片及间接访问。 换句话说，valarray就是一种数组的替代品而已，和vector基本相同。但是**valarray比vector慢很多**，如果需要vector的（更快的）替代品，basic_string能够胜任。 既然这么慢，还要它干嘛呢？因为它对数值操作提供了一些简写和优化。 # valarray的定义和基本操作 前面说了valarray和vector基本相同，定义也是类似的。 ```cpp valarray<int> v; // 一个空的valarray valarray<int> v(2,3); // 由3个2组成的valarray valarray<int> v{2,3,4}; // 需要C++11，一个内容为2,3,4三个数的valarray ``` valarray的访问和数组一样，可以直接访问下标：`v[i]`表示（从0开始标号的）第i个元素。用`v.size()`获取v的大小。 如果使用C++11，可以和大部分其他的STL一样使用range-based for遍历： ```cpp for(int i:v)printf("%d\n",i); ``` # valarray独有的操作 valarray支持像`std::bitset`一样的，把数组看成一个整体的操作。比如把一个valarray中的元素逐个地加到另一个valarray的对应位置上，可以直接写 `u+=v`这样的语句。 这在写高斯消元等等算法的时候会方便很多，让普通的高斯消元和异或方程组的消元一样简短。 举一个例子吧： ```cpp #include<bits/stdc++.h> using namespace std; valarray<double> a{2,3,4},b{1,2,3},c{3,2,1}; double s(double x){return 1/(1+exp(-x));} //相信大家都知道这个函数 int main(){ c+=a; //此时c为{5,5,5} c/=2.5+b; //此时c为{1.429,1.111,0.909} b=cos(c)+log(a); //此时b为{0.835,1.542,2.001} a=b.apply(s); //此时a为{0.697,0.824,0.881} return 0; } ``` 这里的`2.5+b`指把b中的每个元素加上2.5，cos(c)是c中的每个元素的cos值组成的valarray（**表面上**）。`b.apply(s)`指b中的每个元素的s函数值组成的valarray。 为什么不能直接写s(b)呢？因为cos、log之类的函数是C++自带的，已经对于valarray重载了，而自定义的s函数没有对于valarray重载，所以必须写`b.apply(s)`。（经管理员大大提醒，把s声明成模板函数就可以直接`s(b)`了） valarray有`min()`、`max()`、`sum()`三个成员函数，用以计算一个数组的最小值、最大值与和。还有一个`cshift()`函数用于循环移位：比如如果a是{1,2,3},`a.cshift(1)`就是{2,3,1}。 # 更加高端的操作 如果说valarray只有这些功能的话，和手工写一个for循环有什么区别呢？ 当然不是这样。valarray还支持`slice`、`gslice`、`mask_array`这些操作。（这里可能表述不够精准） ## slice `slice(start,size,stride)`表示一个从第start位开始的，相邻两位间隔为stride，长度为size的切片。有点类似于python的`a[2:4]`这样的概念。 比如a为{2,3,4,5,6}，`a[slice(1,2,2)]`就是{3,5}。 slice最常见的应用就是表示一个子串，可以配合使用valarray和C++11的其它特性简化代码。也有更加精妙的应用，比如这个使用一维数组的矩阵类： ```cpp class Matrix{ valarray<int> data; int dim; public: Matrix(int r,int c):data(r*c),dim(c){} int& operator()(int r,int c){return data[r*dim+c];} int trace()const{ return data[slice(0,dim,dim+1)].sum(); } }; ``` 这个trace()函数计算的是主对角线的元素和，stride是dim+1的意思是每次往下跳一行再右移一格。你会发现使用slice，可以统一地表示矩阵的各行、各列、各对角线，并且把这些元素当成一维数组处理。 ## gslice 表示一些slice组成的集合。（对我来讲）没什么用。 ## mask_array 表示一个valarray中符合某个条件的元素的下标集合。比如把a数组中所有奇数值加上b数组中对应位置的值，一句话就够了： ```cpp a[a%2==1]+=b; ``` 此处的a%2不是一个数，（**表面上**）是另一个valarray；a%2==1不是一个bool，是一个mask_array。 是不是感觉这C++已经写的不像C++了？ # 总结 valarray可以简化C++中各种批量数值操作的代码，但**常数较大**。 这里的常数较大是相对不封装的写法，比你自己封装的肯定要快。为什么？因为valarray使用了一个叫做“表达式模板”的技巧。这也是前面我特别加上了几个“表面上”的原因，这个返回值实际是一个**完整的表达式树**，然后被隐式转换成了valarray。这样可以去掉所有的临时赋值。 这个常数较大也并不绝对，某些编译器针对valarray进行了并行计算之类的优化，可以在速度上碾压手写的代码。 如果想要更高级的数值算法支持，可以使用python的NumPy。 最后来张图展示一下C++17、valarray一个别的特性还有我的gedit主题：  # UPD：使用注意事项 今天我用valarray尝试着写了一道高斯消元题，发现一个玄学问题。关键代码如下： ```cpp for(int j=0;j<=n;j++)if(!vis[j]) v[j]-=v[f[i]]/v[f[i]][i]*v[j][i]; ``` 我的高斯消元是不swap的，所以开了一个vis数组。（**表面上**）毫无问题。调试了好久之后终于发现问题还是出在valarray上。 valarray的表现并不像表面上那样是先把等于号右侧算出来再赋值到左侧的。使用valarray的时候**千万不要忘记它的结果类型是一棵表达式树**，具体来说是这样的： ```cpp _Expr<_BinClos<std::__minus, _ValArray, _Expr, typename _BinClos<__multiplies, _Expr, _Constant, _BinClos<__divides, _ValArray, _Constant, double, double>, double>::value_type, std::_BinClos<std::__multiplies, _Expr, _Constant, std::_BinClos<std::__divides, _ValArray, _Constant, double, double>, double> >, typename __fun<__minus, typename _BinClos<__multiplies, _Expr, _Constant, _BinClos<__divides, _ValArray, _Constant, double, double>, double>::value_type>::result_type> ``` 于是经过编译器的复杂化简之后，等效于如下的语句（就是普通的写法循环顺序写反了）： ```cpp for(int j=0;j<=n;j++)if(!vis[j]) for(int k=0;k<=n+1;k++) v[j][k]-=v[f[i]][k]/v[f[i]][i]*v[j][i]; ``` 这当然是错的，因为右侧的比例因子`v[j][i]`是**一边计算一边变化**的。所以不能这么偷懒。把它预存下来就正确了： ```cpp #define vad valarray<double> ...... for(int j=0;j<=n;j++)if(!vis[j]){ vad c=v[f[i]]/v[f[i]][i]*v[j][i]; v[j]-=c; } ``` 所以能够吸取这样一个教训：valarray的语法糖和循环写法之间几乎没有区别，**循环顺序的错valarray中一样会犯**。 这里顺便介绍一个小技巧，用来显示C++中的变量类型，利用了[typeid运算符](https://zh.cppreference.com/w/cpp/language/typeid)和[libstdc++的demangle](https://gcc.gnu.org/onlinedocs/libstdc++/manual/ext_demangling.html): ```cpp #include<bits/stdc++.h> #include<cxxabi.h> using namespace std; template<class T> void printType(const T&x){ cout<<abi::__cxa_demangle(typeid(x).name(),0,0,NULL)<<endl; } ``` 然后调用`printType`函数就会输出变量的类型。 `printType(qsort)` 输出：`void (void*, unsigned long, unsigned long, int (*)(void const*, void const*))` `printType(valarray<int>{2,3,4}/10*5)` 输出：`std::_Expr<std::_BinClos<std::__multiplies, std::_Expr, std::_Constant, std::_BinClos<std::__divides, std::_ValArray, std::_Constant, int, int>, int>, int>`