首页 > 代码库 > CPP之全面总结（上）
CPP之全面总结（上）
OOP之类和对象
1. this指针的引入
每个成员函数都有一个额外的隐含的形参，这个参数就是this指针，它指向调用对象的地址。默认情况下，this的类型是指向类类型非常量版本的常量指针。可以表示成如下伪代码形式：
/* 假设现在有一个类Sales_data，以及其非常量Sales_data类型对象，则该隐式的this指针可以写成如下伪代码形式 */Sales_data *const this = &total;
this指针一般用于解决重名问题和返回自身的值或者引用。例如：
struct A{ int a; void test(int a){ this->a = a; }};test函数的形参a和类成员a成名，根据就近原则，直接使用a，调用的是形参a，那么如何使用被屏蔽的成员a呢，这里就是采用this指针。
2. const成员函数
紧随参数列表之后的const关键字作用为：修改隐式this指针所指向的对象的类型，如下：
/* 假设现在有一个类Sales_data，以及Sales_data类型对象，则在const成员函数中隐式的this指针可以写成如下伪代码形式 */const Sales_data *const this = &total;
这里加const的含义是，这个函数不能修改本对象，其实就是函数体内不得对类的成员进行修改。const主要起到保护的作用。
注意以下几点：
a）非const对象可以调用const成员函数，也可以调用非const成员函数，但是const对象只能调用const成员函数。并且，非const对象优先调用非const成员函数。
b）const成员函数只可以返回本对象的常量引用，如下写法会报错：
Student &print(ostream &os) const{ os << id_ << " " << name_ << " " << age_ << endl; return *this;}报错提示：
clang下：error: binding of reference to type ‘Student‘ to a value of type ‘const Student‘ drops qualifiers
return *this;
g++下：error: invalid initialization of reference of type ‘Student&’ from e
return *this;
最后记住：构造函数不能为const。如果为const，怎么完成初始化工作？！
3. const成员函数和非const成员函数可以构成重载。
到此为止，构成函数重载的要素有：类的名称、函数名、函数形参表以及成员函数的const属性。事实上，函数签名就是由这几个部分构成。
在这里我们解释一个问题： 为什么C语言里面没有函数重载？ 因为在编译器编译C程序时会维护一张符号表，C语言在记载函数的时候就是简单的记录函数的名字，所以函数名就是C函数的唯一标识。当我们试图定义两个名字相同的函数时，就发生了重定义。
C++是怎么做的呢？ 很显然，对于普通函数，它的符号（唯一标识）是根据函数名和参数列表生成的，对于类的成员函数，还要加上类名和const属性，所以我们进行函数重载的时候，这些函数在符号表中的标识是不相同的。 C++正是通过这种机制实现了函数的重载。
注意：C++编译器生成函数符号的时候没有考虑返回值，这也是函数重载和返回值无关的原因。
4. 构造函数之构造函数初始值列表（constructor initialize list）
构造函数有一个特殊的地方，就是它可以包含一个构造函数初始化列表，如下：
Person(int id, const string &name, int age) :_id(id), _name(name), _age(age){}虽然以下形式，也完全可以达到目的：
Person(int id, const string &name, int age){ _id = id; _name = name; _age = age;}但两者是不同的。第一种形式带构造函数初始值列表，执行的是真正的初始化工作；而第二种形式，进行的是赋值操作。
注意，即使构造函数没有构造函数初始值列表（更确切的说是构造函数初始值列表为空），那么类中的成员变量将会执行默认初始化。因此在以下情况我们必须使用构造函数默认初始化列表：
a）const内置类型变量以及没有显示定义默认构造函数的const类类型变量（可以参考该博文合成的默认构造函数定义为delete的一种情况）
b）引用类型成员
c）没有默认构造函数的类类型变量
其本质是因为，const内置类型变量和引用类型必须初始化；而对于类类型对象，可以通过默认构造函数进行默认初始化（非const类类型对象只要有默认构造函数就可以默认初始化，而const类类型对象必须有显示定义的默认构造函数才可以执行默认初始化）
5. 类成员初始化的顺序是它们在类中声明的顺序，而不是初始化列表中列出的顺序
考虑下面的类：
class X { int i; int j;public: X(int val) : j(val), i(j) { }};我们的设想是这样的，用val初始化j，用j的值初始化i，然而这里初始化的次序是先i然后j。
记住：类成员初始化的顺序是它们在类中声明的顺序，而不是初始化列表中列出的顺序！
6. 析构函数
与构造函数一样，析构函数也是一种特殊的函数。构造函数在对象被创建时调用，析构函数则是在对象被销毁时被调用。构造函数与构造函数一样，同样没有返回值，并且析构函数没有任何参数。如下：
~Person(){ }需要引起注意的是：
a）对于类类型对象foo的析构函数只是在它生命期的最后一刻的回调罢了，管不了foo自己所占的内存，就像自己没法给自己收尸一样。
b）对于堆上的类类型对象：free 干的事情是释放内存。delete 干的事情是调用析构函数，然后释放内存，注意是delete释放的内存空间，而不是析构函数释放的。对于栈上的类类型对象，退出作用域时会自动调用析构函数，然后释放内存。
总结：对于栈上的类类型对象其实和内置类型变量一样，退出作用域后都是由系统自动释放内存的。实际上无论是栈空间，还是堆空间，内置类型对象和类类型对象销毁时的区别，在于类对象会在销毁前调用析构函数。
7. static成员
不用于普通的数据成员，static 数据成员独立于该类的任何一个对象而存在，每个static数据成员是与类关联，并不与该类的对象相关联。
正如类可以定义共享的 static 数据成员一样，类也可以定义 static 成员函数。static 成员函数没有 this 形参（因为static成员不属于任何一个对象），它可以直接访问所属类的 static 成员，但不能直接使用非 static 成员（因为没有this指针）。当我们在类的外部定义 static 成员时，无须重复指定 static 保留字，该保留字只出现在类定义体内部的声明处即可。
小结：
a）static 成员是类的组成部分但不是任何对象的组成部分，因此，static 成员函数没有 this 指针。
b）因为 static 成员不是任何对象的组成部分，所以 static 成员函数不能是const成员函数。因为，将成员函数声明为 const 就是承诺不会修改该函数所属的对象，而 static 成员不是任何对象的组成部分。
c）static 函数只能使用 static 成员，而不能直接调用普通成员（方法+数据成员），当然如果这样写，static void print(Test &t) 谁也挡不住其调用对象t的普通成员。
d）static 成员一般在类内声明，类外定义。注意，当我们在类的外部定义 static 成员时，无须重复指定 static 保留字，该保留字只出现在类定义体内部的声明处即可。
8. 友元
1. 必须先定义包含成员函数的类，才能将这个类的成员函数设置为另外一个类的友元。
2. 不必预先声明类和非成员函数来将它们设为友元。
#include <iostream>#include <string>#include <vector>using namespace std;class Test{ public: friend class Other; //声明某个类是Test的朋友 friend void bar(const Test &t); //声明某个函数是Test的朋友 private: int x_; int y_;};class Other{ public: void foo(Test &t) { t.x_ = 10; t.y_ = 20; }};void bar(const Test &t){ cout << t.x_ << endl;}int main(int argc, const char *argv[]){ Test t; return 0;}注意：友元关系是单向的，以上例子中Test并不是Other的朋友，因此Test不能访问Other的private成员。（tmd，这不就是在告诉我们，你的是我的，我的还是我的）。顺便黑一下C++：
C++ is a modern language where your parent can‘t touch your privates but your friends can.
多么痛的领悟。
STL之顺序容器
1. 顺序容器的初始化
顺序容器主要是vector和list，他们的初始化方式有以下五种：
1. 直接初始化一个空的容器
2. 用一个容器去初始化另一个容器
3. 指定容器的初始大小
4. 指定容器的初始大小和初始值
5. 用一对迭代器范围去初始化容器
第2种和第5种初始化方式的区别在于：第2种不仅要求容器类型相同，还要求容器元素类型完全一致，而第5种不要求容器相同，对于容器元素，要求能相互兼容即可。
指针可以当做迭代器，所以可以这样做：
#include <iostream>#include <string>#include <vector>using namespace std;int main(int argc, char **argv) { const size_t MAX_SIZE = 3; string arr[MAX_SIZE] = { "hello", "world", "foobar" }; vector<string> vec(arr, arr + MAX_SIZE); return 0;}注意，凡是传入迭代器作为指定范围的参数，可以使用指针代替。
2. 容器元素的类型约束
凡是放入vector中的元素，必须具备复制和赋值的能力，因为放入vector中的元素只是一份拷贝。下例会报错。
#include <iostream>#include <string>#include <vector>using namespace std;//Test不支持复制和赋值。所以不能放入vectorclass Test{ public: Test() {} private: //设为私有，禁用了Test的复制和赋值能力 Test(const Test &); //用于复制（拷贝构造函数） void operator=(const Test &); //用于赋值（赋值运算符）};int main(int argc, const char *argv[]){ vector<Test> vec; Test t; vec.push_back(t); return 0;}3. 特殊的迭代器成员 begin和end
有四个特殊的迭代器：
c.begin() //指向容器C的第一个元素
C.end() //指向最后一个元素的下一个位置
C.rbegin() //返回一个逆序迭代器，指向容器c的最后一个元素
C.rend() //返回一个逆序迭代器，指向容器c的第一个元素的前面的位置
分别去顺序迭代和逆序迭代容器，例如：
#include <iostream>#include <string>#include <vector>#include <list>using namespace std;int main(int argc, char **argv) { vector<string> vec; vec.push_back("beijing"); vec.push_back("shanghai"); vec.push_back("guangzhou"); vec.push_back("shenzhen"); for (vector<string>::iterator iter = vec.begin(); iter != vec.end(); ++iter) { cout << *iter << endl; } for (vector<string>::reverse_iterator iter = vec.rbegin(); iter != vec.rend(); ++iter) { cout << *iter << endl; } return 0;}/*output:beijingshanghaiguangzhoushenzhenshenzhenguangzhoushanghaibeijing*/4. 顺序容器的插入操作
1. vector没有push_front（vectoe内部实现是数组）。list有push_front。
2. 针对List
a）可以使用insert(p, t) 在指定位置元素之前添加元素，其中p是迭代器，t时元素的值
b）Insert(p, n, t) 在迭代器p指向的位置之前插入n个元素，初始值为t
c）Insert(p, b, e) 在迭代器p指向的位置之前插入迭代器b和迭代器e之间的元素
d）可是使用push_front 头插
5. 顺序容器的删除操作
1. 删第一个或最后一个元素
类似与插入元素，pop_front或者pop_back可以删除第一个或者最后一个元素
2. 删除容器的一个元素
与insert对应，删除采用的是erase操作，该操作有两个版本：删除由一个迭代器指向的元素，或者删除由一对迭代器标记的一段元素。删除元素需要接收返回值，防止迭代器失效，最好使用while循环。
6. 容器大小的操作
vector与容量有关的函数：
a）size 元素数目，类似于会议室中人的数目
b）resize 调整元素数目，类似于调整函数
c）capacity 可容纳数目，类似于会议室中的座位数量
d）reserve 告诉vector容器应该预留多少个元素的存储空间
7. 迭代器的失效问题
任何insert或者push操作都可能导致迭代器失效。当编写循环将元素插入到vector或list容器中时，程序必须确保迭代器在每次循环后都得到更新。
vector迭代器持续有效，除非：
1. 使用者在较小的索引位置插入或者删除元素。
2. 由于容量的变化引起的内存重新分配。
list迭代器持续有效，除非：
将it指向的元素删除，那么it则失效（list内部实现是链表，it指向的元素删了就是没有了，再用it访问直接段错误。vector也有可能失效，只不过后面的元素会往前移，再用it访问可能不会产生段错误）。
删除元素需要接收返回值，最好使用while循环。例如删除下例删除偶数：
vector<int>::iterator it = vec.begin();
while(it != vec.end()){ if(*it % 2 == 0) //vec.erase(it); it = vec.erase(it); else ++it;}8. vector的for_each方法
遍历vector方法：
1. 下标
2. 迭代器
3. for_each
#include <iostream>#include <string>#include <vector>#include <algorithm>using namespace std;void print(int i){ cout << i << endl;}int main(int argc, const char *argv[]){ vector<int> vec; vec.push_back(12); vec.push_back(23); vec.push_back(45); vec.push_back(56); vec.push_back(221); vec.push_back(35); vec.push_back(129); for_each(vec.begin(), vec.end(), print); return 0;}/*output:1223455622135129*/9. vector和list的区别
a) vector采用数组实现，list采用链表。
b) vector支持随机访问，list不提供下标。
c) 大量增加删除的操作适合使用list。
10. string之截取子串substr
例子如下：
#include <iostream>#include <string>#include <vector>using namespace std;int main(int argc, const char *argv[]){ string s = "helloworldfoo"; string s2 = s.substr(1, 4); //ello cout << s2 << endl; return 0;}注意，迭代器一般是取基地址到尾后地址的一段范围。而下标操作，通常是基地址+长度。
11. stack
#include <iostream>#include <string>#include <vector>#include <stack>using namespace std;int main(int argc, const char *argv[]){ stack<int> s; s.push(10); s.push(22); s.push(23); s.push(1); s.push(8); s.push(99); s.push(14); while(!s.top() << endl; s.pop(); } return 0;}/* 输出如下：149981232210*/12. queue
#include <iostream>#include <string>#include <vector>#include <queue>using namespace std;int main(int argc, const char *argv[]){ queue<int> q; q.push(12); q.push(23); q.push(4); q.push(5); q.push(7); while(!q.front() << endl; q.pop(); } return 0;}/*输出：1223457*/13. 优先级队列（用堆实现）
例1：
#include <iostream>#include <string>#include <vector>#include <queue>using namespace std;int main(int argc, const char *argv[]){ priority_queue<int> q; q.push(12); q.push(99); q.push(23); q.push(123); while(!q.top() << endl; q.pop(); } return 0;}/*output：123992312*/例2：
#include <iostream>#include <string>#include <vector>#include <queue>using namespace std;int main(int argc, const char *argv[]){ priority_queue<int, int>, greater<int> > q; q.push(12); q.push(99); q.push(23); q.push(123); while(!q.empty()) { cout << q.top() << endl; q.pop(); } return 0;}/*output:122399123*/#include <iostream>#include <string>#include <vector>#include <queue>using namespace std;int main(int argc, const char *argv[]){ priority_queue<int, int>, less<int> > q; q.push(12); q.push(99); q.push(23); q.push(123); while(!q.empty()) { cout << q.top() << endl; q.pop(); } return 0;}/*output:123992312*/例3：传入函数对象
#include <iostream>#include <string>#include <vector>#include <queue>using namespace std;struct Score{ int score_; string name_; Score(int score, const string name) :score_(score), name_(name) { }};class Cmp{ public: bool operator() (const Score &s1, const Score &s2) { return s1.score_ < s2.score_; }};// Cmp p;// p(s1, s2)int main(int argc, const char *argv[]){ priority_queue<Score, vector<Score>, Cmp> q; q.push(Score(67, "zhangsan")); q.push(Score(88, "lisi")); q.push(Score(34, "wangwu")); q.push(Score(99, "foo")); q.push(Score(0, "bar")); while(!q.empty()) { cout << q.top().name_ << " : " << q.top().score_ << endl; q.pop(); } return 0;}/*output:foo : 99lisi : 88zhangsan : 67wangwu : 34bar : 0*/14. reverse迭代器
反向迭代器逻辑上指向的元素是物理上指向元素的下一个元素。
在实际（物理）实现上，rbegin()指向最后一个元素的下一个位置，rend()指向第一个元素。但是在逻辑上，rbegin()指向最后一个元素，rend()指向第一个元素的前一个位置。
注意：reverse迭代器不能用于erase函数。删除的正确方式是：it = string::reverse_iterator(s.erase((++it).base()));（见示例3）
示例1：
#include <iostream>#include <vector>#include <algorithm>using namespace std;int main(int argc, const char *argv[]){ vector<int> coll; for (int i = 0; i <= 9 ; i++) // 0 1 2 3 4 5 6 7 8 9 { coll.push_back(i); } vector<int>::iterator pos; pos = find(coll.begin(), coll.end(), 5); // 此时pos物理指向的元素就是5 cout << "pos: " << *pos << endl; // 输出5 vector<int>::reverse_iterator rpos(pos); // 反向迭代器物理上指向的元素确实是5 cout << "rpos: " << *rpos << endl; // 但是逻辑上指向的元素是它的下一个元素，在此处即为4 }/*output:pos: 5rpos: 4*/示例2：
#include <iostream>#include <vector>#include <algorithm>using namespace std;void print(int i){ cout << i << " ";}int main(int argc, const char *argv[]){ vector<int> coll; for (int i = 0; i <= 9 ; i++) // 0 1 2 3 4 5 6 7 8 9 { coll.push_back(i); } vector<int>::iterator pos1; pos1 = find(coll.begin(), coll.end(), 2); // pos1指向2 vector<int>::iterator pos2; pos2 = find(coll.begin(), coll.end(), 7); // pos2指向7 for_each(pos1, pos2, print); // 输出2 3 4 5 6 cout << endl; vector<int>::reverse_iterator rpos1(pos1); // rpos1物理指向2，逻辑指向1 vector<int>::reverse_iterator rpos2(pos2); // rpos2物理指向7，逻辑指向6 for_each(rpos2, rpos1, print); // 输出6 5 4 3 2 cout << endl;}/*output:2 3 4 5 66 5 4 3 2*/示例3：
#include <iostream>#include <string>#include <vector>using namespace std;int main(int argc, const char *argv[]){ string s = "helloworld"; string::reverse_iterator it = s.rbegin(); // s.rbegin物理指向的元素最后一个元素之后的位置，逻辑指向的是最后一个元素 while(it != s.rend()) { if(*it == ‘r‘) { string::iterator tmp = (++it).base(); // 由于earse()参数不能是删除反向迭代器，因此需要将其转换为正向迭代器 tmp = s.erase(tmp); // 而it此时物理指向的元素并不是‘r‘，++it后才物理指向‘r’，此时经base()转换为正向迭代器后删除 it = string::reverse_iterator(tmp); // 之后将正向迭代器转换成反向迭代器 //it = string::reverse_iterator(s.erase((++it).base())); } else ++it; } cout << s << endl;}/*output:hellowold*/STL之关联容器
1. Pair类型
Pair是一种简单的关联类型。注意：pair不是容器，而是代表一个key-value键值对。
示例1:
#include <iostream>#include <string>#include <utility>using namespace std;int main(int argc, const char *argv[]){ int, int> p1; p1.first = 10; p1.second = 12;int, string> p2; p2.first = 12; p2.second = "hello"; pair<string, string> p3;}
示例2：#include <iostream>#include <string>#include <vector>using namespace std;//生成pair对象的三种方法int main(int argc, const char *argv[]){ vector<pair<string, int> > vec; pair<string, int> word; word.first = "hello"; word.second = 12; vec.push_back(word); pair<string, int> word2("world", 12); vec.push_back(word2); vec.push_back(make_pair("foo", 3));}示例3：vector中装入pair，实现统计词频：
#include <iostream>#include <string>#include <vector>#include <utility>using namespace std;string, int> > Dict;void makeDict(Dict &dict, const vector<string> &words);void addWordToDict(Dict &dict, const string &word);int main(int argc, const char *argv[]){ vector<string> words; string word; while(cin >> word) words.push_back(word); Dict dict; makeDict(dict, words); for(const pair<string, int> &p : dict) { cout << p.first << " : " << p.second << endl; } return 0;}void makeDict(Dict &dict, const vector<string> &words){ dict.clear(); for(vector<string>::const_iterator it = words.begin(); it != words.end(); ++it) { addWordToDict(dict, *it); }}void addWordToDict(Dict &dict, const string &word){ Dict::iterator it; for(it = dict.begin(); it != dict.end(); ++it) { if(it->first == word) { ++it->second; break; } } if(it == dict.end()) dict.push_back(make_pair(word, 1));}
2. map
map可以看做是一种存储pair类型的容器，内部采用二叉树实现（编译器实现为红黑树）。
1. pair不是容器，而是代表一个key-value键值对；而map则是一个容器，里面存储了pair对象，只是存储的方式与vector<pair>这种连续存储，有所不同，map采用的是二叉排序树存储pair，一般而言是红黑树，因此内部是有序的
2. 当map使用下标访问时，如果key不存在，那么会在map中添加一个新的pair，value为默认值
示例1：
#include <iostream>#include <string>#include <map>using namespace std;int main(int argc, const char *argv[]){ map<string, int> m; m["beijing"] = 2000; m["shenzhen"] = 1000; m["shanghai"] = 1500; m["hongkong"] = 500; m["hangzhou"] = 880; for(map<string, int>::const_iterator it = m.begin(); it != m.end(); ++it) { //*it pair cout << it->first << " : " << it->second << endl; } return 0;}/*output:beijing : 2000hangzhou : 880hongkong : 500shanghai : 1500shenzhen : 1000*/// 由于key是string类型，因此输出按字典序。
示例2：
#include <iostream>#include <string>#include <vector>#include <map>using namespace std;int main(int argc, const char *argv[]){ map<string, int> m; m["beijing"] = 40; m["shenzhen"] = 30; m["guangzhou"] = 37; cout << m.size() << endl; //3 cout << m["shanghai"] << endl; cout << m.size() << endl; return 0;}/*output:304*/3. map 的 key 必须具有小于操作符 operator <
以下为错误代码：
#include <iostream>#include <map>using namespace std;struct Test{ int a;};int main(int argc, const char *argv[]){ map<Test, int> m; Test t; m[t] = 1;}/* 编译报错，因为Test对象在次数为key-value对中的key，但其并没有定义 operator< 运算符，红黑树无法进行排序 */4. map查找元素的效率是lgn，因为树的高度不超过O(lgN)
示例：使用map，实现统计词频，如下：
#include <iostream>#include <string>#include <vector>#include <map>using namespace std;int main(int argc, const char *argv[]){ map<string, int> words; string word; /* 如果key（word）存在，则value++； 如果word不存在，此处会在map（words）中添加一个新的pair，value为默认值（此处为0），然后value++ */ while(cin >> word) words[word]++; for(const pair<string, int> &p : words) cout << p.first << " : " << p.second << endl; return 0;}5. 在map中添加元素
刚才我们看到，采用下标的方式，可以给map添加元素，但更好的做法时采用insert插入一个pair对象。
这里值得注意的是insert的返回值，其返回了一个pair对象，第一个元素是指向该key所在的那个pair对象的的迭代器，第二个则表示插入是否成功。使用insert插入map元素时，如果失败，则不会更新原来的值。看下面例子：
#include <iostream>#include <string>#include <vector>#include <map>using namespace std;int main(int argc, const char *argv[]){ map<string, int> m; m.insert(make_pair("hello", 1)); m.insert(make_pair("foo", 1)); m.insert(make_pair("bar", 1)); m.insert(make_pair("hello", 1)); cout << "size : " << m.size() << endl; /* insert的返回值：指向key所在pair的迭代器，以及表示插入是否成功的布尔值 */ pair<map<string, int>::iterator, bool> ret; // 之前没有这个key，插入成功 ret = m.insert(make_pair("fwfgwfg", 23)); cout << "ret = " << ret.second << endl; // 之前已有的key，插入失败。插入失败的话，不会更新原来的value值 ret = m.insert(make_pair("hello", 25425)); cout << "ret = " << ret.second << endl; cout << ret.first->second << endl; return 0;}/*output:size : 3 ret = 1 ret = 01*/下面的程序仍然是实现统计词频：
#include <iostream>#include <string>#include <map>using namespace std;int main(int argc, const char *argv[]){ map<string, int> words; string word; pair<map<string, int>::iterator, bool> ret; while(cin >> word) { ret = words.insert(make_pair(word, 1)); if(ret.second == false) //word已经存在 ++ret.first->second; } for(const pair<string, int> &p : words) cout << p.first << " : " << p.second << endl; return 0;}综上，在本章中我们已经使用三种方式，去统计词频了，分别是：vector中使用pair， map的下标访问方式以及map的insert方式。
6. 在map中查找元素
刚才看到可以利用下标获取value的值，但是这样存在一个弊端，如果下标访问的是不存在的元素，那么会自动给map增加一个键值对，这显然不是我们所预期的。
我们可以采用 count 和 find 来解决问题，其中 count 仅仅能得出该元素是否存在，而 find 能够返回该元素的迭代器。
示例1：
#include <iostream>#include <string>#include <map>using namespace std;int main(int argc, const char *argv[]){ map<string, string> m; m["beijing"] = "bad"; m["shanghai"] = "just soso"; m["shenzhen"] = "well"; m["hangzhou"] = "good"; cout << m.count("hangzhou") << endl; cout << m.count("HK") << endl; return 0;}/*output:10*/示例2：
#include <iostream>#include <string>#include <map>using namespace std;int main(int argc, const char *argv[]){ map<string, string> m; m["beijing"] = "bad"; m["shanghai"] = "just soso"; m["shenzhen"] = "well"; m["hangzhou"] = "good"; // find的返回值 map<string, string>::iterator it = m.find("HK"); if(it == m.end()) cout << "不存在" << endl; else cout << it->first << " : " << it->second << endl; return 0;}/*output:不存在*/3. set
Set类似于数学上的集合，仅仅表示某个元素在集合中是否存在，而不必关心它的具体位置。同样，set中的元素互异，也就是无法两次插入相同的元素。set 底层采用红黑树实现，按照值进行排序，map则按照key进行排序。使用方式和map类似，但是简单很多。
示例1：
#include <iostream>#include <string>#include <set>using namespace std;int main(int argc, const char *argv[]){ set<int> s; // set不会插入重复的元素 for(int i = 0; i < 20 ; ++i) { s.insert(i); s.insert(i); } cout << "size : " << s.size() << endl; return 0;}/*output:size : 20*/示例2：
#include <iostream>#include <string>#include <vector>#include <set>#include <stdlib.h>using namespace std;int main(int argc, const char *argv[]){ srand(10000); set<int> s; for(int i = 0; i < 40; ++i) { s.insert(rand() % 100); } // 注意是有序的 for(int i : s) { cout << i << " "; } cout << endl; return 0;}/*output:4 5 8 12 13 15 16 20 21 22 24 25 27 32 38 39 42 43 46 50 54 57 59 63 66 72 78 82 85 93 94 96 98*/4. 小结
map 中key 的值是唯一的，set 中的元素都是唯一的。
1. map和set比较：
a) 二者均使用红黑树实现
b) key需要支持<操作
c) map侧重于key-value的快速查找
d) set侧重于查看元素是否存在
2. 用户无法对map和set中的元素进行排序，不然会干扰map和set本身的实现。
最后注意：map 的 key 值是不可更改的。而 set 中的 value 虽然可以更改，但不建议这样做，真有需求，直接删除即可。
5. 哈希
c++11标准添加了 std::unordered_map 与 std::unordered_map。
map采用二叉树实现，hash_map采用hash表，那么二者的使用上：
a) 当key本身需要排序时，使用map
b) 其他情况采用hash_map更佳（hash_map无序），但是采用map效率也是足够的。
#include <iostream>#include <string>#include <vector>#include <unordered_map>using namespace std;int main(int argc, const char *argv[]){ unordered_map<string, int> m; m["beijing"] = 1; m["shanghai"] = 2; m["shenzhen"] = 3; for(unordered_map<string, int>::const_iterator it = m.begin(); it != m.end(); ++it) { cout << it->first << " : " << it->second << endl; }}/*output:shenzhen : 3shanghai : 2beijing : 1*/STL 算法
以下只是对小部分常用算法进行了介绍，但具体用法大同小异。
1. for_each
template <class InputIterator, class Function> Function for_each (InputIterator first, InputIterator last, Function fn);Apply function to range
Applies function fn to each of the elements in the range
[first,last).
#include <iostream>#include <string>#include <vector>#include <list>#include <algorithm>#include <ctype.h>using namespace std;void toUpper(string &s){ for(string::iterator it = s.begin(); it != s.end(); ++it) { if(islower(*it)) *it = toupper(*it); }}void print(const string &s){ cout << s << " ";}int main(int argc, const char *argv[]){ vector<string> vec; vec.push_back("beijing"); vec.push_back("changchun"); vec.push_back("shijiahzuang"); vec.push_back("shenyang"); vec.push_back("dalian"); vec.push_back("jinan"); vec.push_back("nanjing"); for_each(vec.begin(), vec.end(), toUpper); for_each(vec.begin(), vec.end(), print);}/*output:BEIJING CHANGCHUN SHIJIAHZUANG SHENYANG DALIAN JINAN NANJING*/2. count && count_if
count
template <class InputIterator, class T> typename iterator_traits<InputIterator>::difference_type count (InputIterator first, InputIterator last, const T& val);Count appearances of value in range
Returns the number of elements in the range
[first,last)that compare equal to val.
The function usesoperator==to compare the individual elements to val.
示例：
#include <iostream>#include <vector>#include <algorithm>using namespace std;int main(int argc, const char *argv[]){ int myints[] = {10,20,30,30,20,10,10,20}; int mycount = count(myints, myints+8, 10); cout << "10 appears " << mycount << " times." << endl; vector<int> myvector(myints, myints+8); mycount = count(myvector.begin(), myvector.end(), 20); cout << "20 appears " << mycount << " times." << endl;}/*output:10 appears 3 times.20 appears 3 times.*/count_if
template <class InputIterator, class Predicate> typename iterator_traits<InputIterator>::difference_type count_if (InputIterator first, InputIterator last, UnaryPredicate pred);Return number of elements in range satisfying condition
Returns the number of elements in the range
[first,last)for which pred is true.
示例：
/* count_if example */#include <iostream>#include <vector>#include <algorithm>using namespace std;bool IsOdd(int i){ return i % 2 == 1;}int main(int argc, const char *argv[]){ vector<int> vec; for(int i = 1; i < 10; ++i) { vec.push_back(i); //vec: 1 2 3 4 5 6 7 8 9 } int mycount = count_if(vec.begin(), vec.end(), IsOdd); cout << "vec contains " << mycount << " odd values." << endl;}/*output:vec contains 5 odd values.*/3. min_element
default (1)
template <class ForwardIterator> ForwardIterator min_element (ForwardIterator first, ForwardIterator last);custom (2)
template <class ForwardIterator, class Compare> ForwardIterator min_element (ForwardIterator first, ForwardIterator last, Compare comp);Return smallest element in range
Returns an iterator pointing to the element with the smallest value in the range
[first,last).The comparisons are performed using either
operator<for the first version, or comp for the second; An element is the smallest if no other element compares less than it. If more than one element fulfills this condition, the iterator returned points to the first of such elements.
示例：
// min_element/max_element example#include <iostream> // std::cout#include <algorithm> // std::min_element, std::max_elementbool myfn(int i, int j) { return i<j; }struct myclass { bool operator() (int i,int j) { return i<j; }} myobj;int main () { int myints[] = {3,7,2,5,6,4,9}; // using default comparison: std::cout << "The smallest element is " << *std::min_element(myints,myints+7) << ‘\n‘; std::cout << "The largest element is " << *std::max_element(myints,myints+7) << ‘\n‘; // using function myfn as comp: std::cout << "The smallest element is " << *std::min_element(myints,myints+7,myfn) << ‘\n‘; std::cout << "The largest element is " << *std::max_element(myints,myints+7,myfn) << ‘\n‘; // using object myobj as comp: std::cout << "The smallest element is " << *std::min_element(myints,myints+7,myobj) << ‘\n‘; std::cout << "The largest element is " << *std::max_element(myints,myints+7,myobj) << ‘\n‘; return 0;}/*output:The smallest element is 2The largest element is 9The smallest element is 2The largest element is 9The smallest element is 2The largest element is 9*/4. find && find_if
find
template <class InputIterator, class T> InputIterator find (InputIterator first, InputIterator last, const T& val);Find value in range
Returns an iterator to the first element in the range
[first,last)that compares equal to val. If no such element is found, the function returns last.The function uses
operator==to compare the individual elements to val.
find_if
template <class InputIterator, class UnaryPredicate> InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred);Find element in range
Returns an iterator to the first element in the range
[first,last)for which pred returnstrue. If no such element is found, the function returns last.
示例：
#include <iostream>#include <string>#include <vector>#include <list>#include <algorithm>#include <ctype.h>using namespace std;void print(const string &s){ cout << s << " ";}bool isShorter(const string &s){ return s.size() < 6;}int main(int argc, const char *argv[]){ vector<string> vec; vec.push_back("beijing"); vec.push_back("changchun"); vec.push_back("shijiahzuang"); vec.push_back("shenyang"); vec.push_back("dalian"); vec.push_back("jinan"); vec.push_back("nanjing"); vector<string>::iterator it = std::find(vec.begin(), vec.end(), "dalian"); cout << *it << endl; //find_if it = std::find_if(vec.begin(), vec.end(), isShorter); cout << *it << endl;}/*output:dalianjinan*/5. copy
template <class InputIterator, class OutputIterator> OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result);Copy range of elements
Copies the elements in the range
[first,last)into the range beginning at result.The function returns an iterator to the end of the destination range (which points to the element following the last element copied).
The ranges shall not overlap in such a way that result points to an element in the range [first,last). For such cases, seecopy_backward.
示例（注意插入迭代器的用法）：
#include <iostream>#include <string>#include <vector>#include <list>#include <algorithm>#include <ctype.h>using namespace std;void print(const string &s){ cout << s << " ";}int main(int argc, const char *argv[]){ vector<string> vec; vec.push_back("beijing"); vec.push_back("changchun"); vec.push_back("shijiahzuang"); vec.push_back("shenyang"); vec.push_back("dalian"); vec.push_back("jinan"); vec.push_back("nanjing"); list<string> lst; std::copy(vec.begin(), vec.end(), back_inserter(lst)); //执行的是push_back。如果填写lst.begin()，需要list<string> lst(7); for_each(lst.begin(), lst.end(), print); cout << endl; lst.clear(); std::copy(vec.begin(), vec.end(), front_inserter(lst)); //执行的是push_front。如果填写lst.rbegin()，需要list<string> lst(7); for_each(lst.begin(), lst.end(), print); cout << endl; return 0;}/*output:beijing changchun shijiahzuang shenyang dalian jinan nanjingnanjing jinan dalian shenyang shijiahzuang changchun beijing*/6. lambda 表达式
c++11中新增了lambda表达式。
简单来说，编程中提到的 lambda 表达式，通常是在需要一个函数，但是又不想费神去命名一个函数的场合下使用，也就是指匿名函数。
示例：
#include <iostream>#include <string>#include <vector>#include <algorithm>#include <ctype.h>using namespace std;void toUpper(string &s){ for(string::iterator it = s.begin(); it != s.end(); ++it) { if(islower(*it)) *it = toupper(*it); }}void print(const string &s){ cout << s << " ";}int main(int argc, const char *argv[]){ vector<string> vec; vec.push_back("beijing"); vec.push_back("changchun"); vec.push_back("shijiahzuang"); vec.push_back("shenyang"); vec.push_back("dalian"); vec.push_back("jinan"); vec.push_back("nanjing"); for_each(vec.begin(), vec.end(), toUpper); for_each(vec.begin(), vec.end(), " "; } );}/*output:BEIJING CHANGCHUN SHIJIAHZUANG SHENYANG DALIAN JINAN NANJING */OOP之复制控制
1. 对象复制的时机：
a）根据一个类去显式或者隐式初始化一个对象
b）复制一个对象，将它作为实参传给一个函数
c）从函数返回时复制一个对象
那么如何完成对象复制的工作？这里需要的就是拷贝构造函数。
2. 拷贝构造函数（也叫复制构造函数）
只有单个形参，而且该形参是本类类型对象的引用（常用const修饰），这样的构造函数成为复制控制函数。
复制构造函数调用的时机就是在对象复制的时候。
如果什么也不做，编译器会自动帮我们合成一个默认的复制构造函数。
那么如果我们自己来定义复制构造函数，应该怎么写？示例如下：
#include <iostream>#include <string>#include <vector>using namespace std;class Student{ public: Student() {} Student(int id, const string &name, int age) :id_(id), name_(name), age_(age) { } Student(const Student &other) :id_(other.id_), name_(other.name_), age_(other.age_) { } void print() const { cout << id_ << " : " << name_ << " : " << age_; } private: int id_; string name_; int age_;};int main(int argc, const char *argv[]){ Student s(11, "zhangsan", 23); s.print(); cout << endl; Student s2(s); // 调用拷贝构造函数 s2.print(); cout << endl;}/*output:11 : zhangsan : 2311 : zhangsan : 23*/现在来思考一个问题，既然编译器生成的拷贝构造函数工作正常，那么什么时候需要我们自己来编写拷贝构造函数呢？这就是下面的深拷贝和浅拷贝的问题。
3. 深拷贝和浅拷贝
我们通过自己定义的string类来解释深拷贝与浅拷贝的问题。先来看以下这个错误版本的string类：
_string.h
#ifndef _STRING_H_#define _STRING_H_ #include <stddef.h>namespace __str{ class string { public: string(); string(const char*); void debug() const; size_t size() const; ~string(); private: char *_str; };} /* namespace __str */ #endif /*_STRING_H_*/_string.cpp#include "_string.h"#include <iostream>#include <string.h>using namespace std;namespace __str{ string::string() :_str(new char[1]) { _str[0] = 0; } string::string(const char *s) :_str(new char[strlen(s) + 1]) { strcpy(_str, s); } size_t string::size() const { return strlen(_str); } void string::debug() const { cout << _str << endl; } string::~string() { delete []_str; }} /* namespace __str */
main.cpp
#include "_string.h"using namespace __str;int main(int argc, const char *argv[]){ string s("hello"); // 调用一个参数的构造函数 s.debug(); string s2(s); // 调用系统合成的拷贝构造函数 s2.debug();}
程序运行后，输出两次 hello，直接直接挂掉。为什么会这样子呢？
因为系统合成的拷贝构造函数，在复制String对象时，只是简单的复制其中的_str的值，这样复制完毕后，就有两个String中的_str指向同一个内存区域，当对象析构时，发生两次delete，导致程序错误
如何解决？
方案很简单，就是我们在复制String时，不去复制str的值，而是复制其指向的内存区域。
我们自定义拷贝构造函数如下：
string::string(const String &s) :str_(new char[strlen(s.str_) + 1]){ strcpy(str_, s.str_); }如此程序就可以正常运行，输出两次hello。
含有指针成员变量的类在复制时，有两种选择：
a) 复制指针的值，这样复制完毕后，两个对象指向同一块资源，这叫做浅拷贝 shallow copy
b) 复制指针所指向的资源，复制完毕后，两个对象各自拥有自己的资源，这叫做深拷贝 deep copy
注意：编译器默认的是浅拷贝，此时如果需要深拷贝，需要自己编写拷贝构造函数。
4. 赋值运算符
前面的复制构造函数说的是对象的复制，对象的赋值调用的则是对象的赋值运算符。
对于我们自定义的类（例如Student），我们是无法进行比较操作的，因为我们自定义的类没有内置比较运算符（<= < > >= == !=），此时我们就可以通过运算符重载的规则给这些类加上运算符，这里我们需要重载的就是赋值运算符。
当然，如果我们什么也不做，系统也会自动合成一个赋值运算符，但是什么时候需要我们自己来重载赋值运算符呢，仍然是考虑深拷贝和浅拷贝的问题。
对于刚刚我们自定义的string类这个例子而言，如果我们使用系统自动合成的赋值运算符，那么同样会引起错误。因为当发生赋值时，两个string对象的_str仍然会指向同一片内存空间，那么当程序退出时，会析构两次，发生错误。
因此，我们应该自己来定义string类的赋值运算符，如下：
string& string::operator=(const string &s)// 自定义赋值运算符{ // 防止自赋值，这样执行delete的时候，会冲掉原有内容 if(this == &s) { return *this; } // 释放原来指向的内存空间 delete []_str;
_str = new char[strlen(s._str) + 1]; strcpy(_str, s._str); return *this;}
注意：赋值操作符，需要先释放掉以前持有的资源，同时必须处理自赋值的问题。
5. 禁止类的复制和赋值
如果想禁止复制一个类，应该怎么办？
显然需要把类的复制构造函数设为private，但是这样以来类的friend仍然可以复制该类，于是我们只声明这个函数，而不去实现。另外，如果你不需要复制该类的对象，最好把赋值运算也一并禁用掉。
所以这里的做法是：把复制构造函数和赋值运算符的声明设为private而不去实现。
注意：如果一个类，不需要复制和赋值，那就禁用这种能力，这可以帮助避免大量潜在的bug。
示例：
class Test{ public: Test() {} ~Test() {} private: Test(const Test &t); void operator=(const Test &t);};实际上，更通用的做法是写一个类noncopyable，凡是继承该类的任何类都无法复制和赋值。
而google开源项目风格指南建议的做法是使用 DISALLOW_COPY_AND_ASSIGN 宏:
// 禁止使用拷贝构造函数和 operator= 赋值操作的宏// 应该类的 private: 中使用#define DISALLOW_COPY_AND_ASSIGN(TypeName) TypeName(const TypeName&); void operator=(const TypeName&)
在 class foo 中使用方式如下:class Foo { public: Foo(int f); ~Foo(); private: DISALLOW_COPY_AND_ASSIGN(Foo);};绝大多数情况下都应使用 DISALLOW_COPY_AND_ASSIGN 宏。如果类确实需要可拷贝，应在该类的头文件中说明原由，并合理的定义拷贝构造函数和赋值操作。注意在 operator= 中检测自我赋值的情况。为了能作为 STL 容器的值，你可能有使类可拷贝的冲动。在大多数类似的情况下，真正该做的是把对象的指针放到 STL 容器中。可以考虑使用智能指针。
6. 小结
1. 复制构造函数、赋值运算符以及析构函数，称为三法则，一旦提供了其中一个，务必提供其余两个。以我们之前自定义的string类为例：
a) 涉及到深拷贝、浅拷贝问题，所以需要提供拷贝构造函数
b) 然后，为了保持一致，赋值运算符也应该实现深拷贝
c) 既然实现深拷贝，那么必定申请了资源（例如内存），所以必然需要析构函数来手工释放。
2. 一个空类，编译器提供默认无参数构造函数、拷贝构造函数、赋值运算符以及析构函数，一共四个函数（针对03标准，c++11中还有移动构造函数和移动赋值运算符）。
3. 对于复制和赋值，请务必保证在程序的语义上具有一致性。
4. 如果一个类，实现了像value一样的复制和赋值能力（意味着复制和赋值后，两个对象没有任何关联，或者逻辑上看起来无任何关联），那么就称这个类的对象为值语义（value semantics）。如果类不能复制，或者复制后对象之间的资源归属纠缠不清，那么称为对象语义（object semantics），或者引用语义（reference semantics）。
CPP之全面总结（上）