站正巨人的肩膀上——C++概要

3. C++

3.1 概览

函数指针、位运算、引用、const、动态内存分配、内联函数、重载函数、函数缺省参数、面向对象、复制构造函数、类型转换构造函数、析构函数、静态成员变量、成员对象、封闭类、友元、this指针、常量对象、常量成员函数、常引用、运算符重载（赋值运算符重载）、运算符重载为友元函数、可变长数组、流插入运算符和流提取运算符的重载、自增自减运算符重载、派生和继承、复合关系和继承关系、基类派生类同名成员与protected、派生类的构造函数、Public继承的赋值兼容性规则、多态和虚函数、多态的实现原理、虚析构函数、纯虚函数和抽象类、文件操作、函数模板、类模板、string类、输入输出、流操纵算子、标准模板库、vector、list和deque、Set和multiset、map和multimap、Adapters…

3.2 函数指针

程序运行时，函数占据一片连续的内存空间，函数名表示这片空间的起始地址，可以将该地址赋给一个指针变量，使变量指向该函数，然后可通过指针变量调用函数。该指针变量称为函数指针

如何定义？

类型名 (* 指针变量名)(参数类型1, 参数类型2,…);

用法？

函数名赋给函数指针，调用方法：函数指针名(实参表);

实例？

C语言提供了快排库函数：void qsort(void *base, int nelem, unsigned int width,int(* pfCompare)( const void *, const void *));参数分别表示：数组起始地址、数组元素个数、每个元素大小、排序规则(比较函数的地址)。最后一个参数便是函数指针类型。
比较函数的写法：int 函数名(const void * elem1, const void * elem2);略

p.s. main函数的参数为：int argc, char * argv[]

argc: 代表启动程序时，命令行参数的个数。C/C++语言规定，可执行程序程序本身的文件名，也算一个命令行参数，因此，argc的值至少是1
argv: 指针数组，其中的每个元素都是一个char* 类型的指针，该指针指向一个字符串，这个字符串里就存放着命令行参数

3.3 位运算

略
例1. 有两个int型的变量a和n(0 <= n <= 31)，要求写一个表达式，使该表达式的值和a的第n位相同

(a >> n) & 1 或 (a & (1 << n)) >> n

3.4 引用

如何定义一个引用？

类型名 & 引用名 = 变量名;

引用和原变量有何关系，如何理解？

等价。引用相当于是原变量的别名。

引用的注意事项？

定义引用时必须初始化，且引用后不可再引用其他变量

常引用？

添加const关键字，不能通过常引用去修改其引用的内容

常引用与非常引用转换？

略

3.5 const

作用？

定义常量、常量指针、常引用

常量指针？

不可通过常量指针修改其指向的内容，不能把常量指针赋值给非常量指针，反过来可以。常量指针的意义：?函数参数为常量指针时，可避免函数内部不小心改变参数指针所指地方的内容

3.6 动态内存分配

如何实现动态内存分配？

P = mew T;P是类型为T*的指针，动态分配出一片大小为 sizeof(T)字节的内存空间，并且将该内存空间的起始地址赋值给P

如何动态分配数组？

P = new T[N];类型为T*的指针。动态分配出一片大小为 sizeof(T)字节的内存空间，并且将该内存空间的起始地址赋值给P

如何释放动态分配的内存？

delete指针，对于数组，要加[]

3.7 内联函数

内联函数机制如何？

inline关键字，插入函数代码，而非调用

3.8 函数重载

何为函数重载？

函数名同，参数个数或参数类型不同

3.9 函数的缺省参数

如何定义缺省参数？

定义函数的参数列表最右边的连续若干个参数有缺省值

3.10 面向对象

类如何定义？

class关键字，最后记得加;

对象的内存分配如何？

对象的大小 = 所有成员变量的大小之和

对象支持哪些运算？

可以用=赋值，不能进行比较，除非重载

如何访问类的成员变量和成员函数？

对象名.成员名
指针->成员名
引用名.成员名

类的成员函数有哪些写法

函数体和定义分开写，需要用::符

3.11 构造函数

何为构造函数？

名字与类名相同，可以有参数，不能有返回值，其作用是对对象进行初始化，没有写构造函数的话，编译器会生成一个默认的无参构造函数，否则不会生成

构造函数何时调用？

对象生成时自动调用，生成后不会再调用

构造函数如何修饰？

public，private构造函数不能直接用来初始化对象

3.12 类成员的可访问范围

类成员的可访问范围有哪些关键字？

• private: 指定私有成员, 只能在成员函数内被访问
• public: 指定公有成员, 可以在任何地方被访问
• protected: 指定保护成员

缺省是哪种修饰符？

private

设置私有成员的目的？

强制对成员变量的访问一定要通过成员函数进行

3.13 复制构造函数

何为复制构造函数？

唯一参数，为同类对象的引用，形如X::X(X&)或X::X(const X&),如果没有定义复制构造函数，那么编译器生成默认复制构造函数。默认的复制构造函数完成复制功能。如果定义了自己的复制构造函数，则默认的复制构造函数不存在

复制构造函数起作用何时起作用？

1)当用一个对象去初始化同类的另一个对象时
2)如果某函数有一个参数是类 A 的对象，那么该函数被调用时，类A的复制构造函数将被调用
3)如果函数的返回值是类A的对象时，则函数返回时，A的复制构造函数被调用

3.14 类型转换构造函数

类型转换构造函数的目的是什么？

实现类型的自动转换

何为实现类型的自动转换？

只有一个参数，且不是复制构造函数

p.s.类型不匹配时，会建立一个临时对象/临时变量

3.15 析构函数

何为析构函数？

名字与类名相同，前面加~，没有参数和返回值，一个类最多有一个析构函数

析构函数机制是怎样的？

对象消亡时，自动被调用，以处理善后工作，如释放分配的空间等

缺省？

定义类时没写析构函数, 则编译器生成缺省析构函数，不涉及释放用户申请的内存释放等清理工作。定义了析构函数, 则编译器不生成缺省析构函数

析构函数与数组关系?

对象数组生命期结束时,对象数组的每个元素的析构函数都会被调用

析构函数与delete?

delete运算导致析构函数调用

3.16 静态成员

何为静态成员？

static修饰

静态成员特性？

普通成员变量每个对象有各自的一份，而静态成员变量一共就一份，为所有对象共享
普通成员函数必须具体作用于某个对象，而静态成员函数并不具体作用与某个对象
因此静态成员不需要通过对象就能访问

p.s.sizeof不会计算静态成员变量

如何访问静态成员？

类名::成员名
对象名.成员名
指针->成员名
引用.成员名

限制？

在静态成员函数中，不能访问非静态成员变量，也不能调用非静态成员函数

3.17 成员对象和封闭类

何为成员对象？何为封闭类？

一个类的成员变量是另一个类的对象。包含成员对象的类为封闭类

封闭类如何初始化？

定义构造函数时，添加初始化列表
类名::构造函数(参数表):成员变量1(参数表),成员变量2(参数表),… { }

调用顺序？

当封闭类对象生成时：先执行所有成员对象的构造函数，再执行封闭类的构造函数
成员对象的构造函数调用顺序和成员对象再类中的说明顺序一致，与在成员初始化列表中出现的顺序无关
当封闭类的对象消亡时，先执行封闭类的析构函数，再执行成员对象的析构函数

3.18 友元

如何定义友元？

friend

友元?

友元函数和友元类。一个类的友元函数可以访问该类的私有成员

p.s.友元类之间的关系不能传递, 不能继承

3.19 this指针

作用?

指向成员函数所作用的对象
非静态成员函数中可以直接使用this来代表指向该函数作用的对象的指针

this指针和静态成员函数?

静态成员函数中不能使用 this 指针,因为静态成员函数并不具体作用与某个对象,因此，静态成员函数的真实的参数的个数，就是程序中写出的参数个数

3.20 常量对象、常量成员函数和常引用

常量对象?

前面加const修饰，则对象值无法改变

常量成员函数?

后面加在类的成员函数说明后面可以加const关键字，则该成员函数成为常量成员函数。常量成员函数执行期间不应修改其所作用的对象，在常量成员函数中不能修改成员变量的值(静态成员变量除外)，也不能调用同类的非常量成员函数(静态成员函数除外)

p.s.两个成员函数，名字和参数表都一样，但是一个是const,一个不是，算重载

常引用?

引用前加const。不能通过常引用，修改其引用的变量

对象作为函数的参数时，生成该参数需要调用复制构造函数，效率比较低。用指针作参数，代码又不好看，如何解决？

可以用对象的引用作为参数,若想防止改变，可使用常引用

3.21 运算符重载

p.s. c++预定义的运算符只能用于基本数据类型, 用户自定义的数据类型——类，可以使用运算符重载

何为运算符重载?

对已有的运算符赋予多重的含义;使同一运算符作用于不同类型的数据时,产生不同的行为

如何运算符重载?

实质仍是函数重载。
返回值类型 operator 运算符 (形参表) { }

运算符重载机制?

程序编译时，把含运算符的表达式，转换为对运算符函数的调用。
把运算符的操作数，转换为运算符函数的参数
运算符被多次重载时，根据实参的类型决定调用哪个运算符函数
运算符可以被重载为普通函数
也可以被重载为类的成员函数

3.22 赋值运算符重载

为何赋值运算符重载?

支持=两边类型不匹配，注意，赋值运算符只能重载为成员函数

何为浅复制何为深复制?

前者是引用的改变，后者是引用内容的复制，即将一个对象中指针变量指向的内容复制到另一个对象中指针成员对象指向的地方

3.23 运算符重载为友元

p.s. 通常, 将运算符重载为类的成员函数

何时重载为友元函数？

成员函数不能满足使用要求 或 普通函数, 又不能访问类的私有成员

3.24 可变长数组(运算符重载实例)

如何实现可变长？

要用动态分配的内存来存放数组元素，需要一个指针成员变量

如何重载=?

CArray & CArray::operator=(const CArray & a) {
    if (ptr == a.ptr)
        return *this;
    if (a.ptr == NULL) {
        if (ptr)
            delete[] ptr;
        ptr = NULL;
        size = 0;
        return *this;
    }
    if (size < a.size) {
        if (ptr)
            delete[] ptr;
        ptr = new int[a.size];
    }
    memcpy(ptr, a.ptr, sizeof(int)*a.size);
    size = a.size;
    return *this;
}

如何重载[]?

int & CArray::operator[](int i) {
    return ptr[i];
}

3.25 流插入和流提取运算符的重载

cout是什么？

cout是在iostream中定义的，ostream类的对象，iostream对<<进行了重载

流插入运算符的重载如何？

ostream & ostream::operator<<(int n) {
    ...
}

3.26 自增自减运算符重载

自增自减运算符有前置/后置之分，如何重载？

前置运算符作为一元运算符重载
后置运算符作为二元运算符重载

3.27 继承和派生

何为继承?

基类 - 子类

private?

在派生类的各个成员函数中，不能访问基类中的private成员

写法?

class 派生类名 : public 基类名 { };

派生类对象的内存空间如何?

派生类对象的体积，等于基类对象的体积，再加上派生类对象自己的成员变量的体积。在派生类对象中，包含着基类对象，而且基类对象的存储位置位于派生类对象新增的成员变量之前

3.28 复合关系和继承关系

属性?

二者均是类间关系，前者是"有"的关系，后者是"是"的关系

3.29 基类/派生类同名成员与Protected关键字

默认访问?

派生类，若要访问基类同名成员，可加类作用域修饰符

访问范围说明符?

基类的private成员: 可以被下列函数访问

• 基类的成员函数
• 基类的友员函数

基类的public成员: 可以被下列函数访问

• 基类的成员函数
• 基类的友员函数
• 派生类的成员函数
• 派生类的友员函数
• 其他的函数

基类的protected成员: 可以被下列函数访问

• 基类的成员函数
• 基类的友员函数
• 派生类的成员函数可以访问当前对象的基类的保护成员

3.30 派生类的构造函数

执行顺序?

执行派生类构造函数之前, 先执行基类的构造函数
派生类的析构函数被执行时, 执行完派生类的析构函数后, 自动调用基类的析构函数

如何构造派生类构造函数?

构造函数名(形参表): 基类名(基类构造函数实参表) { }

如何调用基类构造函数?

显式方式: 在派生类构造函数中调用
隐式方式：

• 派生类的构造函数中, 省略基类构造函数时，派生类的构造函数, 自动调用基类的默认构造函数

3.31 public继承的赋值兼容规则

如何兼容?

• 派生类的对象可以赋值给基类对象
• 派生类对象可以初始化基类引用
• 派生类对象的地址可以赋值给基类指针

p.s. 以上三条规则限定public，如果派生方式是 private或protected，则上述三条不可行

3.32 虚函数和多态

如何标识虚函数?

virtual关键字标识成员函数，注：只需标识声明，定义不需要

多态表现一?

派生类的指针可以赋给基类指针，通过基类指针调用基类和派生类中的同名虚函数时

• 若该指针指向一个基类的对象，那么被调用是基类的虚函数
• 若该指针指向一个派生类的对象，那么被调用的是派生类的虚函数

多态表现二?

派生类的对象可以赋给基类引用, 通过基类引用调用基类和派生类中的同名虚函数时

• 若该引用引用的是一个基类的对象，那么被调用是基类的虚函数
• 若该引用引用的是一个派生类的对象，那么被调用的是派生类的虚函数

3.33 多态的实现原理

何为动态联编?

基类指针或引用调用虚函数时，编译时无法确定调用的是基类还是派生类，运行时才能确定

如何实现动态联编?

虚函数表。每一个有虚函数的类（或有虚函数的类的派生类）都有一个虚函数表，该类的任何对象中都放着虚函数表的指针。虚函数表中列出了该类的虚函数地址。多出来的4个字节就是用来放虚函数表的地址的。

多态的函数调用语句被编译成一系列根据基类指针所指向的（或基类引用所引用的）对象中存放的虚函数表的地址，在虚函数表中查找虚函数地址，并调用虚函数的指令

3.34 虚析构函数

何为虚析构函数?

将基类的析构函数声明为virtual,派生类的析构函数 virtual可以不进行声明

通过基类的指针删除派生类对象时,顺序如何?

首先调用派生类的析构函数，然后调用基类的析构函数

3.35 纯虚函数与抽象类

何为纯虚函数?

没有函数体的虚函数

何为抽象类?

包含纯虚函数的类

抽象类限制?

只能作为 基类 来派生新类使用;不能创建抽象类的对象；抽象类的指针和引用可指向由抽象类派生出来的类的对象

3.36 文件操作

文件流类?

文件操作流程?

打开文件->读/写文件->关闭文件

略

3.37 函数模板

何为泛型?

算法实现时不指定具体要操作的数据的类型

如何实现?

函数模板、类模板

函数模板?

template <class 类型参数1， class 类型参数2, …>
返回值类型 模板名 (形参表) { 函数体 }

引入函数模板后函数调用顺序如何?

C++编译器遵循以下优先顺序:

• Step 1: 先找参数完全匹配的普通函数(非由模板实例化而得的函数)
• Step 2: 再找参数完全匹配的模板函数
• Step 3: 再找实参经过自动类型转换后能够匹配的普通函数
• Step 4: 上面的都找不到, 则报错

3.38 类模板

如何定义类模板?

template <class 类型参数1, class 类型参数2, …>
class 类模板名 { 成员函数和成员变量 };

类模板中成员函数类外定义如何写?

template <型参数表>
返回值类型 类模板名<类型参数名列表>::成员函数名(参数表) { … }

类模板如何定义对象?

类模板名 <真是类型参数表> 对象名(构造函数实际参数表);
如果类模板有无参构造函数, 那么也可以只写
类模板名 <真是类型参数表> 对象名;

机制?

编译器由类模板生成类的过程叫类模板的实例化. 编译器自动用具体的数据类型替换类模板中的类型参数, 生成模板类的代码

3.39 string类

属性?

string类是一个模板类

头文件?

<string>

性质?

长度用length()获取，支持流读取运算符，支持getline函数

赋值和连接?

支持=赋值，可用assign成员函数复制、部分复制
支持+连接，append成员函数连接

访问string中的字符?

at方法，成员函数at会做范围检查, 如果超出范围, 会抛出out_of_range异常, 而下标运算符不做范围检查

string的比较?

支持运算符比较，返回bool类型，还可用compare成员函数比较

子串?

substr()成员函数

交换?

swap()成员函数

特性?

• 成员函数 capacity():返回无需增加内存即可存放的字符数
• 成员函数maximum_size():返回string对象可存放的最大字符数
• 成员函数length()和size()相同:返回字符串的大小/长度
• 成员函数empty():返回string对象是否为空
• 成员函数resize():改变string对象的长度

查找字符?

find()，rfind()，find_first_of()、find_last_of()、find_first_not_of()、find_last_not_of()

替换字符?

成员函数erase()、find()、成员函数 replace()

插入字符?

成员函数 insert()

转为char*字符串?

c_str()成员函数、成员函数data()、成员函数copy()

3.40 输入输出

相关类?

• istream是用于输入的流类，cin是该类的对象
• ostream是用于输出的流类，cout是该类的对象
• ifstream是用于从文件读取数据的类
• ofstream是用于向文件写入数据的类
• iostream是能输入输出的类
• fstream是能从文件读写的类

输入输出重定向?

freopen()

如何判断输入流结束?

while (cin >> …) { … }

istream成员函数?

istream & getline(char * buf, int bufSize);
从输入流中读取bufSize-1个字符到缓冲区buf，或读到碰到‘\n’为止（哪个先到算哪个）
istream & getline(char * buf, int bufSize,char delim);
从输入流中读取bufSize-1个字符到缓冲区buf，或读到碰到delim字符为止（哪个先到算哪个）
两个函数都会自动在buf中读入数据的结尾添加\0’。,‘\n’或delim都不会被读入buf，但会被从输入流中取走
可以用 if(!cin.getline(…)) 判断输入是否结束
bool eof(); 判断输入流是否结束
int peek(); 返回下一个字符,但不从流中去掉
istream & putback(char c); 将字符ch放回输入流
istream & ignore( int nCount = 1, int delim = EOF );从流中删掉最多nCount个字符，遇到EOF时结束

3.41 流操纵算子

头文件?

#include <iomanip>

整数流的基数?

流操纵算子dec,oct,hex,setbase

浮点数的精度？

precision,setprecision

设置域宽?

setw,width

3.42 标准模板库STL

重用?

C++ 语言的核心优势之一就是便于软件的重用
C++中有两个方面体现重用:

• 面向对象的思想：继承和多态，标准类库
• 泛型程序设计的思想： 模板机制，以及标准模板库 STL

何为标准模板库?

标准模板库 (Standard Template Library) 就是一些常用数据结构和算法的模板的集合

STL基本概念?

容器:可容纳各种数据类型的通用数据结构,是类模板
迭代器可用于依次存取容器中元素，类似于指针
算法用来操作容器中的元素的函数模板

容器?

可以用于存放各种类型的数据（基本类型的变量，对象等）的数据结构，都是类模版,分为三种

• 顺序容器: vector、deque、list
• 关联容器: set、multiset、map、multimap
• 容器适配器: stack、queue、priority_queue

对象被插入容器中时，被插入的是对象的一个复制品。许多算法，比如排序，查找，要求对容器中的元素进行比较，有的容器本身就是排序的，所以，放入容器的对象所属的类，往往还应该重载 == 和 < 运算符

顺序容器?

容器并非排序的，元素的插入位置同元素的值无关. 有vector,deque,list 三种

vector?

头文件<vector>,动态数组。元素在内存连续存放。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能(大部分情况下是常数时间）

deque?

头文件<deque>,双向队列。元素在内存连续存放。随机存取任何元素都能在常数时间完成(但次于vector)。在两端增删元素具有较佳的性能(大部分情况下是常数时间）。

list?

头文件<list>,双向链表。元素在内存不连续存放。在任何位置增删元素都能在常数时间完成。不支持随机存取。

关联容器?

元素是排序的,插入任何元素，都按相应的排序规则来确定其位置,在查找时具有非常好的性能,通常以平衡二叉树方式实现，插入和检索的时间都是 O(log(N))

set/multiset

头文件<set>.set 即集合。set中不允许相同元素，multiset中允许存在相同的元素

map/multimap

头文件<map>.map与set的不同在于map中存放的元素有且仅有两个成员变量,一个名为first,另一个名为second, map根据first值对元素进行从小到大排序，并可快速地根据first来检索元素.map同multimap的不同在于是否允许相同first值的元素

容器适配器

stack

头文件<stack>.栈。是项的有限序列，并满足序列中被删除、检索和修改的项只能是最近插入序列的项（栈顶的项）。后进先出

queue

头文件<queue>。队列。插入只可以在尾部进行，删除、检索和修改只允许从头部进行。先进先出。

priority_queue

头文件<queue>.优先级队列。最高优先级元素总是第一个出列

顺序容器和关联容器中都有的成员函数?

• begin 返回指向容器中第一个元素的迭代器
• end 返回指向容器中最后一个元素后面的位置的迭代器
• rbegin 返回指向容器中最后一个元素的迭代器
• rend 返回指向容器中第一个元素前面的位置的迭代器
• erase 从容器中删除一个或几个元素
• clear 从容器中删除所有元素

顺序容器的常用成员函数?

• front :返回容器中第一个元素的引用
• back : 返回容器中最后一个元素的引用
• push_back : 在容器末尾增加新元素
• pop_back : 删除容器末尾的元素
• erase :删除迭代器指向的元素(可能会使该迭代器失效），或删除一个区间，返回被删除元素后面的那个元素的迭代器

迭代器作用?

用于指向顺序容器和关联容器中的元素. 迭代器用法和指针类似. 有const 和非 const两种.通过迭代器可以读取它指向的元素.通过非const迭代器还能修改其指向的元素

如何定义迭代器?

容器类名::iterator 变量名;
或
容器类名::const_iterator 变量名;

如何访问一个迭代器指向的元素?

* 迭代器变量名

迭代器操作?

迭代器上可以执行 ++ 操作, 以使其指向容器中的下一个元素.如果迭代器到达了容器中的最后一个元素的后面，此时再使用它，就会出错，类似于使用NULL或未初始化的指针一样

示例？

#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    vector<int>::const_iterator i;
    for (i = v.begin(); i != v.end(); ++i)
        cout << *i << ",";
    cout << endl;
}

3.43 vector

vector概述?

vector是可变长的动态数组，需要包含头文件#include <vector>. vector支持随机访问迭代器(根据下标随机访问某个元素时间为常数,在尾部添加速度很快,在中间插入慢),所有STL算法 都能对vector操作

vector成员函数?

• 构造函数初始化
  • vector(): 无参构造函数, 将容器初始化成空的
  • vector(int n):将容器初始化成有n个元素
  • vector(int n, const T & val):假定元素类型是T, 将容器初始化成
    有n个元素, 每个元素的值都是val
  • vector(iterator first, iterator last):将容器初始化为与别的容器上区间[first, last)一致的内容
• 其他常用函数
  • void pop_back():删除容器末尾的元素
  • void push_back(const T & val):将val添加到容器末尾
  • int size():返回容器中元素的个数
  • T & font():返回容器中第一个元素的引用
  • T & back():返回容器中最后一个元素的引用

二维动态数组

示例: vector< vector<int> > v(3)

3.44 list和deque

list?

双向链表，#include <list>.在任何位置插入/删除都是常数时间.不支持根据下标随机存取元素.具有所有顺序容器都有的成员函数

list成员函数?

• push_front 在链表最前面插入
• pop_front 删除链表最前面的元素
• sort 排序 (list 不支持 STL 的算法 sort)
• remove 删除和指定值相等的所有元素
• unique 删除所有和前一个元素相同的元素
• merge 合并两个链表, 并清空被合并的链表
• reverse 颠倒链表
• splice 在指定位置前面插入另一链表中的一个或多个元素,并在另一链表中删除被插入的元素

list之sort函数?

list容器的迭代器不支持完全随机访问,不能用标准库中sort函数对它进行排序.list自己的sort成员函数如下:
list classname
classname.sort(compare); //compare函数可以自己定义
classname.sort(); //无参数版本, 按<排序

p.s. list容器只能使用双向迭代器

deque?

双向队列.必须包含头文件 #include <deque>.所有适用于vector的操作,都适用于deque.deque还有 push_front (将元素插入到容器的头部)和 pop_front (删除头部的元素) 操作

3.45 STL之函数对象

何为函数对象?

若一个类重载了运算符 “()”,则该类的对象就成为函数对象

STL中的函数对象类模板?

greater 函数对象类模板
template
struct greater : public binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const {
return x > y;
}
};

略

3.46 STL之set、multiset

概述?

内部元素有序排列，新元素插入的位置取决于它的值，查找速度快.除了各容器都有的函数外，还支持以下成员函数

• find: 查找等于某个值 的元素(x小于y和y小于x同时不成立即为相等)
• lower_bound : 查找某个下界
• upper_bound : 查找某个上界
• equal_range : 同时查找上界和下界
• count :计算等于某个值的元素个数(x小于y和y小于x同时不成立即为相等)
• insert: 用以插入一个元素或一个区间

略

3.47 STL之map和multimap

概述?

multimap中的元素由 <关键字,值>组成，每个元素是一个pair对象，关键字就是first成员变量,其类型是Key

multimap 中允许多个元素的关键字相同。元素按照first成员变量从小到大排列，缺省情况下用 less<Key> 定义关键字的“小于”关系

3.48 STL之算法

STL算法分类?

• 不变序列算法、变值算法、删除算法、变序算法、排序算法、有序区间算法、数值算法

不变序列算法?

该类算法不会修改算法所作用的容器或对象.适用于顺序容器和关联容器.时间复杂度都是O(n)

• min 求两个对象中较小的(可自定义比较器)
• max 求两个对象中较大的(可自定义比较器)
• min_element 求区间中的最小值(可自定义比较器)
• max_element 求区间中的最大值(可自定义比较器)
• for_each 对区间中的每个元素都做某种操作
• count 计算区间中等于某值的元素个数
• count_if 计算区间中符合某种条件的元素个数
• find 在区间中查找等于某值的元素
• find_if 在区间中查找符合某条件的元素
• find_end 在区间中查找另一个区间最后一次出现的位置(可自定义比较器)
• find_first_of 在区间中查找第一个出现在另一个区间中的元素 (可自定义比较器)
• adjacent_find 在区间中寻找第一次出现连续两个相等元素的位置(可自定义比较器)
• search 在区间中查找另一个区间第一次出现的位置(可自定义比较器)
• search_n 在区间中查找第一次出现等于某值的连续n个元素(可自定义比较器)
• equal 判断两区间是否相等(可自定义比较器)
• mismatch 逐个比较两个区间的元素，返回第一次发生不相等的两个元素的位置(可自定义比较器)
• lexicographical_compare 按字典序比较两个区间的大小(可自定义比较器)

变值算法?

此类算法会修改源区间或目标区间元素的值.值被修改的那个区间, 不可以是属于关联容器的

• for_each 对区间中的每个元素都做某种操作
• copy 复制一个区间到别处
• copy_backward 复制一个区间到别处, 但目标区前是从后往前被修改的
• transform 将一个区间的元素变形后拷贝到另一个区间
• swap_ranges 交换两个区间内容
• fill 用某个值填充区间
• fill_n 用某个值替换区间中的n个元素
• generate 用某个操作的结果填充区间
• generate_n 用某个操作的结果替换区间中的n个元素
• replace 将区间中的某个值替换为另一个值
• replace_if 将区间中符合某种条件的值替换成另一个值
• replace_copy 将一个区间拷贝到另一个区间，拷贝时某个值要换成新值拷过去
• replace_copy_if 将一个区间拷贝到另一个区间，拷贝时符合某条件的值要换成新值拷过去

删除算法?

删除一个容器里的某些元素.删除算法不应作用于关联容器

• remove 删除区间中等于某个值的元素
• remove_if 删除区间中满足某种条件的元素
• remove_copy 拷贝区间到另一个区间. 等于某个值的元素不拷贝
• remove_copy_if 拷贝区间到另一个区间. 符合某种条件的元素不拷贝
• unique 删除区间中连续相等的元素, 只留下一个(可自定义比较器)
• unique_copy 拷贝区间到另一个区间. 连续相等的元素, 只拷贝第一个到目标区间 (可自定义比较器)

变序算法?

变序算法改变容器中元素的顺序,但是不改变元素的值,变序算法不适用于关联容器,算法复杂度都是O(n)的

• reverse 颠倒区间的前后次序
• reverse_copy 把一个区间颠倒后的结果拷贝到另一个区间，源区间不变
• rotate 将区间进行循环左移
• rotate_copy 将区间以首尾相接的形式进行旋转后的结果拷贝到另一个区间，源区间不变
• next_permutation 将区间改为下一个排列(可自定义比较器)
• prev_permutation 将区间改为上一个排列(可自定义比较器)
• random_shuffle 随机打乱区间内元素的顺序
• partition 把区间内满足某个条件的元素移到前面，不满足该条件的移到后面

排序算法?

比前面的变序算法复杂度更高, 一般是O(nlog(n)).排序算法需要随机访问迭代器的支持.不适用于关联容器和list

• sort 将区间从小到大排序(可自定义比较器)
• stable_sort 将区间从小到大排序并保持相等元素间的相对次序(可自定义比较器)
• partial_sort 对区间部分排序, 直到最小的n个元素就位(可自定义比较器)
• partial_sort_copy 将区间前n个元素的排序结果拷贝到别处源区间不变(可自定义比较器)
• nth_element 对区间部分排序, 使得第n小的元素(n从0开始算)就位, 而且比它小的都在它前面, 比它大的都在它后面(可自定义比较器)
• make_heap 使区间成为一个“堆”(可自定义比较器)
• push_heap 将元素加入一个是“堆”区间(可自定义比较器)
• pop_heap 从“堆”区间删除堆顶元素(可自定义比较器)
• sort_heap 将一个“堆”区间进行排序，排序结束后，该区间就是普通的有序区间，不再是 “堆”了(可自定义比较器)

有序区间算法?

要求所操作的区间是已经从小到大排好序的.需要随机访问迭代器的支持.有序区间算法不能用于关联容器和list

• binary_search 判断区间中是否包含某个元素
• includes 判断是否一个区间中的每个元素，都在另一个区间中
• lower_bound 查找最后一个不小于某值的元素的位置
• upper_bound 查找第一个大于某值的元素的位置
• equal_range 同时获取lower_bound和upper_bound
• merge 合并两个有序区间到第三个区间
• set_union 将两个有序区间的并拷贝到第三个区间
• set_intersection 将两个有序区间的交拷贝到第三个区间
• set_difference 将两个有序区间的差拷贝到第三个区间
• set_symmetric_difference 将两个有序区间的对称差拷贝到第三个区间
• inplace_merge 将两个连续的有序区间原地合并为一个有序区间