八、C++标准库补充与总结

补充bitset+容器使用建议

bitset（可当作一个bool类型的集合）

bitset类相当于一个二进制集合，并且能处理超过long long类型大小的位集合。

bitset可以与string和整型相互转化。

1.bitset对象的定义和初始化方法（n是一个大于0的整形字面值常量）

※ bitset<n> b(u);等价于bitset<n> b=u;

以string赋值bitset的例子：

2.bitset支持的操作（bitset可当作一个bool类型的集合）

※ 需要特别注意bitset的下标是从最右边开始的！！（如bitset<4> b=2;(此时b是0010)中b[1]为1而不是0）

3.bitset实现整数十进制与二进制的相互表示

1）十进制到二进制：cin>>n;cout<<bitset<8>(n);（此处n为十进制数；bitset长度为8，但可按需改变）

2）二进制到十进制：cin>>b;cout<<b.to_ulong();（此处b为一个bitset）

function类型和函数式编程

1.function类型

function<T>可以看作是一个函数的“容器”。创建其时，需要额外提供能够表示函数的类型信息，即需要向function类型提供想让它封装的函数的【返回类型以及参数列表】。如下定义了一个接受两个char类型参数，返回一个int类型参数的函数的function类型对象：

因此对f赋值时，应赋予其一个函数对象，且该函数对象的参数列表和返回类型都应与f封装的函数对象的参数列表和返回类型相匹配。例如：

2.函数式编程

函数式编程就是把函数当作普通的变量一样使用。同样的，可以定义一个函数，让它以另一个函数对象为参数。如下展示了find_if算法的简单实现：

命名冲突

在定义的函数名已经存在在C++标准库中时，会造成编译错误，称其为命名冲突。

错误提示通常是：error:reference to '###' is ambiguous，'###'表示发生命名冲突的名字。

出现这种错误提示后，将原来命名的函数改为首字母大写或换名即可。

容器的关系运算

1.前面章节所叙述的所有容器均支持==与!=运算符；除无序关联容器以外的所有容器均支持比较运算符（<、<=、>、>=）。

2.由于容器支持关系运算，所以容器之间不仅可使用关系运算符直接比较，还可以将容器作为参数传递给max、min等函数。

容器选择建议（根据顺序容器、关联容器、容器适配器的性质（见4、6、7章））

①除非有更好的理由选择其他容器，否则应使用vector（默认首选vector）。

②程序要求在容器中间插入或删除元素，使用list（双向链表任何位置增删都快，但没法随机访问）。

③程序不会在中间插入删除，但可能在头尾插入删除元素，分以下情况（结合数据结构即可，不用刻意记）：

1）在尾部插入删除，若不要求随机访问，使用stack栈（LIFO），否则使用vector。（容器适配器不支持随机访问，vector也可作为stack的底层实现）

2）在头部插入删除，若不要求随机访问，使用queue队列（FIFO），否则使用deque。（容器适配器不支持随机访问，deque一般作为queue的底层实现）

3）头尾都有插入删除，使用deque（双端队列头尾增删都快）。

④使用string存储字符串，弃用字符数组（内置数组等同array，不可增删元素不便于操作）。

⑤使用pair或tuple时，若持有的元素类型都相同（假设为T），应用array<T,2>代替pair<T,T>，用array<T,n>代替tuple<T,T,...,T>（n为tuple的元素个数）。因为array支持下标运算符，访问元素更方便。

⑥程序要求对序列去重，可以直接使用set或unordered_set（关键字不可重复，故会自动去重），而不要使用unique，因为unique去重只针对相邻的元素，要对整个序列去重还要先排序，效率低下。

⑦要求建立两种数据之间的映射关系，可以使用unordered_map或map。

⑧vector+sort与set、map（即静态用前者、实时用后者）：若要求一边保持元素有序，一边还要插入新的元素或删除元素，使用set、map（若元素不会重复，用set；否则用map，键表示元素，值表示该元素出现的次数），否则使用vector+sort。

⑨程序不要求元素有序，但要求每次找出容器中某种规则下最优的元素，使用priority_queue，其在类似的复杂情景模拟题中特别好用。

泛型算法使用建议

①容器适配器不支持迭代器，因此不能使用泛型算法。且一般只对顺序容器使用泛型算法。

②对同个算法，若有泛型算法和容器的成员函数版本，优先使用容器的成员函数版本。例如list的成员函数版本的remove和unique。

③若使用可以接收函数对象的泛型算法，应尽可能地传递lambda表达式作参数。

④lambda表达式的参数最好都设置为常引用类型，即lambda表达式内的代码不应该改变参数的值。lambda表达式中代码逻辑也应尽量简单，一般在1~5行为宜。