C++中的STL与标准库算法

By FunnyAWM运行环境说明本章及以后章节换用Windows 64位x86 MinGW GCC编译器进行编译及运行。在C中我们有一组绝大部分编译器都共有的文件这些文件被称作标准库。其中STL也在标准库的范围内。这一章我们来具体探讨一下C中的STL标准模板库容器与标准库函数。在这个仓库中可以找到大量对本章知识的应用。其中大部分容器出于Qt的限制改为了使用Qt提供的容器版本与标准STL容器可能有部分不同STL容器可能缺失了部分方法仅供参考。1. STL容器1. 有哪些容器STL中包含的常用容器有string、vector、map、unordered_map等。受限于文章篇幅我们在这一章里只重点讲述string与vector容器其他容器可能会有提及。2. stringC的字符串容器string容器应该是我们最常用的STL容器之一。string容器可以通过使用C字符串、复制、移动、使用有参构造函数等进行初始化。其中类提供的特殊有参构造函数如下函数描述string(size_type n, char c)创建一个包含n个元素的string对象其中每一个元素都被初始化为字符ctemplateclass Iter string(Iter begin, Iter end)从迭代器范围创建string对象string(const string str, string size_type pos 0, size_type n npos)创建string对象数据为从pos位置开始的n个字符如果n没有指定则为到结尾string(initializer_listchar il)根据初始化列表创建对象将在后面详细讲述容器初始化列表我们可以直接使用cin或getline函数来向string对象中输入数据。string对象的长度是可变的在对象空间不足时会自动扩容。例如std::string str1;std::cinstr1;std::getline(std::cin,str1);// 这种方式同样可以用于从文件流构造字符串getline函数的第一个参数是一个istream流它可以从用户键盘或文件中读取数据并初始化对应的对象。我们将在后续章节详细讲解C的IO流。由于string类重载了[]运算符它也可以被当做常规的C字符串被访问。string类提供了很多功能包括查找子串、获取字符串长度、删除或替换字符等。STL类中的所有函数都能够在Cpp Reference找到在这里不再赘述。3. vectorC的可变长数组与string类似vector也具有可变长度特性。vector属于我们之前提到的泛型类它接受一个任意类型的模板参数然后根据模板类型来初始化对象。vector同样为我们提供了很多功能包括获取元素数目、交换容器内容、获取容器的迭代器等。这里我们不再赘述其他方法重点讲述一下STL容器中迭代器的概念。4. 迭代器迭代器可以被当做指向容器元素的指针使用但其并不指向任何实际对象常用于遍历整个容器。例如voidMSTDataSource::updateFavoriteBatch(constQListFavoriteUpdateupdates){query.exec(BEGIN TRANSACTION);for(autoupdateupdates.begin();update!updates.end();update){prepareStatement(UPDATE musicInfo SET favorite :fav WHERE fileName :fileName);bindValue(:fav,update-isFavorite);bindValue(:fileName,update-fileName);execQuery();}query.exec(COMMIT);}当然由于QList具有迭代器与可迭代特性上述代码也可以用C的范围for循环进一步简化voidMSTDataSource::updateFavoriteBatch(constQListFavoriteUpdateupdates){query.exec(BEGIN TRANSACTION);for(constautoupdate:updates){prepareStatement(UPDATE musicInfo SET favorite :fav WHERE fileName :fileName);bindValue(:fav,update.isFavorite);bindValue(:fileName,update.fileName);execQuery();}query.exec(COMMIT);}几乎所有具有迭代器的容器也都支持反向迭代操作。要实现反向迭代只需要将begin()与end()改为rbegin()与rend()即可。end()迭代器指向的对象都是容器中最后一个对象的后一对象。所有涉及到双迭代器的操作后续用it1代表靠前的迭代器用it2代表靠后的其包含的范围都是[it1, it2)包括it1指向的元素但不包含it2指向的元素。迭代器有以下几个不同的类型输入迭代器只读迭代器单向移动只能遍历一次适用于从文件或输入流中读取数据输出迭代器只写迭代器单向移动只能遍历一次适用于将数据输出到文件或输出流中前向迭代器结合了前两种迭代器的特点同时支持了多次遍历双向迭代器在前向迭代器的基础上实现了双向移动随机访问迭代器在双向迭代器的基础上加入了任意位置跳转的能力。随机访问迭代器支持常数时间的任意位置跳转O ( 1 ) O(1)O(1)而其他迭代器只能通过逐步移动来访问元素从当前位置移动到任意位置的时间复杂度为O ( n ) O(n)O(n)。时间复杂度描述了某个算法或操作需要耗费的时间随输入规模的变化趋势。其中O ( 1 ) O(1)O(1)代表该算法或操作在使用任意参数时耗费的时间恒定而O ( n ) O(n)O(n)代表该算法或操作需要的时间随需要进行该操作的元素数量呈线性增长。相似的表述还有O ( n 2 ) O(n^2)O(n2)需要的时间随元素数呈二次增长、O ( l o g n ) O(log n)O(logn)需要的时间随元素数呈对数增长、O ( n l o g n ) O(n log n)O(nlogn)需要的时间随元素数呈线性对数增长、O ( 2 n ) O(2^n)O(2n)需要的时间随元素数呈指数增长、O ( n ! ) O(n!)O(n!)需要的时间随元素数呈阶乘增长等。注意1当容器发生结构性变化例如vector扩容、deque插入中间元素时针对当前容器的迭代器将全部失效需要重新为其赋值。使用失效的迭代器可能会引起未定义行为。2. 标准库算法标准库算法为我们提供了一系列方便的功能包括以下几方面非修改式序列操作例如for_each()与find()等修改式序列操作例如transform()、random_shuffle()、any_of()、remove_if()等排序、交换等及其相关操作例如sort()与swap()等通用数字运算。这些函数主要集中在algorithm头文件一些基础数学运算函数则在numeric头文件中。以下我们选取几个典型函数进行详细讲解所有函数的使用方法都能够在Cpp Reference找到。any_of与remove_if函数于C11中被实现而random_shuffle函数已在C17中被移除在C11及以后更推荐使用std::shuffle。1. for_each该函数接收两个迭代器参数与一个函数指针或Lambda表达式对迭代器范围内的所有对象执行函数或Lambda操作。2. xxx_of宇宙与xxx_if宇宙这些函数都是从C11开始引入的算法极大方便了对容器的元素筛选与整体判断操作。any_of函数接收两个迭代器参数与一个函数指针或Lambda表达式用于判断迭代器范围中是否有元素满足函数或Lambda表达式中描述的条件。其中函数指针或Lambda表达式必须满足谓词要求即要求这个函数的返回类型必须为bool。all_of对参数的要求同any_of用于判断迭代器范围中是否所有元素都满足要求。none_of对参数的要求同any_of用于判断迭代器范围中是否没有元素满足要求。以上所有函数在满足判断时返回true不满足时返回false。remove_if函数对参数的要求同any_of但是remove_if的作用为将所有不满足函数或Lambda表达式中描述的条件的元素移动到容器尾并返回一个新范围结尾的尾迭代器。这个函数配合erase函数可以用于快速筛选满足指定要求的值被称为擦除移除手法。例如std::string strThe quick brown fox jumps over the lazy dog;str.erase(std::remove_if(str.begin(),str.end(),[](unsignedcharch){returnstd::isspace(ch);// 需要包含cctype以使用isspace函数}),str.end());// 这个操作移除了容器中的所有空格字符从C20开始这个操作也可以被直接被erase_if替代直接实现移除擦除手法一步到位。3. 排序与交换1. 排序sort函数为我们提供了标准库内部支持的排序操作对于可比较类型直接调用sort函数即可。对于自定义类型通常需要手动实现operator以满足可比较特性或手动传入返回bool类型的比较函数以满足可比较特性。如果没有实现可比较特性编译器会在编译时抛出如下报错// 示例代码#includelistusingnamespacestd;structMyStruct{inta;};intmain(){std::listMyStructlist;list.sort();// 这里使用的是list容器的sort成员函数而非std::sort这是因为list无法满足标准sort函数的随机访问迭代器要求list只有双向迭代器}In file included from E:/JetBrainsTools/CLion/bin/mingw/lib/gcc/x86_64-w64-mingw32/13.1.0/include/c/list:65, from C:/Users/11429/CLionProjects/toturial/main.cpp:2: E:/JetBrainsTools/CLion/bin/mingw/lib/gcc/x86_64-w64-mingw32/13.1.0/include/c/bits/stl_list.h: In instantiation of bool std::__detail::_Scratch_list::_Ptr_cmp_Iter, void::operator()(std::__detail::_List_node_base*, std::__detail::_List_node_base*) const [with _Iter std::_List_iteratorMyStruct]: E:/JetBrainsTools/CLion/bin/mingw/lib/gcc/x86_64-w64-mingw32/13.1.0/include/c/bits/stl_list.h:203:18: required from void std::__detail::_Scratch_list::merge(std::__detail::_List_node_base, _Cmp) [with _Cmp _Ptr_cmpstd::_List_iteratorMyStruct, void] E:/JetBrainsTools/CLion/bin/mingw/lib/gcc/x86_64-w64-mingw32/13.1.0/include/c/bits/list.tcc:515:23: required from void std::__cxx11::list_Tp, _Alloc::sort() [with _Tp MyStruct; _Alloc std::allocatorMyStruct] C:/Users/11429/CLionProjects/toturial/main.cpp:11:14: required from here E:/JetBrainsTools/CLion/bin/mingw/lib/gcc/x86_64-w64-mingw32/13.1.0/include/c/bits/stl_list.h:188:34: error: no match for operator (operand types are MyStruct and MyStruct) 188 | { return *_Iter(__lhs) *_Iter(__rhs); } | ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~这里的报错原因是由于我们既没有实现operator也没有实现自定义比较函数sort函数由于无法建立严格弱序关系而报错。DLC从离散数学角度解释排序为什么要实现正确比较STL的排序算法要求元素上存在一种严格弱序关系从数学上讲这要求operator函数或自定义比较函数必须定义该集合上的一个二元关系R ( a b ) R(a b)R(ab)。STL要求这样的R必须满足以下三条公理非自反性Irreflexive对于集合中的任意元素a aa,a a a aaa恒为假。即任何元素都不能小于自身;非对称性Asymmetric对于任意元素a , b a, ba,b如果a b abab为真那么b a baba必然为假。不能出现“相互小于”这种左右脑互搏的情况。传递性Transitive对于任意元素a , b , c a,b,ca,b,c如果a b abab且b c bcbc那么a c acac必然为真。如果其中的任意一条公理无法满足就会导致该R在集合上的关系不再是一个偏序关系。这将导致排序算法无法保证满足其不变式进而导致算法结果不可预测。假设我们有以下代码#includeiostream#includevector#includealgorithmstructBroken{intvalue;};intmain(){autobroken_compare[](constBrokena,constBrokenb){if(a.value%20b.value%21)returntrue;if(a.value%21b.value%20)returnfalse;returna.valueb.value;};std::vectorBrokenvec{{2},{3},{5},{1},{4}};std::sort(vec.begin(),vec.end(),broken_compare);// 结果不可预测可能死循环或错误排序for(constautox:vec){std::coutx.value ;}return0;}很明显上述代码中的broken_compare函数不满足偏序关系中要求的传递性进而导致sort函数的结果不可预测甚至导致未定义行为。2. 交换swap函数能够实现对任意相同类型变量的值交换操作这要求元素必须实现可复制特性即有能够使用的复制构造函数即便它是默认的。从C11开始swap函数会优先使用移动构造函数实现交换行为如移动构造函数不可用则会退化到复制行为。对于STL容器部分容器实现了自己的swap成员函数用于快速交换整个容器而不需要逐个交换元素。