3.1 string容器
3.1.1 string容器基本概念
C风格字符串(以空字符结尾的字符数组)太过复杂难于掌握，不适合大程序的开发，所以C++标准库定义了一种string类，定义在头文件<string>。
String和c风格字符串对比：
1.Char*是一个指针，String是一个类
string封装了char*，管理这个字符串，是一个char*型的容器。
2.String封装了很多实用的成员方法
查找find，拷贝copy，删除delete 替换replace，插入insert
3.不用考虑内存释放和越界
string管理char*所分配的内存。每一次string的复制，取值都由string类负责维护，不用担心复制越界和取值越界等。
3.1.2 string容器常用操作
3.1.2.1 string 构造函数
string(); //创建一个空的字符串 例如: string str; string(const string& str); //使用一个string对象初始化另一个string对象 string(const char* s); //使用字符串s初始化 string(int n, char c); //使用n个字符c初始化 |
void test()
{
string str01;
string str02(str01);
string str03 = "abc";
string str04(10, 'a');
cout << str01 << endl;
cout << str02 << endl;
cout << str03 << endl;
cout << str04 << endl;
}
int main()
{
test();
return 0;
}输出结果
abc
aaaaaaaaaa3.1.2.2 string基本赋值操作
string& operator=(const char* s); //char*类型字符串 赋值给当前的字符串 string& operator=(const string &s); //把字符串s赋给当前的字符串 string& operator=(char c); //字符赋值给当前的字符串 string& assign(const char *s); //把字符串s赋给当前的字符串 string& assign(const char *s, int n); //把字符串s的前n个字符赋给当前的字符串 string& assign(const string &s); //把字符串s赋给当前字符串 string& assign(int n, char c); //用n个字符c赋给当前字符串 string& assign(const string &s, int start, int n); //将s从start开始n个字符赋值给字符串 |
void test()
{
string str01;
str01.assign("abcde", 3);
cout << str01 << endl;
string str02;
str02.assign(str01);
cout << str02 << endl;
string str03;
//将s从0开始2个字符赋值给字符串
str03.assign(str01, 0, 2);
cout << str03 << endl;
}
int main()
{
test();
return 0;
}输出结果
abc
abc
ab3.1.2.3 string存取字符操作
char& operator[](int n); //通过[]方式取字符 char& at(int n); //通过at方法获取字符 |
void test()
{
string str = "hello world";
for (int i = 0; i < str.size(); i++)
{
cout << str[i] << " ";
}
cout << endl;
for (int i = 0; i < str.size(); i++)
{
cout << str.at(i) << " ";
}
cout << endl;
//[]和at区别，[]访问越界 直接挂掉， at访问越界 抛出out_of_range异常
try
{
cout << str.at(100) << endl;
}
catch (out_of_range& e)
{
cout << e.what() << endl;
}
catch (...)
{
cout << "异常捕获" << endl;
}
}
int main()
{
test();
return 0;
}输出结果
h e l l o w o r l d
h e l l o w o r l d
invalid string position3.1.2.4 string拼接操作
string& operator+=(const string& str); //重载+=操作符 string& operator+=(const char* str); //重载+=操作符 string& operator+=(const char c); //重载+=操作符 string& append(const char *s); //把字符串s连接到当前字符串结尾 string& append(const char *s, int n); //把字符串s的前n个字符连接到当前字符串结尾 string& append(const string &s); //同operator+=() string& append(const string &s, int pos, int n); //把字符串s中从pos开始的n个字符连接到当前字符串结尾 string& append(int n, char c); //在当前字符串结尾添加n个字符c |
void test()
{
//拼接
string str01 = "我";
string str02 = "爱北京";
string str03 = str01 + str02;
cout << str03 << endl;
//查找
string str04 = "abcdef";
int pos = str04.find("abc");
if (pos == -1)
{
cout << "未找到字符串" << endl;
}
else
{
cout << "找到了字符串，起始位置为：" << pos << endl;
}
//替换
string str05 = "hello world";
//替换从pos开始n个字符为字符串str
str05.replace(6, 5, "C/Cpp");
cout << str05 << endl;
}
int main()
{
test();
return 0;
}输出结果
我爱北京
3.1.2.5 string查找和替换
int find(const string& str, int pos = 0) const; //查找str第一次出现位置,从pos开始查找 int find(const char* s, int pos = 0) const; //查找s第一次出现位置,从pos开始查找 int find(const char* s, int pos, int n) const; //从pos位置查找s的前n个字符第一次位置 int find(const char c, int pos = 0) const; //查找字符c第一次出现位置 int rfind(const string& str, int pos = npos) const;//查找str最后一次位置,从pos开始查找 int rfind(const char* s, int pos = npos) const;//查找s最后一次出现位置,从pos开始查找 int rfind(const char* s, int pos, int n) const; //从pos查找s的前n个字符最后一次位置 int rfind(const char c, int pos = 0) const; //查找字符c最后一次出现位置 string& replace(int pos, int n, const string& str); //替换从pos开始n个字符为字符串str string& replace(int pos, int n, const char* s); //替换从pos开始的n个字符为字符串s |
void test()
{
//查找
string str04 = "abcdef";
int pos = str04.find("abc");
if (pos == -1)
{
cout << "未找到字符串" << endl;
}
else
{
cout << "找到了字符串，起始位置为：" << pos << endl;
}
//替换
string str05 = "hello world";
//替换从pos开始n个字符为字符串str
str05.replace(6, 5, "C/Cpp");
cout << str05 << endl;
}
int main()
{
test();
return 0;
}输出结果
找到了字符串，起始位置为：0
hello C/Cpp3.1.2.6 string比较操作
/* compare函数在>时返回 1，<时返回 -1，==时返回 0。比较区分大小写，比较时参考字典顺序，排越前面的越小。大写的A比小写的a小。 */ int compare(const string &s) const; //与字符串s比较 int compare(const char *s) const; //与字符串s比较 |
void test()
{
string str01 = "abcde";
string str02 = "abcdf";
if (str01.compare(str02) == 0)
{
cout << "str01==str02" << endl;
}
else if (str01.compare(str02) > 0)
{
cout << "str01>str02" << endl;
}
else
{
cout << "str01<str02" << endl;
}
}
int main()
{
test();
return 0;
}输出结果
str01<str023.1.2.7 string子串
string substr(int pos = 0, int n = npos) const;//返回由pos开始的n个字符组成的字符串 |
void test()
{
//返回由pos开始的n个字符组成
string str01 = "abcdef";
string str02 = str01.substr(0, 3);
cout << str02 << endl;
string email = "Cpp@China.com";
int n = email.find("@");
cout << n << endl;
string str03 = email.substr(0, n);
cout << str03 << endl;
}
int main()
{
test();
return 0;
}输出结果
abc
3
Cpp
void test()
{
string str01 = "www.itcast.com.cn";
//将 www itcast com cn 单词截取到 vector容器中
vector<string>v;
int pos = -1;
int start = 0;
while (true)
{
pos = str01.find(".", start);
if (pos == -1)
{
string tempStr = str01.substr(start, str01.size() - start);
v.push_back(tempStr);
break;
}
string tempStr = str01.substr(start, pos - start);
v.push_back(tempStr);
start = pos + 1;
}
for (vector<string>::iterator it = v.begin(); it != v.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
int main()
{
test();
return 0;
}www itcast com cn3.1.2.8 string插入和删除操作
string& insert(int pos, const char* s); //插入字符串 string& insert(int pos, const string& str); //插入字符串 string& insert(int pos, int n, char c); //在指定位置插入n个字符c string& erase(int pos, int n = npos); //删除从Pos开始的n个字符 |
输出结果
void test()
{
string str01 = "hello world";
str01.insert(5, "you");
cout << str01 << endl;
str01.erase(1, 3);
cout << str01 << endl;
}
int main()
{
test();
return 0;
}输出结果
helloyou world
hoyou world3.1.2.9 string和c-style字符串转换
//string 转 char* string str = "itcast"; const char* cstr = str.c_str(); //char* 转 string char* s = "itcast"; string str(s); |
void doWork01(string str)
{
;
}
void doWork02(const char* str)
{
;
}
void test()
{
//const char * 转为 string
const char* str01 = "abcd";
string str02(str01);
cout << str02 << endl;
//string 转为 const char *
const char* str03 = str02.c_str();
cout << str03 << endl;
//const char * 可以隐式类型转换为 string
doWork01(str03);
//string 不可以隐式类型转换为 const char*
//doWork02(str02);
}
int main()
{
test();
return 0;
}输出结果
abcd
abcd提示:
在c++中存在一个从const char*到string的隐式类型转换，却不存在从一个string对象到C_string的自动类型转换。通常，程序员在整个程序中应坚持使用string类对象。 |
提示:
为了修改string字符串的内容，下标操作符[]和at都会返回字符的引用。但当字符串的内存被重新分配之后，可能发生错误。 |
void test()
{
string str01 = "abcdef";
cout << str01 << endl;
char& a = str01[0];
char& b = str01[1];
a = '0';
b = '1';
cout << str01 << endl;
str01 = "hello world hello you";
cout << str01 << endl;
//此时str01已经重新寻找地址，a,b已经不指向原空间，故不可以再操作
//a = '0';
//b = '1';
}
int main()
{
test();
return 0;
}输出结果
abcdef
01cdef
hello world hello you练习：小写字符转大写字符
void test()
{
string str01 = "abcdef";
cout << str01 << endl;
for (int i = 0; i < str01.size(); i++)
{
str01[i] = toupper(str01[i]);
//str01[i] = tolower(str01[i]);
}
cout << str01 << endl;
}
int main()
{
test();
return 0;
}输出结果
abcdef
ABCDEF3.2 vector容器
3.2.1 vector容器基本概念
vector的数据安排以及操作方式，与array非常相似，两者的唯一差别在于空间的运用的灵活性。Array是静态空间，一旦配置了就不能改变，要换大一点或者小一点的空间，可以，一切琐碎得由自己来，首先配置一块新的空间，然后将旧空间的数据搬往新空间，再释放原来的空间。Vector是动态空间，随着元素的加入，它的内部机制会自动扩充空间以容纳新元素。因此vector的运用对于内存的合理利用与运用的灵活性有很大的帮助，我们再也不必害怕空间不足而一开始就要求一个大块头的array了。
Vector的实现技术，关键在于其对大小的控制以及重新配置时的数据移动效率，一旦vector旧空间满了，如果客户每新增一个元素，vector内部只是扩充一个元素的空间，实为不智，因为所谓的扩充空间(不论多大)，一如刚所说，是”配置新空间-数据移动-释放旧空间”的大工程,时间成本很高，应该加入某种未雨绸缪的考虑，稍后我们便可以看到vector的空间配置策略。
3.2.2 vector迭代器
Vector维护一个线性空间，所以不论元素的型别如何，普通指针都可以作为vector的迭代器，因为vector迭代器所需要的操作行为，如operaroe*, operator->, operator++, operator--, operator+, operator-, operator+=, operator-=, 普通指针天生具备。Vector支持随机存取，而普通指针正有着这样的能力。所以vector提供的是随机访问迭代器(Random Access Iterators).
根据上述描述，如果我们写如下的代码：
Vector<int>::iterator it1;
Vector<Teacher>::iterator it2;
it1的型别其实就是Int*,it2的型别其实就是Teacher*.
void test()
{
vector<int >v;
for (int i = 0; i < 10; i++)
{
v.push_back(i);
cout << v.capacity() << endl;
}
}
int main()
{
test();
return 0;
}输出结果
1
2
3
4
6
6
9
9
9
133.2.3 vector的数据结构
Vector所采用的数据结构非常简单，线性连续空间，它以两个迭代器_Myfirst和_Mylast分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器_Myend指向整块连续内存空间的尾端。
为了降低空间配置时的速度成本，vector实际配置的大小可能比客户端需求大一些，以备将来可能的扩充，这边是容量的概念。换句话说，一个vector的容量永远大于或等于其大小，一旦容量等于大小，便是满载，下次再有新增元素，整个vector容器就得另觅居所。
注意：
所谓动态增加大小，并不是在原空间之后续接新空间(因为无法保证原空间之后尚有可配置的空间)，而是一块更大的内存空间，然后将原数据拷贝新空间，并释放原空间。因此，对vector的任何操作，一旦引起空间的重新配置，指向原vector的所有迭代器就都失效了。这是程序员容易犯的一个错误，务必小心。 |
3.2.4 vector常用API操作
3.2.4.1 vector构造函数
vector<T> v; //采用模板实现类实现，默认构造函数 vector(v.begin(), v.end()); //将v[begin(), end())区间中的元素拷贝给本身。 vector(n, elem); //构造函数将n个elem拷贝给本身。 vector(const vector &vec); //拷贝构造函数。 |
void test()
{
int arr[] = { 1,2,3,4,5 };
vector<int>v01(arr, arr + sizeof(arr) / sizeof(int));
for (vector<int>::iterator it = v01.begin(); it != v01.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
int main()
{
test();
return 0;
}输出结果
1 2 3 4 53.2.4.2 vector常用赋值操作
assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身。 assign(n, elem); //将n个elem拷贝赋值给本身。 vector& operator=(const vector &vec); //重载等号操作符 swap(vec); //将vec与本身的元素互换。 |
void test()
{
vector<int>v1;
v1.push_back(10);
v1.push_back(20);
v1.push_back(30);
v1.push_back(40);
v1.push_back(50);
PrintVector(v1);
vector<int>v2(v1.begin(), v1.end());
PrintVector(v2);
vector<int>v3;
v3.assign(v1.begin(), v1.end());
PrintVector(v3);
vector<int>v4(10, 100);
PrintVector(v4);
cout << "v3和v4互换后：" << endl;
v3.swap(v4);
PrintVector(v3);
PrintVector(v4);
}
int main()
{
test();
return 0;
}输出结果
10 20 30 40 50
10 20 30 40 50
10 20 30 40 50
100 100 100 100 100 100 100 100 100 100
v3和v4互换后：
100 100 100 100 100 100 100 100 100 100
10 20 30 40 503.2.4.3 vector大小操作
size(); //返回容器中元素的个数 empty(); //判断容器是否为空 resize(int num); //重新指定容器的长度为num，若容器变长，则以默认值填充新 位置。如果容器变短，则末尾超出容器长度的元素被删除。 resize(int num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新 位置。如果容器变短，则末尾超出容器长>度的元素被删除。 capacity(); //容器的容量 reserve(int len); //容器预留len个元素长度，预留位置不初始化，元素不可访问。 |
3.2.4.4 vector数据存取操作
at(int idx); //返回索引idx所指的数据，如果idx越界，抛出out_of_range异常。 operator[]; //返回索引idx所指的数据，越界时，运行直接报错 front(); //返回容器中第一个数据元素 back(); //返回容器中最后一个数据元素 |
void PrintVector(vector<int>& v)
{
for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
void test()
{
vector<int>v1;
v1.push_back(10);
v1.push_back(20);
v1.push_back(30);
v1.push_back(40);
v1.push_back(50);
if (v1.empty())
{
cout << "v1为空" << endl;
}
else
{
cout << "v1不为空,大小为：" << v1.size() << endl;
}
//第二个参数代表默认填充值
v1.resize(10, 100);
PrintVector(v1);
v1.resize(3);
PrintVector(v1);
cout << "v1的front=" << v1.front() << endl;
cout << "v1的back=" << v1.back() << endl;
}
int main()
{
test();
return 0;
}输出结果
v1不为空,大小为：5
10 20 30 40 50 100 100 100 100 100
10 20 30
v1的front=10
v1的back=303.2.4.5 vector插入和删除操作
insert(const_iterator pos, int count,ele); //迭代器指向位置pos插入count个元素ele. push_back(ele); //尾部插入元素ele pop_back(); //删除最后一个元素 erase(const_iterator start, const_iterator end); //删除迭代器从start到end之间的元素 erase(const_iterator pos); //删除迭代器指向的元素 clear(); //删除容器中所有元素 |
void PrintVector(vector<int>& v)
{
for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
void test01()
{
vector<int>v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.insert(v.begin(), 100);
PrintVector(v);
v.push_back(1000);
PrintVector(v);
v.erase(v.begin());
PrintVector(v);
//v.erase(v.begin(), v.end()); 等价于 v.clear();
v.clear();
PrintVector(v);
}
//案例展示
void test02()
{
vector<int>v;
for (int i = 0; i < 10000; i++)
{
v.push_back(i);
}
cout << "v.capacity" << v.capacity() << endl;
cout << "v.size" << v.size() << endl;
v.reserve(3);
cout << "v.capacity" << v.capacity() << endl;
cout << "v.size" << v.size() << endl;
//巧用swap收缩内存
vector<int>(v).swap(v);
cout << "v.capacity" << v.capacity() << endl;
cout << "v.size" << v.size() << endl;
}
int main()
{
test01();
test02();
return 0;
}输出结果
100 10 20 30 40
100 10 20 30 40 1000
10 20 30 40 1000
v.capacity12138
v.size10000
v.capacity12138
v.size10000
v.capacity10000
v.size100003.2.5.2 reserve预留空间
void test()
{
vector<int>v;
//预先开辟空间
v.reserve(10);
int* p = NULL;
int num = 0;
for (int i = 0; i < 10000; i++)
{
v.push_back(i);
if (p != &v[0])
{
p = &v[0];
num++;
}
}
cout << "num=" << num << endl;
}
int main()
{
test();
return 0;
}输出结果
num=193.3 deque容器
3.3.1 deque容器基本概念
Vector容器是单向开口的连续内存空间，deque则是一种双向开口的连续线性空间。所谓的双向开口，意思是可以在头尾两端分别做元素的插入和删除操作，当然，vector容器也可以在头尾两端插入元素，但是在其头部操作效率奇差，无法被接受。
Deque容器和vector容器最大的差异，一在于deque允许使用常数项时间对头端进行元素的插入和删除操作。二在于deque没有容量的概念，因为它是动态的以分段连续空间组合而成，随时可以增加一段新的空间并链接起来，换句话说，像vector那样，”旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间”这样的事情在deque身上是不会发生的。也因此，deque没有必须要提供所谓的空间保留(reserve)功能.
虽然deque容器也提供了Random Access Iterator,但是它的迭代器并不是普通的指针，其复杂度和vector不是一个量级，这当然影响各个运算的层面。因此，除非有必要，我们应该尽可能的使用vector，而不是deque。对deque进行的排序操作，为了最高效率，可将deque先完整的复制到一个vector中，对vector容器进行排序，再复制回deque.
3.3.2 deque容器实现原理
Deque容器是连续的空间，至少逻辑上看来如此，连续现行空间总是令我们联想到array和vector,array无法成长，vector虽可成长，却只能向尾端成长，而且其成长其实是一个假象，事实上(1) 申请更大空间 (2)原数据复制新空间 (3)释放原空间 三步骤，如果不是vector每次配置新的空间时都留有余裕，其成长假象所带来的代价是非常昂贵的。
Deque是由一段一段的定量的连续空间构成。一旦有必要在deque前端或者尾端增加新的空间，便配置一段连续定量的空间，串接在deque的头端或者尾端。Deque最大的工作就是维护这些分段连续的内存空间的整体性的假象，并提供随机存取的接口，避开了重新配置空间，复制，释放的轮回，代价就是复杂的迭代器架构。
既然deque是分段连续内存空间，那么就必须有中央控制，维持整体连续的假象，数据结构的设计及迭代器的前进后退操作颇为繁琐。Deque代码的实现远比vector或list都多得多。
Deque采取一块所谓的map(注意，不是STL的map容器)作为主控，这里所谓的map是一小块连续的内存空间，其中每一个元素(此处成为一个结点)都是一个指针，指向另一段连续性内存空间，称作缓冲区。缓冲区才是deque的存储空间的主体。
3.3.3 deque常用API
3.3.3.1 deque构造函数
deque<T> deqT; //默认构造形式 deque(beg, end); //构造函数将[beg, end)区间中的元素拷贝给本身。 deque(n, elem); //构造函数将n个elem拷贝给本身。 deque(const deque &deq); //拷贝构造函数。 |
3.3.3.2 deque赋值操作
assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身。 assign(n, elem); //将n个elem拷贝赋值给本身。 deque& operator=(const deque &deq); //重载等号操作符 swap(deq); // 将deq与本身的元素互换 |
3.3.3.3 deque大小操作
deque.size(); //返回容器中元素的个数 deque.empty(); //判断容器是否为空 deque.resize(num); //重新指定容器的长度为num,若容器变长，则以默认值填充新 位置。如果容器变短，则末尾超出容器长度的元素被删除。 deque.resize(num, elem); //重新指定容器的长度为num,若容器变长，则以elem值填充 新位置,如果容器变短，则末尾超出容器长度的元素被删除。 |
void PrintDeque(const deque<int>& d)
{
//iterator普通迭代器
//reverse_iterator 反转迭代器
//const_iterator 只读迭代器
for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
void test()
{
deque<int>d01;
d01.push_back(10);
d01.push_back(20);
d01.push_back(30);
d01.push_back(40);
PrintDeque(d01);
deque<int>d02;
d02 = d01;
PrintDeque(d02);
if (d02.empty())
{
cout << "d02为空" << endl;
}
else
{
cout << "d02不为空，size=" << d02.size() << endl;
}
}
int main()
{
test();
return 0;
}输出结果
10 20 30 40
10 20 30 40
d02不为空，size=43.3.3.4 deque双端插入和删除操作
push_back(elem); //在容器尾部添加一个数据 push_front(elem); //在容器头部插入一个数据 pop_back(); //删除容器最后一个数据 pop_front(); //删除容器第一个数据 |
3.3.3.5 deque数据存取
at(idx); //返回索引idx所指的数据，如果idx越界，抛出out_of_range。 operator[]; //返回索引idx所指的数据，如果idx越界，不抛出异常，直接出错。 front(); //返回第一个数据。 back(); //返回最后一个数据 |
void PrintDeque(const deque<int>& d)
{
//iterator普通迭代器
//reverse_iterator 反转迭代器
//const_iterator 只读迭代器
for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
void test()
{
deque<int>d01;
d01.push_back(10);
d01.push_back(20);
d01.push_back(30);
d01.push_back(100);
d01.push_back(200);
d01.push_back(300);
PrintDeque(d01);
//尾删
d01.pop_back();
//头删
d01.pop_front();
PrintDeque(d01);
cout << "第一个元素为" << d01.front() << endl;
cout << "最后一个元素为" << d01.back() << endl;
}
int main()
{
test();
return 0;
}输出结果
10 20 30 100 200 300
20 30 100 200
第一个元素为20
最后一个元素为2003.3.3.6 deque插入操作
insert(pos,elem); //在pos位置插入一个elem元素的拷贝，返回新数据的位置。 insert(pos,n,elem); //在pos位置插入n个elem数据，无返回值。 insert(pos,beg,end); //在pos位置插入[beg,end)区间的数据，无返回值。 |
3.3.3.7 deque删除操作
clear(); //移除容器的所有数据 erase(beg,end); //删除[beg,end)区间的数据，返回下一个数据的位置。 erase(pos); //删除pos位置的数据，返回下一个数据的位置。 |
void PrintDeque(const deque<int>& d)
{
//iterator普通迭代器
//reverse_iterator 反转迭代器
//const_iterator 只读迭代器
for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
void test()
{
deque<int>d01;
d01.push_back(10);
d01.push_back(20);
d01.push_back(30);
d01.push_back(100);
d01.push_back(200);
d01.push_back(300);
PrintDeque(d01);
//插入
d01.insert(d01.begin(), 2, 1000);
PrintDeque(d01);
//删除
d01.erase(d01.begin());
PrintDeque(d01);
deque<int>::iterator it1 = d01.begin();
it1 = it1 + 1;
deque<int>::iterator it2 = d01.begin();
it2 = it2 + 3;
d01.erase(it1, it2);
PrintDeque(d01);
//清空
d01.clear();
PrintDeque(d01);
}
int main()
{
test();
return 0;
}输出结果
10 20 30 100 200 300
1000 1000 10 20 30 100 200 300
1000 10 20 30 100 200 300
1000 30 100 200 300自定义排序
void PrintDeque(const deque<int>& d)
{
//iterator普通迭代器
//reverse_iterator 反转迭代器
//const_iterator 只读迭代器
for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
bool myCompare(int v1, int v2)
{
return v1 > v2;
}
void test()
{
deque<int>d01;
d01.push_back(10);
d01.push_back(20);
d01.push_back(30);
d01.push_back(100);
d01.push_back(200);
d01.push_back(300);
//默认排序从小到大
sort(d01.begin(), d01.end());
PrintDeque(d01);
sort(d01.begin(), d01.end(), myCompare);
PrintDeque(d01);
}
int main()
{
test();
return 0;
}输出结果
10 20 30 100 200 300
300 200 100 30 20 10练习：评委打分案例
/*
//有5名选手：选手ABCDE，10个评委分别对每一名选手打分，去除最高分，去除评委中最低分，取平均分。
//1. 创建五名选手，放到vector中
//2. 遍历vector容器，取出来每一个选手，执行for循环，可以把10个评分打分存到deque容器中
//3. sort算法对deque容器中分数排序，pop_back pop_front去除最高和最低分
//4. deque容器遍历一遍，累加分数，累加分数/d.size()
//5. person.score = 平均分
*/
class Player
{
public:
Player(string name, int score)
{
this->Name = name;
this->Score = score;
}
string Name;
int Score;
};
void createPlayer(vector<Player>& v)
{
string nameseed = "ABCDE";
string name = "选手";
for (int i = 0; i < 5; i++)
{
name = name + nameseed[i];
int score = 0;
Player player(name, score);
v.push_back(player);
}
}
void SetScore(vector<Player>&v)
{
for (vector<Player>::iterator it = v.begin(); it != v.end(); it++)
{
//存放评委打分的容器
deque<int>d;
for (int i = 0; i < 10; i++)
{
int score = rand() % 41 + 60;
d.push_back(score);
}
sort(d.begin(), d.end());
//去除最高最低分
d.pop_back();
d.pop_front();
int sum = 0;
for (deque<int>::iterator dit = d.begin(); dit != d.end(); dit++)
{
sum = sum + *dit;
}
//平均分
int avg = sum / d.size();
it->Score = avg;
}
}
void ShowScore(vector<Player>& v)
{
for (vector<Player>::iterator it = v.begin(); it != v.end(); it++)
{
cout << "姓名：" << (*it).Name << "平均分数：" << it->Score << endl;
}
}
int main()
{
//设置随机数种子
srand((unsigned int)time(NULL));
//1.创建5名选手
vector<Player>v;
createPlayer(v);
//2.打分
SetScore(v);
//3.显示平均分
ShowScore(v);
return 0;
}输出结果
姓名：选手A平均分数：79
姓名：选手AB平均分数：76
姓名：选手ABC平均分数：80
姓名：选手ABCD平均分数：81
姓名：选手ABCDE平均分数：793.4 stack容器
3.4.1 stack容器基本概念
stack是一种先进后出(First In Last Out,FILO)的数据结构，它只有一个出口，形式如图所示。stack容器允许新增元素，移除元素，取得栈顶元素，但是除了最顶端外，没有任何其他方法可以存取stack的其他元素。换言之，stack不允许有遍历行为。
有元素推入栈的操作称为:push,将元素推出stack的操作称为pop.
3.4.2 stack没有迭代器
Stack所有元素的进出都必须符合”先进后出”的条件，只有stack顶端的元素，才有机会被外界取用。Stack不提供遍历功能，也不提供迭代器。
3.4.3 stack常用API
3.4.3.1 stack构造函数
stack<T> stkT; //stack采用模板类实现， stack对象的默认构造形式： stack(const stack &stk); //拷贝构造函数 |
3.4.3.2 stack赋值操作
stack& operator=(const stack &stk); //重载等号操作符 |
3.4.3.3 stack数据存取操作
push(elem); //向栈顶添加元素 pop(); //从栈顶移除第一个元素 top(); //返回栈顶元素 |
3.4.3.4 stack大小操作
empty(); //判断堆栈是否为空 size(); //返回堆栈的大小 |
void test()
{
stack<int>S;
//入栈
S.push(10);
S.push(20);
S.push(30);
S.push(40);
cout << "size = " << S.size() << endl;
while (!S.empty())
{
//访问栈顶元素
cout << S.top() << endl;
//出栈
S.pop();
}
cout << "size = " << S.size() << endl;
}
int main()
{
test();
return 0;
}输出结果
size = 4
40
30
20
10
size = 03.5 queue容器
3.5.1 queue容器基本概念
Queue是一种先进先出(First In First Out,FIFO)的数据结构，它有两个出口，queue容器允许从一端新增元素，从另一端移除元素。
3.5.2 queue没有迭代器
Queue所有元素的进出都必须符合”先进先出”的条件，只有queue的顶端元素，才有机会被外界取用。Queue不提供遍历功能，也不提供迭代器。
3.5.3 queue常用API
3.5.3.1 queue构造函数
queue<T> queT; //queue采用模板类实现，queue对象的默认构造形式： queue(const queue &que); //拷贝构造函数 |
3.5.3.2 queue存取、插入和删除操作
push(elem); //往队尾添加元素 pop(); //从队头移除第一个元素 back(); //返回最后一个元素 front(); //返回第一个元素 |
3.5.3.3 queue赋值操作
queue& operator=(const queue &que); //重载等号操作符 |
3.5.3.4 queue大小操作
empty(); //判断队列是否为空 size(); //返回队列的大小 |
class Person
{
public:
Person(string name, int age)
{
this->Name = name;
this->Age = age;
}
public:
string Name;
int Age;
};
void test()
{
queue<Person>Q;
Person p1("aaa", 10);
Person p2("bbb", 20);
Person p3("ccc", 30);
Person p4("ddd", 40);
//入队
Q.push(p1);
Q.push(p2);
Q.push(p3);
Q.push(p4);
cout << "size = " << Q.size() << endl;
while (!Q.empty())
{
cout << "队头元素 " << Q.front().Name << "年龄 " << Q.front().Age << endl;
cout << "队尾元素 " << Q.back().Name << "年龄 " << Q.back().Age << endl;
//出队
Q.pop();
}
cout << "size = " << Q.size() << endl;
}
int main()
{
test();
return 0;
}输出结果
size = 4
队头元素 aaa年龄 10
队尾元素 ddd年龄 40
队头元素 bbb年龄 20
队尾元素 ddd年龄 40
队头元素 ccc年龄 30
队尾元素 ddd年龄 40
队头元素 ddd年龄 40
队尾元素 ddd年龄 40
size = 03.6 list容器
3.6.1 list容器基本概念
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
相较于vector的连续线性空间，list就显得负责许多，它的好处是每次插入或者删除一个元素，就是配置或者释放一个元素的空间。因此，list对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素的移除，list永远是常数时间。
List和vector是两个最常被使用的容器。
List容器是一个双向链表。
- 采用动态存储分配，不会造成内存浪费和溢出
- 链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素
- 链表灵活，但是空间和时间额外耗费较大
3.6.2 list容器的迭代器
List容器不能像vector一样以普通指针作为迭代器，因为其节点不能保证在同一块连续的内存空间上。List迭代器必须有能力指向list的节点，并有能力进行正确的递增、递减、取值、成员存取操作。所谓”list正确的递增，递减、取值、成员取用”是指，递增时指向下一个节点，递减时指向上一个节点，取值时取的是节点的数据值，成员取用时取的是节点的成员。
由于list是一个双向链表，迭代器必须能够具备前移、后移的能力，所以list容器提供的是Bidirectional Iterators.
List有一个重要的性质，插入操作和删除操作都不会造成原有list迭代器的失效。这在vector是不成立的，因为vector的插入操作可能造成记忆体重新配置，导致原有的迭代器全部失效，甚至List元素的删除，也只有被删除的那个元素的迭代器失效，其他迭代器不受任何影响。
3.6.3 list容器的数据结构
list容器不仅是一个双向链表，而且还是一个循环的双向链表。
3.6.4 list常用API
3.6.4.1 list构造函数
list<T> lstT; //list采用采用模板类实现,对象的默认构造形式： list(beg,end); //构造函数将[beg, end)区间中的元素拷贝给本身。 list(n,elem); //构造函数将n个elem拷贝给本身。 list(const list &lst); //拷贝构造函数。 |
3.6.4.2 list数据元素插入和删除操作
push_back(elem); //在容器尾部加入一个元素 pop_back(); //删除容器中最后一个元素 push_front(elem); //在容器开头插入一个元素 pop_front(); //从容器开头移除第一个元素 insert(pos,elem); //在pos位置插elem元素的拷贝，返回新数据的位置。 insert(pos,n,elem); //在pos位置插入n个elem数据，无返回值。 insert(pos,beg,end); //在pos位置插入[beg,end)区间的数据，无返回值。 clear(); //移除容器的所有数据 erase(beg,end); //删除[beg,end)区间的数据，返回下一个数据的位置。 erase(pos); //删除pos位置的数据，返回下一个数据的位置。 remove(elem); //删除容器中所有与elem值匹配的元素。 |
//遍历链表
void PrintList(const list<int>& L)
{
for (list<int>::const_iterator it = L.begin(); it != L.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
void test01()
{
list <int>L1;
L1.push_back(10);
L1.push_back(20);
L1.push_back(30);
//逆序遍历
for (list<int>::reverse_iterator it = L1.rbegin(); it != L1.rend(); it++)
{
cout << *it << endl;
}
//list迭代器不支持随机访问
list<int>::iterator it = L1.begin();
//it = it + 1;
}
void test02()
{
list<int>L;
L.push_back(10);
L.push_back(20);
L.push_back(30);
L.push_back(100);
L.push_back(200);
L.push_back(300);
PrintList(L);
L.pop_front();
L.pop_back();
PrintList(L);
L.erase(L.begin());
PrintList(L);
L.push_back(100);
L.push_back(100);
PrintList(L);
L.remove(100);
PrintList(L);
}
int main()
{
test01();
test02();
return 0;
}输出结果
30
20
10
10 20 30 100 200 300
20 30 100 200
30 100 200
30 100 200 100 100
30 2003.6.4.3 list大小操作
size(); //返回容器中元素的个数 empty(); //判断容器是否为空 resize(num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位 置。如果容器变短，则末尾超出容器长度的元素被删除。 resize(num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新 位置。如果容器变短，则末尾超出容器长度的元素被删除。 |
3.6.4.4 list赋值操作
assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身。 assign(n, elem); //将n个elem拷贝赋值给本身。 list& operator=(const list &lst); //重载等号操作符 swap(lst); //将lst与本身的元素互换。 |
3.6.4.5 list数据的存取
front(); //返回第一个元素。 back(); //返回最后一个元素。 |
3.6.4.6 list反转排序
reverse(); //反转链表，比如lst包含1,3,5元素，运行此方法后，lst就包含5,3,1元素。 sort(); //list排序 |
//遍历链表
void PrintList(const list<int>& L)
{
for (list<int>::const_iterator it = L.begin(); it != L.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
void test()
{
list<int>L1;
L1.push_back(10);
L1.push_back(20);
L1.push_back(30);
L1.push_back(100);
L1.push_back(200);
L1.push_back(300);
PrintList(L1);
L1.resize(9);
PrintList(L1);
L1.resize(3);
PrintList(L1);
list<int>L2;
L2.assign(10,100);
PrintList(L2);
L1.swap(L2);
PrintList(L2);
cout << L2.front() << " " << L2.back() << endl;
}
int main()
{
test();
return 0;
}输出结果
10 20 30 100 200 300
10 20 30 100 200 300 0 0 0
10 20 30
100 100 100 100 100 100 100 100 100 100
10 20 30
10 303.6.4.6 list反转排序
reverse(); //反转链表，比如lst包含1,3,5元素，运行此方法后，lst就包含5,3,1元素。 sort(); //list排序 |
//遍历链表
void PrintList(const list<int>& L)
{
for (list<int>::const_iterator it = L.begin(); it != L.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
bool myCompare(int v1, int v2)
{
return v1 > v2;
}
void test()
{
list<int>L;
L.push_back(10);
L.push_back(30);
L.push_back(20);
L.push_back(100);
L.push_back(300);
L.push_back(200);
PrintList(L);
//反转
L.reverse();
PrintList(L);
//排序
L.sort();
PrintList(L);
//自定义排序
L.sort(myCompare);
PrintList(L);
}
int main()
{
test();
return 0;
}输出结果
10 30 20 100 300 200
200 300 100 20 30 10
10 20 30 100 200 300
300 200 100 30 20 10案例：使用list存储自定义类型
class Person
{
public:
Person(string name, int age, int height)
{
this->Name = name;
this->Age = age;
this->Height = height;
}
bool operator==(const Person& p)
{
if (this->Name == p.Name && this->Age == p.Age && this->Height == p.Height)
{
return true;
}
return false;
}
public:
string Name;
int Age;
int Height;
};
bool myComparePerson(Person& p1, Person& p2)
{
if (p1.Age == p2.Age)
{
return p1.Height < p2.Height;
}
return p1.Age < p2.Age;
}
void PrintPerson(list<Person>& L)
{
for (list<Person>::iterator it = L.begin(); it != L.end(); it++)
{
cout << it->Name << " " << it->Age << " " << it->Height << endl;
}
cout << endl;
}
void test()
{
list<Person>L;
Person p1("亚瑟", 40, 180);
Person p2("赵云", 20, 160);
Person p3("妲己", 30, 120);
Person p4("黄忠", 50, 150);
Person p5("关羽", 60, 140);
Person p6("刘备", 70, 130);
Person p7("张飞", 80, 190);
L.push_back(p1);
L.push_back(p2);
L.push_back(p3);
L.push_back(p4);
L.push_back(p5);
L.push_back(p6);
L.push_back(p7);
PrintPerson(L);
//按照年龄进行降序 从大到下 , 如果年龄相等，按照身高进行升序
//对于自定义数据类型，必须要指定排序规则
L.sort(myComparePerson);
PrintPerson(L);
}
int main()
{
test();
return 0;
}输出结果
亚瑟 40 180
赵云 20 160
妲己 30 120
黄忠 50 150
关羽 60 140
刘备 70 130
张飞 80 190
赵云 20 160
妲己 30 120
亚瑟 40 180
黄忠 50 150
关羽 60 140
刘备 70 130
张飞 80 1903.7 set/multiset容器
3.7.1 set/multiset容器基本概念
3.7.1.1 set容器基本概念
Set的特性是。所有元素都会根据元素的键值自动被排序。Set的元素不像map那样可以同时拥有实值和键值，set的元素即是键值又是实值。Set不允许两个元素有相同的键值。
我们可以通过set的迭代器改变set元素的值吗？不行，因为set元素值就是其键值，关系到set元素的排序规则。如果任意改变set元素值，会严重破坏set组织。换句话说，set的iterator是一种const_iterator.
set拥有和list某些相同的性质，当对容器中的元素进行插入操作或者删除操作的时候，操作之前所有的迭代器，在操作完成之后依然有效，被删除的那个元素的迭代器必然是一个例外。
3.7.1.2 multiset容器基本概念
multiset特性及用法和set完全相同，唯一的差别在于它允许键值重复。set和multiset的底层实现是红黑树，红黑树为平衡二叉树的一种。
树的简单知识：
二叉树就是任何节点最多只允许有两个字节点。分别是左子结点和右子节点。
二叉搜索树，是指二叉树中的节点按照一定的规则进行排序，使得对二叉树中元素访问更加高效。二叉搜索树的放置规则是：任何节点的元素值一定大于其左子树中的每一个节点的元素值，并且小于其右子树的值。因此从根节点一直向左走，一直到无路可走，即得到最小值，一直向右走，直至无路可走，可得到最大值。那么在儿茶搜索树中找到最大元素和最小元素是非常简单的事情。下图为二叉搜索树：
上面我们介绍了二叉搜索树，那么当一个二叉搜索树的左子树和右子树不平衡的时候，那么搜索依据上图表示，搜索9所花费的时间要比搜索17所花费的时间要多，由于我们的输入或者经过我们插入或者删除操作，二叉树失去平衡，造成搜索效率降低。
所以我们有了一个平衡二叉树的概念，所谓的平衡不是指的完全平衡。
RB-tree(红黑树)为二叉树的一种。
3.7.2 set常用API
3.7.2.1 set构造函数
set<T> st; //set默认构造函数： mulitset<T> mst; //multiset默认构造函数: set(const set &st); //拷贝构造函数 |
3.7.2.2 set赋值操作
set& operator=(const set &st); //重载等号操作符 swap(st); //交换两个集合容器 |
3.7.2.3 set大小操作
size(); //返回容器中元素的数目 empty(); //判断容器是否为空 |
3.7.2.4 set插入和删除操作
insert(elem); //在容器中插入元素。 clear(); //清除所有元素 erase(pos); //删除pos迭代器所指的元素，返回下一个元素的迭代器。 erase(beg, end); //删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。 erase(elem); //删除容器中值为elem的元素。 |
void PrintSet(set<int>& s)
{
for (set<int>::iterator it = s.begin(); it != s.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
void test()
{
set<int>s;
s.insert(10);
s.insert(20);
s.insert(50);
s.insert(30);
s.insert(40);
PrintSet(s);
if (s.empty())
{
cout << "set为空" << endl;
}
else
{
cout << "set不为空，大小为：" << s.size() << endl;
}
s.erase(20);
PrintSet(s);
}
int main()
{
test();
return 0;
}输出结果
10 20 30 40 50
set不为空，大小为：5
10 30 40 503.7.2.5 set查找操作
find(key); //查找键key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回 set.end(); count(key); //查找键key的元素个数 lower_bound(keyElem); //返回第一个key>=keyElem元素的迭代器。 upper_bound(keyElem); //返回第一个key>keyElem元素的迭代器。 equal_range(keyElem); //返回容器中key与keyElem相等的上下限的两个迭代器。 |
3.7.3 对组(pair)
对组(pair)将一对值组合成一个值，这一对值可以具有不同的数据类型，两个值可以分别用pair的两个公有属性first和second访问。
类模板：template <class T1, class T2> struct pair.
如何创建对组?
void test()
{
//第一种方法
pair <string, int>pair01(string("Tom"), 20);
cout << pair01.first << " ";
cout << pair01.second << endl;
//第二种方法
pair <string, int>pair02=make_pair(string("Tom"), 20);
cout << pair02.first << " ";
cout << pair02.second << endl;
//第三种方法
pair<string, int>pair3("Tom", 20);
cout << pair02.first<<" ";
cout << pair02.second << endl;
}
int main()
{
test();
return 0;
}输出结果
Tom 20
Tom 20
Tom 20void PrintSet(set<int>& s)
{
for (set<int>::iterator it = s.begin(); it != s.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
void test01()
{
cout << endl;
cout << "test01" << endl;
set<int>s;
s.insert(10);
s.insert(20);
s.insert(50);
s.insert(30);
s.insert(40);
set<int>::iterator pos = s.find(30);
if (pos != s.end())
{
cout << "找到了元素" << endl;
}
else
{
cout << "未找到" << endl;
}
//对于set而言，count的结果 要么是0 要么是1
int num = s.count(40);
cout << "key为40的个数为" << num << endl;
set<int>::iterator pos2 = s.lower_bound(30);
//lower_bound(keyElem),返回第一个key>=keyElem元素的迭代器
if (pos2 != s.end())
{
cout << "lower_bound的值为：" << *pos << endl;
}
else
{
cout << "未找到" << endl;
}
//upper_bound(keyElem),返回第一个key>keyElem元素的迭代器
pos2 = s.upper_bound(30);
if (pos != s.end())
{
cout << "upper_bound的值为：" << *pos << endl;
}
else
{
cout << "未找到" << endl;
}
//equal_range(keyElem),返回容器中key与keyElem相等的上下限的两个迭代器
pair<set<int>::iterator, set<int>::iterator> ret = s.equal_range(30);
if (ret.first != s.end())
{
cout << "equal_range中的lower_bound的值为：" << *ret.first << endl;
}
else
{
cout << "未找到" << endl;
}
if (ret.second != s.end())
{
cout << "equal_range中的upper_bound的值为：" << *ret.first << endl;
}
else
{
cout << "未找到" << endl;
}
}
void test02()
{
cout << endl;
cout << "test02" << endl;
pair<string, int>p01("Tom", 10);
cout << p01.first << " " << p01.second << endl;
pair<string, int>p02("Jack", 10);
cout << p02.first << " " << p02.second << endl;
}
void test03()
{
cout << endl;
cout << "test03" << endl;
set<int>s;
pair<set<int>::iterator, bool>ret = s.insert(10);
if (ret.second)
{
cout << "第一次插入成功" << endl;
}
else
{
cout << "第一次插入失败" << endl;
}
ret = s.insert(10);
if (ret.second)
{
cout << "第二次插入成功" << endl;
}
else
{
cout << "第二次插入失败" << endl;
}
PrintSet(s);
multiset<int>ms;
ms.insert(10);
ms.insert(10);
cout << "----------" << endl;
for (multiset<int>::iterator it = ms.begin(); it != ms.end(); it++)
{
cout << *it << endl;
}
}
class myCompareInt
{
public:
bool operator()(int v1, int v2)const
{
return v1 > v2;
}
};
void test04()
{
cout << endl;
cout << "test04" << endl;
//set容器的排序规则要在插入之前指定
set<int, myCompareInt>s;
s.insert(10);
s.insert(20);
s.insert(30);
s.insert(40);
s.insert(50);
for (set<int, myCompareInt>::iterator it = s.begin(); it != s.end(); it++)
{
cout << *it << endl;
}
}
//对于自定义数据类型
class Person
{
public:
Person(const string name, int age)
{
this->Nane = name;
this->Age = age;
}
string Nane;
int Age;
};
class myComparePerson
{
public:
bool operator()(const Person& p1, const Person& p2)const
{
//按照年龄 升序 从小到大
return p1.Age < p2.Age;
}
};
void test05()
{
cout << endl;
cout << "test05" << endl;
//利用仿函数 指定出自定义数据类型的排序规则
set<Person, myComparePerson>s;
Person p1("aaa", 10);
Person p2("bbb", 40);
Person p3("ccc", 20);
Person p4("ddd", 30);
Person p5("eee", 50);
s.insert(p1);
s.insert(p2);
s.insert(p3);
s.insert(p4);
s.insert(p5);
for (set<Person, myComparePerson>::iterator it = s.begin(); it != s.end(); it++)
{
cout << (*it).Nane << " " << (*it).Age << endl;
}
}
int main()
{
test01();
test02();
test03();
test04();
test05();
return 0;
}输出结果
test01
找到了元素
key为40的个数为1
lower_bound的值为：30
upper_bound的值为：30
equal_range中的lower_bound的值为：30
equal_range中的upper_bound的值为：30
test02
Tom 10
Jack 10
test03
第一次插入成功
第二次插入失败
10
----------
10
10
test04
50
40
30
20
10
test05
aaa 10
ccc 20
ddd 30
bbb 40
eee 503.8 map/multimap容器
3.8.1 map/multimap基本概念
Map的特性是，所有元素都会根据元素的键值自动排序。Map所有的元素都是pair,同时拥有实值和键值，pair的第一元素被视为键值，第二元素被视为实值，map不允许两个元素有相同的键值。
我们可以通过map的迭代器改变map的键值吗？答案是不行，因为map的键值关系到map元素的排列规则，任意改变map键值将会严重破坏map组织。如果想要修改元素的实值，那么是可以的。
Map和list拥有相同的某些性质，当对它的容器元素进行新增操作或者删除操作时，操作之前的所有迭代器，在操作完成之后依然有效，当然被删除的那个元素的迭代器必然是个例外。
Multimap和map的操作类似，唯一区别multimap键值可重复。
Map和multimap都是以红黑树为底层实现机制。
3.8.2 map/multimap常用API
3.8.2.1 map构造函数
map<T1, T2> mapTT; //map默认构造函数: map(const map &mp); //拷贝构造函数 |
3.8.2.2 map赋值操作
map& operator=(const map &mp); //重载等号操作符 swap(mp); //交换两个集合容器 |
3.8.2.3 map大小操作
size(); //返回容器中元素的数目 empty(); //判断容器是否为空 |
3.8.2.4 map插入数据元素操作
map.insert(...); //往容器插入元素，返回pair<iterator,bool> map<int, string> mapStu; // 第一种 通过pair的方式插入对象 mapStu.insert(pair<int, string>(3, "小张")); // 第二种 通过pair的方式插入对象 mapStu.inset(make_pair(-1, "校长")); // 第三种 通过value_type的方式插入对象 mapStu.insert(map<int, string>::value_type(1, "小李"));// 第四种 通过数组的方式插 入值 mapStu[3] = "小刘"; mapStu[5] = "小王"; |
void test()
{
map<int, int>m;
//第一种插入方式
m.insert(pair<int, int>(1, 10));
//第二种插入方式
m.insert(make_pair(2, 20));
//第三种插入方式
m.insert(map<int, int>::value_type(3, 30));
//第四种插入方式
m[4] = 40;
//cout << m[10] << endl; //如果利用第四种 使用未指定的key，生成一个key为为指定的值，value为0的数据插入到容器中
for (map<int, int>::iterator it = m.begin(); it != m.end(); it++)
{
cout << it->first << " " << it->second << endl;
}
}
int main()
{
test();
return 0;
}输出结果
1 10
2 20
3 30
4 403.8.2.5 map删除操作
clear(); //删除所有元素 erase(pos); //删除pos迭代器所指的元素，返回下一个元素的迭代器。 erase(beg,end); //删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。 erase(keyElem); //删除容器中key为keyElem的对组。 |
void PrintMap(map<int, int>& m)
{
for (map<int, int>::iterator it = m.begin(); it != m.end(); it++)
{
cout << it->first << " " << it->second << endl;
}
cout << endl;
}
void test()
{
map<int, int>m;
m.insert(pair<int, int>(1, 10));
m.insert(pair<int, int>(2, 20));
m.insert(pair<int, int>(3, 30));
m.insert(pair<int, int>(4, 40));
PrintMap(m);
//删除
m.erase(4);
PrintMap(m);
}
int main()
{
test();
return 0;
}输出结果
1 10
2 20
3 30
4 40
1 10
2 20
3 303.8.2.6 map查找操作
find(key); //查找键key是否存在,若存在，返回该键的元素的迭代器；/若 不存在，返回 map.end(); count(keyElem); //返回容器中key为keyElem的对组个数。对map来说，要么 是0，要么是1。对multimap来说，值可能大于1。 lower_bound(keyElem); //返回第一个key>=keyElem元素的迭代器。 upper_bound(keyElem); //返回第一个key>keyElem元素的迭代器。 equal_range(keyElem); //返回容器中key与keyElem相等的上下限的两个迭代器。 |
void PrintMap(map<int, int>& m)
{
for (map<int, int>::iterator it = m.begin(); it != m.end(); it++)
{
cout << it->first << " " << it->second << endl;
}
cout << endl;
}
void test01()
{
map<int, int>m;
m.insert(pair<int, int>(1, 10));
m.insert(pair<int, int>(2, 20));
m.insert(pair<int, int>(3, 30));
m.insert(pair<int, int>(4, 40));
PrintMap(m);
map<int, int>::iterator ret = m.find(3);
if (ret != m.end())
{
cout << "找到了 key为 " << ret->first << " value = " << ret->second << endl;
}
else
{
cout << "未找到" << endl;
}
//统计
int num = m.count(4);
cout << "key为4的对组个数为： " << num << endl;
//lower_bound(keyElem),返回第一个key>=keyElem元素的迭代器
map<int, int>::iterator pos = m.lower_bound(3);
if (pos != m.end())
{
cout << "找到了lower_bound key: " << pos->first << " value: " << pos->second << endl;
}
else
{
cout << "未找到" << endl;
}
//upper_bound(keyElem),返回第一个key>keyElem元素的迭代器
pos = m.upper_bound(3);
if (pos != m.end())
{
cout << "找到了upper_bound key: " << pos->first << " value: " << pos->second << endl;
}
else
{
cout << "未找到" << endl;
}
//equal_range(keyElem),返回容器中key与keyElem相等的上下限的两个迭代器
pair<map<int, int>::iterator, map<int, int>::iterator> ret02 = m.equal_range(3);
if (ret02.first != m.end())
{
cout << "找到了equal_range中的 lower_bound的 key = " << ret02.first->first << " value" << ret02.first->second << endl;
}
else
{
cout << "未找到" << endl;
}
if (ret02.second != m.end())
{
cout << "找到了equal_range中的 upper_bound的 key = " << ret02.second->first << " value" << ret02.second->second << endl;
}
else
{
cout << "未找到" << endl;
}
}
class myCompareInt
{
public:
bool operator()(int v1, int v2) const
{
return v1 > v2;
}
};
void test02()
{
map<int, int, myCompareInt>m;
m.insert(pair<int, int>(1, 10));
m.insert(pair<int, int>(2, 20));
m.insert(pair<int, int>(3, 30));
m.insert(pair<int, int>(4, 40));
for (map<int, int, myCompareInt>::iterator it = m.begin(); it != m.end(); it++)
{
cout << "key = " << it->first << " value = " << it->second << endl;
}
}
int main()
{
test01();
test02();
return 0;
}输出结果
4 40
找到了 key为 3 value = 30
key为4的对组个数为： 1
找到了lower_bound key: 3 value: 30
找到了upper_bound key: 4 value: 40
找到了equal_range中的 lower_bound的 key = 3 value30
找到了equal_range中的 upper_bound的 key = 4 value40
key = 4 value = 40
key = 3 value = 30
key = 2 value = 20
key = 1 value = 103.8.3 multimap案例
公司今天招聘了5个员工，5名员工进入公司之后，需要指派员工在哪个部门工作，人员信息有: 姓名 年龄 电话 工资等组成。通过Multimap进行信息的插入 保存 显示。
enum
{ CAIWU,
RENLI,
YANFA
};
class Worker
{
public:
string Name;
int Money;
};
void createWorker(vector<Worker>& v)
{
string nameseed = "ABCDE";
for (int i = 0; i < 5; i++)
{
Worker worker;
worker.Name = "员工";
worker.Name = worker.Name + nameseed[i];
worker.Money = rand() % 10000 + 10000;
v.push_back(worker);
}
}
void setGround(vector<Worker>& v, multimap<int, Worker>& m)
{
for (vector<Worker>::iterator it = v.begin(); it != v.end(); it++)
{
//随机产生部门编号 0 1 2
int did = rand() % 3;
m.insert(make_pair(did, *it));
}
}
void showWorker(multimap<int, Worker>& m)
{
cout << "财务部门员工信息如下：" << endl;
multimap<int, Worker>::iterator pos = m.find(CAIWU);
int num = m.count(CAIWU);
int index = 0;
for (index = 0; pos != m.end(), index < num; pos++, index++)
{
cout << "姓名：" << pos->second.Name << " 工资：" << pos->second.Money << endl;
}
cout << endl;
cout << "人力部门员工信息如下：" << endl;
pos = m.find(RENLI);
num = m.count(RENLI);
index = 0;
for (index = 0; pos != m.end(), index < num; pos++, index++)
{
cout << "姓名：" << pos->second.Name << " 工资：" << pos->second.Money << endl;
}
cout << endl;
cout << "研发部门员工信息如下：" << endl;
pos = m.find(YANFA);
num = m.count(YANFA);
index = 0;
for (index = 0; pos != m.end(), index < num; pos++, index++)
{
cout << "姓名：" << pos->second.Name << " 工资：" << pos->second.Money << endl;
}
}
int main()
{
//随机数种子
srand((unsigned int)time(NULL));
vector<Worker>v;
//1.创建5名员工
createWorker(v);
//2.员工分组
multimap<int, Worker>m;
setGround(v, m);
//3.分部门显示员工
showWorker(m);
return 0;
}输出结果
财务部门员工信息如下：
姓名：员工C 工资：11178
人力部门员工信息如下：
姓名：员工A 工资：13616
姓名：员工D 工资：18411
研发部门员工信息如下：
姓名：员工B 工资：10631
姓名：员工E 工资：184773.9 STL容器使用时机
vector |
deque |
list |
set |
multiset |
map |
multimap |
|
典型内存结构 |
单端数组 |
双端数组 |
双向链表 |
二叉树 |
二叉树 |
二叉树 |
二叉树 |
可随机存取 |
是 |
是 |
否 |
否 |
否 |
对key而言：不是 |
否 |
元素搜寻速度 |
慢 |
慢 |
非常慢 |
快 |
快 |
对key而言：快 |
对key而言：快 |
元素安插移除 |
尾端 |
头尾两端 |
任何位置 |
- |
- |
- |
- |
- vector的使用场景：比如软件历史操作记录的存储，我们经常要查看历史记录，比如上一次的记录，上上次的记录，但却不会去删除记录，因为记录是事实的描述。
- deque的使用场景：比如排队购票系统，对排队者的存储可以采用deque，支持头端的快速移除，尾端的快速添加。如果采用vector，则头端移除时，会移动大量的数据，速度慢。
vector与deque的比较：
1）：vector.at()比deque.at()效率高，比如vector.at(0)是固定的，deque的开始位置 却是不固定的。
2）：如果有大量释放操作的话，vector花的时间更少，这跟二者的内部实现有关。
3）：deque支持头部的快速插入与快速移除，这是deque的优点。
- list的使用场景：比如公交车乘客的存储，随时可能有乘客下车，支持频繁的不确实位置元素的移除插入。
- set的使用场景：比如对手机游戏的个人得分记录的存储，存储要求从高分到低分的顺序排列。
- map的使用场景：比如按ID号存储十万个用户，想要快速要通过ID查找对应的用户。二叉树的查找效率，这时就体现出来了。如果是vector容器，最坏的情况下可能要遍历完整个容器才能找到该用户。