C++基础知识（六）之STL容器

二十、STL容器 1、string容器

string是字符容器，内部维护了一个动态的字符数组。

与普通的字符数组相比，string容器有三个优点：1）使用的时候，不必考虑内存分配和释放的问题；2）动态管理内存（可扩展）；3）提供了大量操作容器的API。缺点是效率略有降低，占用的资源也更多。

string类是std::basic_string类模板的一个具体化版本的别名。

using std::string=std::basic_string<char, std::char_traits<char>, std::allocator<char>> 1）构造和析构

静态常量成员string::npos为字符数组的最大长度（通常为unsigned int的最大值）；

NBTS（null-terminated string）：C风格的字符串（以空字符0结束的字符串）。

string类有七个构造函数（C++11新增了两个）：

1）string(); // 创建一个长度为0的string对象（默认构造函数）。

2）string(const char *s); // 将string对象初始化为s指向的NBTS（转换函数）。

3）string(const string &str); // 将string对象初始化为str（拷贝构造函数）。

4）string(const char *s,size_t n); // 将string对象初始化为s指向的地址后n字节的内容。

5）string(const string &str,size_t pos=0,size_t n=npos); // 将sring对象初始化为str从位置pos开始到结尾的字符（或从位置pos开始的n个字符）。

6）template<class T> string(T begin,T end); // 将string对象初始化为区间[begin,end]内的字符，其中begin和end的行为就像指针，用于指定位置，范围包括begin在内，但不包括end。

7）string(size_t n,char c); // 创建一个由n个字符c组成的string对象。

析构函数~string()释放内存空间。

C++11新增的构造函数：

1）string(string && str) noexcept：它将一个string对象初始化为string对象str，并可能修改str（移动构造函数）。

2）string(initializer_list<char> il)：它将一个string对象初始化为初始化列表il中的字符。

例如：string ss = { 'h','e','l','l','o' };

#include <iostream> using namespace std; int main() { // 1）string()：创建一个长度为0的string对象（默认构造函数）。 string s1; // 创建一个长度为0的string对象 cout << "s1=" << s1 << endl; // 将输出s1= cout << "s1.capacity()=" << s1.capacity() << endl; // 返回当前容量，可以存放字符的总数。 cout << "s1.size()=" << s1.size() << endl; // 返回容器中数据的大小。 cout << "容器动态数组的首地址=" << (void *)s1.c_str() << endl; s1 = "xxxxxxxxxxxxxxxxxxxx"; cout << "s1.capacity()=" << s1.capacity() << endl; // 返回当前容量，可以存放字符的总数。 cout << "s1.size()=" << s1.size() << endl; // 返回容器中数据的大小。 cout << "容器动态数组的首地址=" << (void *)s1.c_str() << endl; // 2）string(const char *s)：将string对象初始化为s指向的NBTS（转换函数）。 string s2("hello world"); cout << "s2=" << s2 << endl; // 将输出s2=hello world string s3 = "hello world"; cout << "s3=" << s3 << endl; // 将输出s3=hello world // 3）string(const string & str)：将string对象初始化为str（拷贝构造函数）。 string s4(s3); // s3 = "hello world"; cout << "s4=" << s4 << endl; // 将输出s4=hello world string s5 = s3; cout << "s5=" << s5 << endl; // 将输出s5=hello world // 4）string(const char* s, size_t n)：将string对象初始化为s指向的NBTS的前n个字符，即使超过了NBTS结尾。 string s6("hello world", 5); cout << "s6=" << s6 << endl; // 将输出s6=hello cout << "s6.capacity()=" << s6.capacity() << endl; // 返回当前容量，可以存放字符的总数。 cout << "s6.size()=" << s6.size() << endl; // 返回容器中数据的大小。 string s7("hello world", 50); cout << "s7=" << s7 << endl; // 将输出s7=hello未知内容 cout << "s7.capacity()=" << s7.capacity() << endl; // 返回当前容量，可以存放字符的总数。 cout << "s7.size()=" << s7.size() << endl; // 返回容器中数据的大小。 // 5）string(const string & str, size_t pos = 0, size_t n = npos)： // 将string对象初始化为str从位置pos开始到结尾的字符，或从位置pos开始的n个字符。 string s8(s3, 3, 5); // s3 = "hello world"; cout << "s8=" << s8 << endl; // 将输出s8=lo wo string s9(s3, 3); cout << "s9=" << s9 << endl; // 将输出s9=lo world cout << "s9.capacity()=" << s9.capacity() << endl; // 返回当前容量，可以存放字符的总数。 cout << "s9.size()=" << s9.size() << endl; // 返回容器中数据的大小。 string s10("hello world", 3, 5); cout << "s10=" << s10 << endl; // 将输出s10=lo wo string s11("hello world", 3); // 注意：不会用构造函数5），而是用构造函数4） cout << "s11=" << s11 << endl; // 将输出s11=hel // 6）template<class T> string(T begin, T end)：将string对象初始化为区间[begin, end]内的字符， // 其中begin和end的行为就像指针，用于指定位置，范围包括begin在内，但不包括end。 // 7）string(size_t n, char c)：创建一个由n个字符c组成的string对象。 string s12(8, 'x'); cout << "s12=" << s12 << endl; // 将输出s12=xxxxxxxx cout << "s12.capacity()=" << s12.capacity() << endl; // s12.capacity()=15 cout << "s12.size()=" << s12.size() << endl; // s12.size()=8 string s13(30, 0); cout << "s13=" << s13 << endl; // 将输出s13= cout << "s13.capacity()=" << s13.capacity() << endl; // s13.capacity()=31 cout << "s13.size()=" << s13.size() << endl; // s12.size()=30 }

容器动态数组的首地址=0000008D4B90F3E0 s1.capacity()=31 s1.size()=20 容器动态数组的首地址=0000026121FD9530 s2=hello world s3=hello world s4=hello world s5=hello world s6=hello s6.capacity()=15 s6.size()=5 s7=hello worlds2=s3=s4=s5=s6=s6.capacit s7.capacity()=63 s7.size()=50 s8=lo wo s9=lo world s9.capacity()=15 s9.size()=8 s10=lo wo s11=hel s12=xxxxxxxx s12.capacity()=15 s12.size()=8 s13= s13.capacity()=31 s13.size()=30

#define _CRT_SECURE_NO_WARNINGS #include <iostream> using namespace std; int main() { char cc[8]; // 在栈上分配8字节的内存空间。 // 把cc的内存空间用于字符串。 strcpy(cc, "hello"); cout << "cc=" << cc << endl << endl; // 把cc的内存空间用于int型整数。 int* a, * b; a = (int*)cc; // 前4个字节的空间用于整数a。 b = (int*)cc + 4; // 后4个字节的空间用于整数b。 *a = 12345; *b = 54321; cout << "*a=" << *a << endl; cout << "*b=" << *b << endl << endl; // 把cc的内存空间用于double。 double* d = (double*)cc; *d = 12345.7; cout << "*d=" << *d << endl << endl; // 把cc的内存空间用于结构体。 struct stt { int a; char b[4]; }*st; st = (struct stt*)cc; st->a = 38; strcpy(st->b, "abc"); cout << "st->a=" << st->a << endl; cout << "st->b=" << st->b << endl << endl; // void* malloc(size_t size); //char* cc1 = (char*)malloc(8); //int* cc1 = (int*)malloc(8); }

cc=hello

*a=12345 *b=54321

*d=12345.7

st->a=38 st->b=abc

#define _CRT_SECURE_NO_WARNINGS #include <iostream> using namespace std; int main() { struct st_girl { // 超女结构体。 int bh; char name[30]; bool yz; double weight; string memo; } girl; cout << "超女结构体的大小：" << sizeof(struct st_girl) << endl; string buffer; // 创建一个空的string容器buffer。 // 生成10名超女的信息，存入buffer中。 for (int ii = 1; ii <= 10; ii++) { // 对超女结构体成员赋值。 memset(&girl, 0, sizeof(struct st_girl)); girl.bh = ii; sprintf(girl.name, "西施%02d", ii); girl.yz = true; girl.weight = 48.5 + ii; girl.memo = "中国历史第一美女。"; // 把超女结构追加到buffer中。 buffer.append((char*)&girl, sizeof(struct st_girl)); } cout << "buffer.capacity()=" << buffer.capacity() << endl; // 显示容量。 cout << "buffer.size()=" << buffer.size() << endl; // 显示实际大小。 // 用一个循环，把buffer容器中全部的数据取出来。 for (int ii = 0; ii < buffer.size() / sizeof(struct st_girl); ii++) { memset(&girl, 0, sizeof(struct st_girl)); // 初始化超女结构体。 // 把容器中的数据复制到超女结构体。 memcpy(&girl , buffer.data() + ii * sizeof(struct st_girl), sizeof(struct st_girl)); // buffer.copy((char*)&girl, sizeof(struct st_girl), ii * sizeof(struct st_girl)); // 显示超女结构体成员的值。 cout << "bh=" << girl.bh << ",name=" << girl.name << ",yz=" << girl.yz << ",weight=" << girl.weight << ",memo=" << girl.memo << endl; } }

超女结构体的大小：88 buffer.capacity()=964 buffer.size()=880 bh=1,name=西施01,yz=1,weight=49.5,memo=中国历史第一美女。 bh=2,name=西施02,yz=1,weight=50.5,memo=中国历史第一美女。 bh=3,name=西施03,yz=1,weight=51.5,memo=中国历史第一美女。 bh=4,name=西施04,yz=1,weight=52.5,memo=中国历史第一美女。 bh=5,name=西施05,yz=1,weight=53.5,memo=中国历史第一美女。 bh=6,name=西施06,yz=1,weight=54.5,memo=中国历史第一美女。 bh=7,name=西施07,yz=1,weight=55.5,memo=中国历史第一美女。 bh=8,name=西施08,yz=1,weight=56.5,memo=中国历史第一美女。 bh=9,name=西施09,yz=1,weight=57.5,memo=中国历史第一美女。 bh=10,name=西施10,yz=1,weight=58.5,memo=中国历史第一美女。

2）特性操作

size_t max_size() const; // 返回string对象的最大长度string::npos，此函数意义不大。

size_t capacity() const; // 返回当前容量，可以存放字符的总数。

size_t length() const; // 返回容器中数据的大小（字符串语义）。

size_t size() const; // 返回容器中数据的大小（容器语义）。

bool empty() const; // 判断容器是否为空。

void clear(); // 清空容器，清空后，size()将返回0。

void shrink_to_fit(); // 将容器的容量降到实际大小（需要重新分配内存）。

void reserve( size_t size=0); // 将容器的容量设置为至少size。

void resize(size_t len,char c=0); // 把容器的实际大小置为len，如果len<实际大小，会截断多出的部分；如果len>实际大小，就用字符c填充。resize()后，length()和size()将返回len。

3）字符操作

char &operator;

const char &operator const; // 只读。

char &at(size_t n);

const char &at(size_t n) const; // 只读。

operator[]和at()返回容器中的第n个元素，但at函数提供范围检查，当越界时会抛出out_of_range异常，operator[]不提供范围检查。

const char *c_str() const; // 返回容器中动态数组的首地址，语义：寻找以null结尾的字符串。

const char *data() const; // 返回容器中动态数组的首地址，语义：只关心容器中的数据。

int copy(char *s, int n, int pos = 0) const; // 把当前容器中的内容，从pos开始的n个字节拷贝到s中，返回实际拷贝的数目。

4）赋值操作

给已存在的容器赋值，将覆盖容器中原有的内容。

1）string &operator=(const string &str); // 把容器str赋值给当前容器。

2）string &assign(const char *s); // 将string对象赋值为s指向的NBTS。

3）string &assign(const string &str); // 将string对象赋值为str。

4）string &assign(const char *s,size_t n); // 将string对象赋值为s指向的地址后n字节的内容。

5）string &assign(const string &str,size_t pos=0,size_t n=npos); // 将sring对象赋值为str从位置pos开始到结尾的字符（或从位置pos开始的n个字符）。

6）template<class T> string &assign(T begin,T end); // 将string对象赋值为区间[begin,end]内的字符。

7）string &assign(size_t n,char c); // 将string对象赋值为由n个字符c。

5）连接操作

把内容追加到已存在容器的后面。

1）string &operator+=(const string &str); //把容器str连接到当前容器。

2）string &append(const char *s); // 把指向s的NBTS连接到当前容器。

3）string &append(const string &str); // 把容器str连接到当前容器。

4）string &append(const char *s,size_t n); // 将s指向的地址后n字节的内容连接到当前容器。

5）string &append(const string &str,size_t pos=0,size_t n=npos); // 将str从位置pos开始到结尾的字符（或从位置pos开始的n个字符）连接到当前容器。

6）template<class T> string &append (T begin,T end); // 将区间[begin,end]内的字符连接到容器。

7）string &append(size_t n,char c); // 将n个字符c连接到当前容器。

6）交换操作

void swap(string &str); // 把当前容器与str交换。

如果数据量很小，交换的是动态数组中的内容，如果数据量比较大，交换的是动态数组的地址。

7）截取操作

string substr(size_t pos = 0,size_t n = npos) const; // 返回pos开始的n个字节组成的子容器。

8）比较操作

bool operator==(const string &str1,const string &str2) const; // 比较两个字符串是否相等。

int compare(const string &str) const; // 比较当前字符串和str1的大小。

int compare(size_t pos, size_t n,const string &str) const; // 比较当前字符串从pos开始的n个字符组成的字符串与str的大小。

int compare(size_t pos, size_t n,const string &str,size_t pos2,size_t n2)const; // 比较当前字符串从pos开始的n个字符组成的字符串与str中pos2开始的n2个字符组成的字符串的大小。

以下几个函数用于和C风格字符串比较。

int compare(const char *s) const;

int compare(size_t pos, size_t n,const char *s) const;

int compare(size_t pos, size_t n,const char *s, size_t pos2) const;

compre()函数有异常，慎用

9）查找操作

size_t find(const string& str, size_t pos = 0) const;

size_t find(const char* s, size_t pos = 0) const;

size_t find(const char* s, size_t pos, size_t n) const;

size_t find(char c, size_t pos = 0) const;

size_t rfind(const string& str, size_t pos = npos) const;

size_t rfind(const char* s, size_t pos = npos) const;

size_t rfind(const char* s, size_t pos, size_t n) const;

size_t rfind(char c, size_t pos = npos) const;

size_t find_first_of(const string& str, size_t pos = 0) const;

size_t find_first_of(const char* s, size_t pos = 0) const;

size_t find_first_of(const char* s, size_t pos, size_t n) const;

size_t find_first_of(char c, size_t pos = 0) const;

size_t find_last_of(const string& str, size_t pos = npos) const;

size_t find_last_of(const char* s, size_t pos = npos) const;

size_t find_last_of(const char* s, size_t pos, size_t n) const;

size_t find_last_of(char c, size_t pos = npos) const;

size_t find_first_not_of(const string& str, size_t pos = 0) const;

size_t find_first_not_of(const char* s, size_t pos = 0) const;

size_t find_first_not_of(const char* s, size_t pos, size_t n) const;

size_t find_first_not_of(char c, size_t pos = 0) const;

size_t find_last_not_of(const string& str, size_t pos = npos) const;

size_t find_last_not_of(const char* s, size_t pos = npos) const;

size_t find_last_not_of(const char* s, size_t pos, size_t n) const;

size_t find_last_not_of(char c, size_t pos = npos) const;

这些函数都是C++标准库中std::string类的成员函数，用于在字符串中搜索特定字符或子字符串。下面是每个函数的简要说明：

find 函数

size_t find(const string& str, size_t pos = 0) const; 在字符串中从位置pos开始向前搜索子字符串str，返回第一次出现的位置。如果未找到，则返回std::string::npos。

size_t find(const char* s, size_t pos = 0) const; 与上一个函数类似，但搜索的是以空字符结尾的C风格字符串s。

size_t find(const char* s, size_t pos, size_t n) const; 在C风格字符串s的前n个字符中，从位置pos开始向前搜索，返回第一次出现的位置。

size_t find(char c, size_t pos = 0) const; 在字符串中从位置pos开始向前搜索字符c，返回第一次出现的位置。

rfind 函数

这些函数与find函数类似，但搜索方向相反，即从字符串末尾向前搜索。

find_first_of 函数

size_t find_first_of(const string& str, size_t pos = 0) const; 在字符串中从位置pos开始向前搜索，返回在str中任意字符第一次出现的位置。

size_t find_first_of(const char* s, size_t pos = 0) const; 和 size_t find_first_of(const char* s, size_t pos, size_t n) const; 与上一个函数类似，但搜索的是C风格字符串s的前n个字符。

size_t find_first_of(char c, size_t pos = 0) const; 在字符串中从位置pos开始向前搜索字符c，返回第一次出现的位置。

find_last_of 函数

这些函数与find_first_of函数类似，但搜索方向相反，即从字符串末尾向前搜索。

find_first_not_of 函数

size_t find_first_not_of(const string& str, size_t pos = 0) const; 在字符串中从位置pos开始向前搜索，返回第一个不在str中的字符的位置。

size_t find_first_not_of(const char* s, size_t pos = 0) const; 和 size_t find_first_not_of(const char* s, size_t pos, size_t n) const; 与上一个函数类似，但搜索的是C风格字符串s的前n个字符。

size_t find_first_not_of(char c, size_t pos = 0) const; 在字符串中从位置pos开始向前搜索，返回第一个不等于c的字符的位置。

find_last_not_of 函数

这些函数与find_first_not_of函数类似，但搜索方向相反，即从字符串末尾向前搜索。

在所有这些函数中，npos是一个静态成员常量，表示一个不可能的位置，通常用于指示未找到的情况。size_t是一个无符号整数类型，用于表示大小和索引。

10）替换操作

string& replace(size_t pos, size_t len, const string& str);

这个函数用于替换字符串中从位置pos开始、长度为len的子串，将其替换为另一个字符串str。pos是替换开始的起始位置，len是要被替换的子串的长度，str是用于替换的新字符串。函数返回对原字符串的引用，以便进行链式调用。

string& replace(size_t pos, size_t len, const string& str, size_t subpos, size_t sublen = npos);

这个函数也用于替换字符串中的部分内容，但它允许你指定str中的一个子串来进行替换。pos和len参数与上一个函数相同，分别表示替换的起始位置和长度。str是包含替换内容的字符串，subpos是str中要被用作替换内容的子串的起始位置，sublen是要被用作替换的子串的长度。如果sublen是npos（默认值），则使用从subpos开始到str末尾的所有字符。

string& replace(size_t pos, size_t len, const char* s);

这个函数将字符串中从位置pos开始、长度为len的子串替换为以空字符结尾的C风格字符串s。pos和len参数的含义与前面相同，s是要替换进去的新字符串（实际上是C风格字符串）。

string& replace(size_t pos, size_t len, const char* s, size_t n);

这个函数与上一个函数类似，但它允许你指定s中的前n个字符来进行替换。pos和len参数的含义相同，s是要从中取字符的C风格字符串，n是要从s中取出的字符数量。

string& replace(size_t pos, size_t len, size_t n, char c);

这个函数将字符串中从位置pos开始、长度为len的子串替换为n个字符c。pos和len参数的含义与之前相同，n是要插入的新字符的数量，c是要插入的字符。

在这些函数中，npos是一个静态成员常量，表示一个不可能的位置，通常用于指示直到字符串末尾的所有字符。size_t是一个无符号整数类型，用于表示大小和索引。这些函数都返回对原字符串的引用，使得可以在单个表达式中进行多个替换操作。

以下函数意义不大。

string& replace(iterator i1, iterator i2, const string& str);

string& replace(iterator i1, iterator i2, const char* s);

string& replace(iterator i1, iterator i2, const char* s, size_t n);

string& replace(iterator i1, iterator i2, size_t n, char c);

template <class InputIterator>

string& replace(iterator i1, iterator i2, InputIterator first, InputIterator last);

11）插入操作

string& insert(size_t pos, const string& str);

这个函数在字符串str的pos位置插入另一个字符串str的全部内容。pos是插入的起始位置，它必须是一个有效的索引，即在字符串的当前长度范围内（但可以是该范围的最大值，即在字符串末尾插入）。如果pos超出了当前字符串的长度，那么插入操作会在字符串的末尾进行。函数返回对原字符串的引用，以便进行链式调用。

string& insert(size_t pos, const string& str, size_t subpos, size_t sublen = npos);

这个函数在字符串的pos位置插入另一个字符串str的一个子串。pos是插入的起始位置，str是包含要插入内容的字符串，subpos是str中要被插入的子串的起始位置，sublen是要被插入的子串的长度。如果sublen是npos（默认值），则使用从subpos开始到str末尾的所有字符。函数同样返回对原字符串的引用。

string& insert(size_t pos, const char* s);

这个函数在字符串的pos位置插入一个以空字符结尾的C风格字符串s。pos是插入的起始位置，s是要插入的C风格字符串。如果s为nullptr，则行为是未定义的。函数返回对原字符串的引用。

string& insert(size_t pos, const char* s, size_t n);

这个函数与上一个函数类似，但它允许你指定s中的前n个字符来进行插入。pos是插入的起始位置，s是要从中取字符的C风格字符串，n是要从s中取出的字符数量。如果n大于s的长度（不包括空字符），则只插入s中的有效字符。函数返回对原字符串的引用。

string& insert(size_t pos, size_t n, char c);

这个函数在字符串的pos位置插入n个字符c。pos是插入的起始位置，n是要插入的字符数量，c是要插入的字符。这相当于在指定位置重复插入相同的字符多次。函数返回对原字符串的引用。

在这些函数中，npos是一个静态成员常量，表示一个不可能的位置，通常用于指示直到字符串末尾的所有字符。size_t是一个无符号整数类型，用于表示大小和索引。这些插入操作会改变原字符串的内容，并可能增加字符串的长度。由于函数返回对原字符串的引用，因此可以在单个表达式中进行多个插入操作。

以下函数意义不大。

iterator insert(iterator p, size_t n, char c);

iterator insert(iterator p, char c);

template <class InputIterator>

iterator insert(iterator p, InputIterator first, InputIterator last);

12）删除操作

string &erase(size_t pos = 0, size_t n = npos); // 删除pos开始的n个字符。

以下函数意义不大。

iterator erase(iterator it); // 删除it指向的字符，返回删除后迭代器的位置。

iterator erase(iterator first, iterator last); / /删除[first，last）之间的所有字符，返回删除后迭代器的位置。

2、vector容器

vector容器封装了动态数组。

包含头文件： #include<vector>

vector类模板的声明：

template<class T, class Alloc = allocator<T>> class vector{ private: T *start_; T *finish_; T *end_; …… }

分配器

各种STL容器模板都接受一个可选的模板参数，该参数指定使用哪个分配器对象来管理内存

如果省略该模板参数的值，将默认使用allocator<T>，用new和delete分配和释放内存。

1）构造函数

1）vector(); // 创建一个空的vector容器。

2）vector(initializer_list<T> il); // 使用统一初始化列表。

3）vector(const vector<T>& v); // 拷贝构造函数。

4）vector(Iterator first, Iterator last); // 用迭代器创建vector容器。

5）vector(vector<T>&& v); // 移动构造函数（C++11标准）。

6）explicit vector(const size_t n); // 创建vector容器，元素个数为n（容量和实际大小都是n）。

7）vector(const size_t n, const T& value); // 创建vector容器，元素个数为n，值均为value。

析构函数~vector()释放内存空间。

2）特性操作

size_t max_size() const; // 返回容器的最大长度，此函数意义不大。

size_t capacity() const; // 返回容器的容量。

size_t size() const; // 返回容器的实际大小（已使用的空间）。

bool empty() const; // 判断容器是否为空。

void clear(); // 清空容器。

void reserve(size_t size); // 将容器的容量设置为至少size。

void shrink_to_fit(); // 将容器的容量降到实际大小（需要重新分配内存）。

void resize(size_t size); // 把容器的实际大小置为size。

void resize(size_t size,const T &value); // 把容器的实际大小置为size，如果size<实际大小，会截断多出的部分；如果size>实际大小，就用value填充。

3）元素操作

T &operator;

const T &operator const; // 只读。

T &at(size_t n);

const T &at(size_t n) const; // 只读。

T *data(); // 返回容器中动态数组的首地址。

const T *data() const; // 返回容器中动态数组的首地址。

T &front(); // 第一个元素。

const T &front(); // 第一个元素，只读。

const T &back(); // 最后一个元素，只读。

T &back(); // 最后一个元素。

4）赋值操作

给已存在的容器赋值，将覆盖容器中原有的内容。

1）vector &operator=(const vector<T> &v); // 把容器v赋值给当前容器。

2）vector &operator=(initializer_list<T> il); // 用统一初始化列表给当前容器赋值。

3）void assign(initializer_list<T> il); // 使用统一初始化列表赋值。

4）void assign(Iterator first, Iterator last); // 用迭代器赋值。

5）void assign(const size_t n, const T& value); // 把n个value给容器赋值。

示例：

#include <iostream> #include <vector> using namespace std; int main() { vector<int> v1; v1 = { 1,2,3,4,5 }; // 使用统一初始化列表赋值。 for (int ii = 0; ii < v1.size(); ii++) cout << v1[ii] << " "; cout << endl; vector<int> v2; v2 = v1; // 把容器v1赋值给当前容器。 for (int ii = 0; ii < v2.size(); ii++) cout << v2[ii] << " "; cout << endl; vector<int> v3; v3.assign({ 1,2,3,4,5 }); // 用assign()函数给当前容器赋值，参数是统一初始化列表。 for (int ii = 0; ii < v3.size(); ii++) cout << v3[ii] << " "; cout << endl; } 5）交换操作

void swap(vector<T> &v); // 把当前容器与v交换。

交换的是动态数组的地址。

6）比较操作

bool operator == (const vector<T> & v) const;

bool operator != (const vector<T> & v) const;

7）插入和删除

1）void push_back(const T& value); // 在容器的尾部追加一个元素。

2）void emplace_back(…); // 在容器的尾部追加一个元素，…用于构造元素。C++11

3）iterator insert(iterator pos, const T& value); // 在指定位置插入一个元素，返回指向插入元素的迭代器。

4）iterator emplace (iterator pos, …); // 在指定位置插入一个元素，…用于构造元素，返回指向插入元素的迭代器。C++11

5）iterator insert(iterator pos, iterator first, iterator last); // 在指定位置插入一个区间的元素，返回指向第一个插入元素的迭代器。

6）void pop_back(); // 从容器尾部删除一个元素。

7）iterator erase(iterator pos); // 删除指定位置的元素，返回下一个有效的迭代器。

8）iterator erase(iterator first, iterator last); // 删除指定区间的元素，返回下一个有效的迭代器。

示例：

#include <iostream> #include <vector> using namespace std; class AA { public: int m_bh; // 编号。 string m_name; // 姓名。 AA() // 默认构造函数。 { //cout << "默认构造函数AA()。\n"; } AA(const int& bh, const string& name) : m_bh(bh), m_name(name) // 有两个参数的构造函数。 { //cout << "构造函数，name=" << m_name << "。\n"; } AA(const AA& g) :m_bh(g.m_bh), m_name(g.m_name) // 拷贝构造函数。 { //cout << "拷贝构造函数，name=" << m_name << "。\n"; } //~AA() { cout << "析构函数。\n"; } }; int main() { vector<AA> v(10); cout << v.size() << v.data() << endl; //AA a(18,"西施"); //v.push_back(a); //v.emplace_back(a); v.emplace_back(18, "西施"); cout << "bh=" << v[0].m_bh << ",name=" << v[0].m_name << endl; }

10000002860DEA72E0

bh=-842150451,name=

8）vector的嵌套

vector容器可以嵌套使用。

示例：

#include <iostream> #include <vector> using namespace std; int main() { vector<vector<int>> vv; // 创建一个vector容器vv，元素的数据类型是vector<int>。 vector<int> v; // 创建一个容器v，它将作为容器vv的元素。 v = { 1,2,3,4,5 }; // 用统一初始化列表给v赋值。 vv.push_back(v); // 把容器v作为元素追加到vv中。 v = { 11,12,13,14,15,16,17 }; // 用统一初始化列表给v赋值。 vv.push_back(v); // 把容器v作为元素追加到vv中。 v = { 21,22,23 }; // 用统一初始化列表给v赋值。 vv.push_back(v); // 把容器v作为元素追加到vv中。 // 用嵌套的循环，把vv容器中的数据显示出来。 for (int ii = 0; ii < vv.size(); ii++) { for (int jj = 0; jj < vv[ii].size(); jj++) cout << vv[ii][jj] << " "; // 像二维数组一样使用容器vv。 cout << endl; } }

1 2 3 4 5 11 12 13 14 15 16 17 21 22 23

9）注意事项

迭代器失效的问题

resize()、reserve()、assign()、push_back()、pop_back()、insert()、erase()等函数会引起vector容器的动态数组发生变化，可能导致vector迭代器失效。

3、迭代器

迭代器是访问容器中元素的通用方法。

如果使用迭代器，不同的容器，访问元素的方法是相同的。

迭代器支持的基本操作：赋值（=）、解引用（*）、比较（==和!=）、从左向右遍历（++）。

一般情况下，迭代器是指针和移动指针的方法。

迭代器有五种分类：

1）正向迭代器

只能使用++运算符从左向右遍历容器，每次沿容器向右移动一个元素。

容器名<元素类型>::iterator 迭代器名; // 正向迭代器。

容器名<元素类型>::const_iterator 迭代器名; // 常正向迭代器。

相关的成员函数：

iterator begin(); const_iterator begin(); const_iterator cbegin(); // 配合auto使用。 iterator end(); const_iterator end(); const_iterator cend();

2）双向迭代器

具备正向迭代器的功能，还可以反向（从右到左）遍历容器（也是用++），不管是正向还是反向遍历，都可以用--让迭代器后退一个元素。

容器名<元素类型>:: reverse_iterator 迭代器名; // 反向迭代器。

容器名<元素类型>:: const_reverse_iterator 迭代器名; // 常反向迭代器。

相关的成员函数：

reverse_iterator rbegin(); const_reverse_iterator crbegin(); reverse_iterator rend(); const_reverse_iterator crend();

3）随机访问迭代器

具备双向迭代器的功能，还支持以下操作：

用于比较两个迭代器相对位置的关系运算（<、<=、>、>=）。

迭代器和一个整数值的加减法运算（+、+=、-、-=）。

支持下标运算（iter[n]）。

数组的指针是纯天然的随机访问迭代器。

4）输入和输出迭代器

这两种迭代器比较特殊，它们不是把容器当做操作对象，而是把输入/输出流作为操作对象。

#include <iostream> #include <vector> #include <list> using namespace std; struct Node // 单链表的结点。 { int item; Node* next; }; int* find_(int* arr, int n, const int& val) // 在整型数组arr中查找值为val的元素。 { for (int ii = 0; ii < n; ii++) // 遍历数组。 if (arr[ii] == val) return &arr[ii]; // 如果找到了，返回数组中元素的地址。 return nullptr; } int* find_(int* begin, int* end, const int& val) // 在整型数组的区间中查找值为val的元素。 { for (int* iter = begin; iter != end; iter++) // 遍历查找区间。 if (*iter == val) return iter; // 如果找到了元素，返回区间中的位置。 return nullptr; } Node* find_(Node* begin, Node* end, const Node& val) // 在单链表中查找值为val的元素。 { for (Node * iter = begin; iter != end; iter = iter->next) // 遍历链表。 if (iter->item == val.item) return iter; // 如果找到了，返回链表中结点的地址。 return nullptr; } // 查找元素的算法。 template<typename T1, typename T2> // begin-查找区间开始的位置；end-查找区间结束的位置；val-待查找的值。 T1 find_(T1 begin, T1 end, const T2 &val) { for (T1 iter = begin; iter != end; iter++) // 遍历查找区间。 if (*iter == val) return iter; // 如果找到了元素，返回区间中的位置。 return end; } int main() { // 在vector容器中查找元素。 vector<int> vv = { 1,2,3,4,5 }; // 初始化vector容器。 vector<int>::iterator it2 = find_(vv.begin(), vv.end(), 3); if (it2 != vv.end()) cout << "查找成功。\n"; else cout << "查找失败。\n"; // 在list容器中查找元素。 list<int> ll = {1,2,3,4,5}; // 初始化vector容器。 list<int>::iterator it3 = find_(ll.begin(), ll.end(), 3); if (it3 != ll.end()) cout << "查找成功。\n"; else cout << "查找失败。\n"; } 4、基于范围的for循环

对于一个有范围的集合来说，在程序代码中指定循环的范围有时候是多余的，还可能犯错误。

C++11中引入了基于范围的for循环。

语法：

for (迭代的变量 : 迭代的范围)

{

// 循环体。

}

注意：

1）迭代的范围可以是数组名、容器名、初始化列表或者可迭代的对象（支持begin()、end()、++、==）。

2）数组名传入函数后，已退化成指针，不能作为容器名。

3）如果容器中的元素是结构体和类，迭代器变量应该申明为引用，加const约束表示只读。

4）注意迭代器失效的问题。

示例：

#include <iostream> #include <vector> using namespace std; class AA { public: string m_name; AA() { cout << "默认构造函数AA()。\n"; } AA(const string& name) : m_name(name) { cout << "构造函数，name=" << m_name << "。\n"; } AA(const AA& a) : m_name(a.m_name) { cout << "拷贝构造函数，name=" << m_name << "。\n"; } AA& operator=(const AA& a) { m_name = a.m_name; cout << "赋值函数，name=" << m_name << "。\n"; return *this; } ~AA() { cout << "析构函数，name=" << m_name<<"。\n"; } }; int main() { vector<int> vv = { 1,2,3,4,5,6,7,8,9,10 }; //for (auto it = vv.begin(); it != vv.end(); it++) // 用迭代器遍历容器vv。 //{ // cout << *it << " "; //} //cout << endl; for (auto val : vv) // 用基于范围的for循环遍历数组vv。 { cout << val << " "; vv.push_back(10); } cout << endl; /*vector<AA> v; cout << "1111，v.capacity()=" << v.capacity() << "\n"; v.emplace_back("西施"); cout << "2222，v.capacity()=" << v.capacity() << "\n"; v.emplace_back("冰冰"); cout << "3333，v.capacity()=" << v.capacity() << "\n"; v.emplace_back("幂幂"); cout << "4444，v.capacity()=" << v.capacity() << "\n"; for (const auto &a : v) cout << a.m_name << " "; cout << endl;*/ }

1 -572662307 -572662307 -572662307 -572662307 -572662307 -572662307 -572662307 -572662307 -572662307

5、list容器

list容器封装了双链表。

包含头文件： #include<list>

list类模板的声明：

template<class T, class Alloc = allocator<T>> class list{ private: iterator head; iterator tail; …… } 1）构造函数

1）list(); // 创建一个空的list容器。

2）list(initializer_list<T> il); // 使用统一初始化列表。

3）list(const list<T>& l); // 拷贝构造函数。

4）list(Iterator first, Iterator last); // 用迭代器创建list容器。

5）list(list<T>&& l); // 移动构造函数（C++11标准）。

6）explicit list(const size_t n); // 创建list容器，元素个数为n。

7）list(const size_t n, const T& value); // 创建list容器，元素个数为n，值均为value。

析构函数~list()释放内存空间。

示例：

#include <iostream> #include <vector> #include <list> using namespace std; int main() { // 1）list(); // 创建一个空的list容器。 list<int> l1; // cout << "li.capacity()=" << l1.capacity() << endl; // 链表没有容量说法。 cout << "li.size()=" << l1.size() << endl; // 2）list(initializer_list<T> il); // 使用统一初始化列表。 list<int> l2({ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }); // list<int> l2={ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; // list<int> l2 { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; for (int value : l2) // 用基于范围的for循环遍历容器。 cout << value << " "; cout << endl; // 3）list(const list<T>& l); // 拷贝构造函数。 list<int> l3(l2); // list<int> l3=l2; for (int value : l3) cout << value << " "; cout << endl; // 4）list(Iterator first, Iterator last); // 用迭代器创建list容器。 list<int> l4(l3.begin(), l3.end()); // 用list容器的迭代器。 for (int value : l4) cout << value << " "; cout << endl; vector<int> v1 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; // 创建vector容器。 list<int> l5(v1.begin() + 2, v1.end() - 3); // 用vector容器的迭代器创建list容器。 for (int value : l5) cout << value << " "; cout << endl; int a1[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; // 创建数组。 list<int> l6(a1 + 2, a1 + 10 - 3); // 用数组的指针作为迭代器创建list容器。 for (int value : l6) cout << value << " "; cout << endl; char str[] = "hello world"; // 定义C风格字符串。 string s1(str + 1, str + 7); // 用C风格字符串创建string容器。 for (auto value : s1) // 遍历string容器。 cout << value << " "; cout << endl; cout << s1 << endl; // 以字符串的方式显示string容器。 vector<int> v2(l3.begin(), l3.end()); // 用list迭代器创建vector容器。 for (auto value : v2) // 遍历vector容器。 cout << value << " "; cout << endl; }

li.size()=0 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 3 4 5 6 7 3 4 5 6 7 e l l o   w ello w 1 2 3 4 5 6 7 8 9 10

2）特性操作

size_t max_size() const; // 返回容器的最大长度，此函数意义不大。

size_t size() const; // 返回容器的实际大小（已使用的空间）。

bool empty() const; // 判断容器是否为空。

void clear(); // 清空容器。

void resize(size_t size); // 把容器的实际大小置为size。

void resize(size_t size,const T &value); // 把容器的实际大小置为size，如果size<实际大小，会截断多出的部分；如果size>实际大小，就用value填充。

3）元素操作

T &front(); // 第一个元素。

const T &front(); // 第一个元素，只读。

const T &back(); // 最后一个元素，只读。

T &back(); // 最后一个元素。

4）赋值操作

给已存在的容器赋值，将覆盖容器中原有的内容。

1）list &operator=(const list<T> &l); // 把容器l赋值给当前容器。

2）list &operator=(initializer_list<T> il); // 用统一初始化列表给当前容器赋值。

3）list assign(initializer_list<T> il); // 使用统一初始化列表赋值。

4）list assign(Iterator first, Iterator last); // 用迭代器赋值。

5）void assign(const size_t n, const T& value); // 把n个value给容器赋值。

5）交换、反转、排序、归并

void swap(list<T> &l); // 把当前容器与l交换，交换的是链表结点的地址。

void reverse(); // 反转链表。

void sort(); // 对容器中的元素进行升序排序。

void sort(Pr2 _Pred); // 对容器中的元素进行排序，排序的方法由Pred决定（二元函数）。

void merge(list<T> &l); // 采用归并法合并两个已排序的list容器，合并后的list容器仍是有序的。

示例：

#include <iostream> #include <vector> #include <list> using namespace std; int main() { list<int> la = { 8,2,6,4,5 }; for (auto &val : la) cout << val << " "; cout << endl; la.reverse(); // 反转链表。 for (auto& val : la) cout << val << " "; cout << endl; la.sort(); // 链表排序。 for (auto& val : la) cout << val << " "; cout << endl; list<int> lb = { 3,7,9,10,1 }; lb.sort(); // 链表排序。 la.merge(lb); // 归并链表。 for (auto& val : la) cout << val << " "; cout << endl; }

8 2 6 4 5 5 4 6 2 8 2 4 5 6 8 1 2 3 4 5 6 7 8 9 10

6）比较操作

bool operator == (const vector<T> & l) const;

bool operator != (const vector<T> & l) const;

7）插入和删除

1）void push_back(const T& value); // 在链表的尾部追加一个元素。

2）void emplace_back(…); // 在链表的尾部追加一个元素，…用于构造元素。C++11

3）iterator insert(iterator pos, const T& value); // 在指定位置插入一个元素，返回指向插入元素的迭代器。

4）iterator emplace (iterator pos, …); // 在指定位置插入一个元素，…用于构造元素，返回指向插入元素的迭代器。C++11

5）iterator insert(iterator pos, iterator first, iterator last); // 在指定位置插入一个区间的元素，返回指向第一个插入元素的迭代器。

6）void pop_back(); // 从链表尾部删除一个元素。

7）iterator erase(iterator pos); // 删除指定位置的元素，返回下一个有效的迭代器。

8）iterator erase(iterator first, iterator last); // 删除指定区间的元素，返回下一个有效的迭代器。

9）push_front(const T& value); // 在链表的头部插入一个元素。

10）emplace_front(…); // 在链表的头部插入一个元素，…用于构造元素。C++11

11）splice(iterator pos, const vector<T> & l); // 把另一个链表连接到当前链表。

12）splice(iterator pos, const vector<T> & l, iterator first, iterator last); // 把另一个链表指定的区间连接到当前链表。

13）splice(iterator pos, const vector<T> & l, iterator first); // 把另一个链表从first开始的结点连接到当前链表。

14）void remove(const T& value); // 删除链表中所有值等于value的元素。

15）void remove_if(Pr1 _Pred); // 删除链表中满足条件的元素，参数Pred是一元函数。

16）void unique(); // 删除链表中相邻的重复元素，只保留一个。

17）void pop_front(); // 从链表头部删除一个元素。

示例：

#include <iostream> #include <vector> #include <list> using namespace std; int main() { list<int> la = { 8,2,6,4,5 }; for (auto& val : la) cout << val << " "; cout << endl; list<int> lb = { 3,7,9,10,1 }; for (auto& val : lb) cout << val << " "; cout << endl; auto first = lb.begin(); first++; auto last = lb.end(); last--; la.splice(la.begin(), lb, first, last); for (auto& val : la) cout << val << " "; cout << endl; cout << "lb.size()=" << lb.size() << endl; for (auto& val : lb) cout << val << " "; cout << endl; }

8 2 6 4 5 3 7 9 10 1 7 9 10 8 2 6 4 5 lb.size()=2 3 1

8）list容器的简单实现

以下demo程序简单的实现了list容器。

示例：

#include<iostream> using namespace std; namespace { template<class _Ty> class List; template<class _Ty> class ListIterator; // 节点类。 template<class _Ty> class ListNode { friend class List<_Ty>; friend class ListIterator<_Ty>; public: ListNode() :_Value(_Ty()), _Next(nullptr), _Prev(nullptr) {} ListNode(_Ty V, ListNode* next = nullptr, ListNode* prev = nullptr) :_Value(V), _Next(next), _Prev(prev) {} private: _Ty _Value; ListNode* _Next; ListNode* _Prev; }; // 迭代器。 template<class _Ty> class ListIterator { typedef ListIterator<_Ty> _It; public: ListIterator() :_Ptr(nullptr) {} ListIterator(ListNode<_Ty>* _P) :_Ptr(_P) {} public: _It& operator++() { _Ptr = _Ptr->_Next; return *this; } _It& operator--() { _Ptr = _Ptr->Prev; return *this; } _Ty& operator*() { return (_Ptr->_Value); } bool operator!=(const _It& it) { return _Ptr != it._Ptr; } bool operator==(const _It& it) { return _Ptr == it._Ptr; } ListNode<_Ty>* _Mynode() { return _Ptr; } private: ListNode<_Ty>* _Ptr; }; // 链表类。 template<class _Ty> class List { public: typedef ListNode<_Ty>* _Nodeptr; typedef ListIterator<_Ty> iterator; public: List() :_Size(0) { CreateHead(); } List(size_t n, const _Ty& x = _Ty()) :_Size(0) { CreateHead(), insert(begin(), n, x); } List(const _Ty* first, const _Ty* last) :_Size(0) { CreateHead(); while (first != last) push_back(*first++); } List(iterator first, iterator last) { CreateHead(); while (first != last) { push_back(*first); ++first; } } List(List<_Ty>& lt) :_Size(0) { CreateHead(); List<_Ty>tmp(lt.begin(), lt.end()); this->swap(tmp); } ~List() { clear(); delete _Head; _Size = 0; } public: void push_back(const _Ty& x) { insert(end(), x); } void pop_back() { erase(--end()); } void push_front(const _Ty& x) { insert(begin(), x); } void pop_front() { erase(begin()); } _Ty& front() { return *begin(); } const _Ty& front()const { return *begin(); } _Ty& back() { return *--end(); } const _Ty& back()const { return *--end(); } public: size_t size()const { return _Size; } bool empty()const { return (size() == 0); } public: iterator begin() { return iterator(_Head->_Next); } iterator end() { return iterator(_Head); } void clear() { erase(begin(), end()); } public: //在_P位置前插入值为x的节点 iterator insert(iterator _P, const _Ty& x) { _Nodeptr cur = _P._Mynode(); _Nodeptr _S = new ListNode<_Ty>(x); _S->_Next = cur; _S->_Prev = cur->_Prev; _S->_Prev->_Next = _S; _S->_Next->_Prev = _S; _Size++; return iterator(_S); } void insert(iterator _P, size_t n, const _Ty& x = _Ty()) { while (n--) insert(_P, x); } //删除_P位置的节点，返回该节点的下一个节点位置 iterator erase(iterator _P) { _Nodeptr cur = _P._Mynode(); _Nodeptr next_node = cur->_Next; cur->_Prev->_Next = cur->_Next; cur->_Next->_Prev = cur->_Prev; delete cur; _Size--; return iterator(next_node); } iterator erase(iterator first, iterator last) { while (first != last) { first = erase(first); } return first; } void swap(List<_Ty>& lt) { std::swap(_Head, lt._Head); std::swap(_Size, lt._Size); } protected: void CreateHead() { _Head = new ListNode<_Ty>; _Head->_Prev = _Head->_Next = _Head; } private: _Nodeptr _Head; size_t _Size; }; }; int main() { int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; List<int>la(arr+2, arr + 10); List<int>lb(la); for (auto elem:la) cout << elem << " "; //3 4 5 6 7 8 9 10 cout << endl; for (auto elem : lb) cout << elem << " "; //3 4 5 6 7 8 9 10 cout << endl; } 6、pair键值对

pair是类模板，一般用于表示key/value数据，其实现是结构体。

pair结构模板的定义如下：

template <class T1, class T2> struct pair { T1 first; // 第一个成员，一般表示key。 T2 second; // 第二个成员，一般表示value。 pair(); // 默认构造函数。 pair(const T1 &val1,const T2 &val2); // 有两个参数的构造函数。 pair(const pair<T1,T2> &p); // 拷贝构造函数。 void swap(pair<T1,T2> &p); // 交换两个pair。 };

make_pair函数模板的定义如下：

template <class T1, class T2> make_pair(const T1 &first,const T2 &second) { return pair<T1,T2>(first, second); }

示例：

#include <iostream> using namespace std; template <class T1, class T2> struct Pair { T1 first; // 第一个成员，一般表示key。 T2 second; // 第二个成员，一般表示value。 Pair() { cout << "调用了有默认的构造函数。\n"; } Pair(const T1& val1, const T2& val2) :first(val1), second(val2) { cout << "调用了有两个参数的构造函数。\n"; } Pair(const Pair<T1, T2>& p) : first(p.first),second(p.second) { cout << "调用了拷贝构造函数。\n"; } }; template <class T1, class T2> Pair<T1, T2> make_Pair(const T1& first, const T2& second) { // Pair<T1, T2> p(first, second); // return p; // 返回局部对象。 return Pair<T1, T2>(first, second); // 返回临时对象。 } int main() { //pair<int, string> p0; //cout << "p0 first=" << p0.first << ",second=" << p0.second << endl; //pair<int, string> p1(1, "西施1"); // 两个参数的构造函数。 //cout << "p1 first=" << p1.first << ",second=" << p1.second << endl; //pair<int, string> p2 = p1; // 拷贝构造。 //cout << "p2 first=" << p2.first << ",second=" << p2.second << endl; //pair<int, string> p3 = { 3, "西施3" }; // 两个参数的构造函数。 pair<int, string> p3 { 3, "西施3" }; // 两个参数的构造函数，省略了等于号。 //cout << "p3 first=" << p3.first << ",second=" << p3.second << endl; auto p4 = Pair<int, string>(4, "西施4"); // 匿名对象（显式调用构造函数）。 cout << "p4 first=" << p4.first << ",second=" << p4.second << endl; auto p5 = make_Pair<int, string>(5, "西施5"); // make_pair()返回的临时对象。 cout << "p5 first=" << p5.first << ",second=" << p5.second << endl; //pair<int, string> p6 = make_pair(6, "西施6"); // 慎用，让make_pair()函数自动推导，再调用拷贝构造，再隐式转换。 //cout << "p6 first=" << p6.first << ",second=" << p6.second << endl; //auto p7 = make_pair(7, "西施7"); // 慎用，让make_pair()函数自动推导，再调用拷贝构造。 //cout << "p7 first=" << p7.first << ",second=" << p7.second << endl; //p5.swap(p4); // 交换两个pair。 //cout << "p4 first=" << p4.first << ",second=" << p4.second << endl; //cout << "p5 first=" << p5.first << ",second=" << p5.second << endl; //struct st_girl //{ // string name; // int age; // double height; //}; 用pair存放结构体数据。 //pair<int, st_girl> p = { 3,{"西施",23,48.6} }; //cout << "p first=" << p.first << endl; //cout << "p second.name=" << p.second.name << endl; //cout << "p second.age=" << p.second.age << endl; //cout << "p second.height=" << p.second.height << endl; }

调用了有两个参数的构造函数。 p4 first=4,second=西施4 调用了有两个参数的构造函数。 p5 first=5,second=西施5

7、map容器

map 容器封装了红黑树（平衡二叉排序树），用于查找。

包含头文件： #include<map>

map容器的元素是pair键值对。

map类模板的声明：

template <class K, class V, class P = less<K>, class _Alloc = allocator<pair<const K, V >>>

class map : public Tree<Tmap_traits< K, V, P, _Alloc, false>>

{

…

}

第一个模板参数K：key的数据类型（pair.first）。

第二个模板参数V：value的数据类型（pair.second）。

第三个模板参数P：排序方法，缺省按key升序。

第四个模板参数_Alloc：分配器，缺省用new和delete。

map提供了双向迭代器。

二叉链表：

struct BTNode { pair<K,V> p; // 键值对。 BTNode *parent; // 父节点。 BTNode *lchirld; // 左子树。 BTNode *rchild; // 右子树。 }; 1）构造函数

1）map(); // 创建一个空的map容器。

2）map(initializer_list<pair<K,V>> il); // 使用统一初始化列表。

3）map(const map<K,V>& m); // 拷贝构造函数。

4）map(Iterator first, Iterator last); // 用迭代器创建map容器。

5）map(map<K,V>&& m); // 移动构造函数（C++11标准）。

示例：

#include <iostream> #include <map> using namespace std; int main() { // 1）map(); // 创建一个空的map容器。 map<int, string> m1; // 2）map(initializer_list<pair<K, V>> il); // 使用统一初始化列表。 map<int, string> m2( { { 8,"冰冰" }, { 3,"西施" }, { 1,"幂幂" }, { 7,"金莲" }, { 5,"西瓜" } } ); // map<int, string> m2={ { 8,"冰冰" }, { 3,"西施" }, { 1,"幂幂" }, { 7,"金莲" }, { 5,"西瓜" } }; // map<int, string> m2 { { 8,"冰冰" }, { 3,"西施" }, { 1,"幂幂" }, { 7,"金莲" }, { 5,"西瓜" } }; for (auto& val : m2) cout << val.first << "," << val.second << " "; cout << endl; // 3）map(const map<K, V>&m); // 拷贝构造函数。 map<int, string> m3 = m2; for (auto& val : m3) cout << val.first << "," << val.second << " "; cout << endl; // 4）map(Iterator first, Iterator last); // 用迭代器创建map容器。 auto first = m3.begin(); first++; auto last = m3.end(); last--; map<int, string> m4(first,last); for (auto& val : m4) cout << val.first << "," << val.second << " "; cout << endl; // 5）map(map<K, V> && m); // 移动构造函数（C++11标准）。 }

1,幂幂  3,西施  5,西瓜  7,金莲  8,冰冰 1,幂幂  3,西施  5,西瓜  7,金莲  8,冰冰 3,西施  5,西瓜  7,金莲

2）特性操作

size_t size() const; // 返回容器的实际大小（已使用的空间）。

bool empty() const; // 判断容器是否为空。

void clear(); // 清空容器。

3）元素操作

V &operator; // 用给定的key访问元素。

const V &operator const; // 用给定的key访问元素，只读。

V &at(K key); // 用给定的key访问元素。

const V &at(K key) const; // 用给定的key访问元素，只读。

注意：

1）[ ]运算符：如果指定键不存在，会向容器中添加新的键值对；如果指定键不存在，则读取或修改容器中指定键的值。

2）at()成员函数：如果指定键不存在，不会向容器中添加新的键值对，而是直接抛出out_of_range 异常。

示例：

#include <iostream> #include <map> using namespace std; int main() { map<string, string> m( { { "08","冰冰" }, { "03","西施" }, { "01","幂幂" }, { "07","金莲" }, { "05","西瓜" } } ); cout << "m[08]=" << m["08"] << endl; // 显示key为08的元素的value。 cout << "m[09]=" << m["09"] << endl; // 显示key为09的元素的value。key为09的元素不存在，将添加新的键值对。 m["07"] = "花花"; // 把key为07的元素的value修改为花花。 m["12"] = "小乔"; // 将添加新的键值对。 for (auto& val : m) cout << val.first << "," << val.second << " "; cout << endl; }

m[08]=冰冰 m[09]= 01,幂幂  03,西施  05,西瓜  07,花花  08,冰冰  09,  12,小乔

4）赋值操作

给已存在的容器赋值，将覆盖容器中原有的内容。

1）map<K,V> &operator=(const map<K,V>& m); // 把容器m赋值给当前容器。

2）map<K,V> &operator=(initializer_list<pair<K,V>> il); // 用统一初始化列表给当前容器赋值。

5）交换操作

void swap(map<K,V>& m); // 把当前容器与m交换。

交换的是树的根结点。

6）比较操作

bool operator == (const map<K,V>& m) const;

bool operator != (const map<K,V>& m) const;

7）查找操作

1）查找键值为key的键值对

在map容器中查找键值为key的键值对，如果成功找到，则返回指向该键值对的迭代器；失败返回end()。

iterator find(const K &key);

const_iterator find(const K &key) const; // 只读。

2）查找键值>=key的键值对

在map容器中查找第一个键值>=key的键值对，成功返回迭代器；失败返回end()。

iterator lower_bound(const K &key);

const_iterator lower_bound(const K &key) const; // 只读。

3）查找键>key的键值对

在map容器中查找第一个键值>key的键值对，成功返回迭代器；失败返回end()。

iterator upper_bound(const K &key);

const_iterator upper_bound(const K &key) const; // 只读。

4）统计键值对的个数

统计map容器中键值为key的键值对的个数。

size_t count(const K &key) const;

示例：

#include <iostream> #include <map> using namespace std; int main() { map<string, string> m( { { "08","冰冰" }, { "03","西施" }, { "01","幂幂" }, { "07","金莲" }, { "05","西瓜" } } ); for (auto& val : m) cout << val.first << "," << val.second << " "; cout << endl; // 在map容器中查找键值为key的键值对，如果成功找到，则返回指向该键值对的迭代器；失败返回end()。 auto it1 = m.find("05"); if (it1 != m.end()) cout << "查找成功：" << it1->first << "," << it1->second << endl; else cout << "查找失败。\n"; // 在map容器中查找第一个键值 >= key的键值对，成功返回迭代器；失败返回end()。 auto it2 = m.lower_bound("05"); if (it2 != m.end()) cout << "查找成功：" << it2->first << "," << it2->second << endl; else cout << "查找失败。\n"; // 在map容器中查找第一个键值 > key的键值对，成功返回迭代器；失败返回end()。 auto it3 = m.upper_bound("05"); if (it3 != m.end()) cout << "查找成功：" << it3->first << "," << it3->second << endl; else cout << "查找失败。\n"; // 统计map容器中键值为key的键值对的个数。 cout << "count(05)=" << m.count("05") << endl; // 返回1。 cout << "count(06)=" << m.count("06") << endl; // 返回0。 }

01,幂幂  03,西施  05,西瓜  07,金莲  08,冰冰 查找成功：05,西瓜 查找成功：05,西瓜 查找成功：07,金莲 count(05)=1 count(06)=0

8）插入和删除

1）void insert(initializer_list<pair<K,V>> il); // 用统一初始化列表在容器中插入多个元素。

2）pair<iterator,bool> insert(const pair<K,V> &value); // 在容器中插入一个元素，返回值pair：first是已插入元素的迭代器，second是插入结果。

3）void insert(iterator first,iterator last); // 用迭代器插入一个区间的元素。

4）pair<iterator,bool> emplace (...); // 将创建新键值对所需的数据作为参数直接传入，map容器将直接构造元素。返回值pair：first是已插入元素的迭代器，second是插入结果。

例：mm.emplace(piecewise_construct, forward_as_tuple(8), forward_as_tuple("冰冰", 18));

5）iterator emplace_hint (const_iterator pos,...); // 功能与第4）个函数相同，第一个参数提示插入位置，该参数只有参考意义，如果提示的位置是正确的，对性能有提升，如果提示的位置不正确，性能反而略有下降，但是，插入是否成功与该参数元关。该参数常用end()和begin()。成功返回新插入元素的迭代器；如果元素已经存在，则插入失败，返回现有元素的迭代器。

6）size_t erase(const K & key); // 从容器中删除指定key的元素，返回已删除元素的个数。

7）iterator erase(iterator pos); // 用迭代器删除元素，返回下一个有效的迭代器。

8）iterator erase(iterator first,iterator last); // 用迭代器删除一个区间的元素，返回下一个有效的迭代器。

示例：

#include <iostream> #include <map> using namespace std; class CGirl // 超女类。 { public: string m_name; // 超女姓名。 int m_age; // 超女年龄。 /*CGirl() : m_age(0) { cout << "默认构造函数。\n"; }*/ CGirl(const string name, const int age) : m_name(name), m_age(age) { cout << "两个参数的构造函数。\n"; } CGirl(const CGirl & g) : m_name(g.m_name), m_age(g.m_age) { cout << "拷贝构造函数。\n"; } }; int main() { //map<int, CGirl> mm; //mm.insert (pair<int, CGirl>(8, CGirl("冰冰", 18))); // 一次构造函数，两次拷贝构造函数。 //mm.insert (make_pair<int, CGirl>(8, CGirl("冰冰", 18))); // 一次构造函数，两次拷贝构造函数。 //mm.emplace(pair<int, CGirl>(8, CGirl("冰冰", 18))); // 一次构造函数，两次拷贝构造函数。 //mm.emplace(make_pair<int, CGirl>(8, CGirl("冰冰", 18))); // 一次构造函数，两次拷贝构造函数。 //mm.emplace(8, CGirl("冰冰", 18)); // 一次构造函数，一次拷贝构造函数。 //mm.emplace(8, "冰冰", 18); // 错误。 //mm.emplace(piecewise_construct, forward_as_tuple(8), forward_as_tuple("冰冰", 18)); // 一次构造函数。 //for (const auto& val : mm) // cout << val.first << "," << val.second.m_name << "," << val.second.m_name << " "; //cout << endl; //return 0; map<int, string> m; // 1）void insert(initializer_list<pair<K,V>> il); // 用统一初始化列表在容器中插入多个元素。 m.insert({ { 8,"冰冰" }, { 3,"西施" }}); m.insert({ pair<int,string>(1,"幂幂"), make_pair<int,string>(7,"金莲"), {5,"西瓜"}}); m.insert({ { 18,"冰冰" }, { 3,"西施" } }); // 2）pair<iterator,bool> insert(const pair<K,V> &value); // 在容器中插入一个元素，返回值pair：first是已插入元素的迭代器，second是插入结果。 auto ret = m.insert(pair<int, string>(18, "花花")); if (ret.second == true) cout << "插入成功：" << ret.first->first << "," << ret.first->second << endl; else cout << "插入失败。\n"; // 3）void insert(iterator first, iterator last); // 用迭代器插入一个区间的元素。 // 4）pair<iterator, bool> emplace(...); // 将创建新键值对所需的数据作为参数直接传入，map容器将直接构造元素。 // 返回值pair：first是已插入元素的迭代器，second是插入结果。 auto ret1 = m.emplace(20, "花花"); if (ret1.second == true) cout << "插入成功：" << ret1.first->first << "," << ret1.first->second << endl; else cout << "插入失败。\n"; // 5）iterator emplace_hint(const_iterator pos, ...); // 功能与第4）个函数相同，第一个参数提示插入位置，该参数只有参考意义，如果提示的位置是正确的， // 对性能有提升，如果提示的位置不正确，性能反而略有下降，但是，插入是否成功与该参数元关。 // 该参数常用end()和begin()。成功返回新插入元素的迭代器；如果元素已经存在，则插入失败，返回现 // 有元素的迭代器。 m.emplace_hint(m.begin(), piecewise_construct, forward_as_tuple(23), forward_as_tuple("冰棒")); for (auto& val : m) cout << val.first << "," << val.second << " "; cout << endl; }

插入失败。 插入成功：20,花花 1,幂幂  3,西施  5,西瓜  7,金莲  8,冰冰  18,冰冰  20,花花  23,冰棒

8、unordered_map容器

unordered_map容器封装了哈希表，查找、插入和删除元素时，只需要比较几次key的值。

包含头文件： #include<unordered_map>

unordered_map容器的元素是pair键值对。

unordered_map类模板的声明：

template <class K, class V, class _Hasher = hash<K>, class _Keyeq = equal_to<K>,

class _Alloc = allocator<pair<const K, V>>>

class unordered_map : public Hash<Umap_traits<K, V, _Uhash_compare<K, _Hasher, _Keyeq>, _Alloc, false>>

{

…

}

第一个模板参数K：key的数据类型（pair.first）。

第二个模板参数V：value的数据类型（pair.second）。

第三个模板参数_Hasher：哈希函数，默认值为std::hash<K>

第四个模板参数_Keyeq：比较函数，用于判断两个key是否相等，默认值是std::equal_to<K>。

第五个模板参数_Alloc：分配器，缺省用new和delete。

创建std::unordered_map类模板的别名：

template<class K,class V>

using umap = std::unordered_map<K, V>;

1）构造函数

1）umap(); // 创建一个空的umap容器。

2）umap(size_t bucket); // 创建一个空的umap容器，指定了桶的个数，下同。

3）umap(initializer_list<pair<K,V>> il); // 使用统一初始化列表。

4）umap(initializer_list<pair<K,V>> il, size_t bucket); // 使用统一初始化列表。

5）umap(Iterator first, Iterator last); // 用迭代器创建umap容器。

6）umap(Iterator first, Iterator last, size_t bucket); // 用迭代器创建umap容器。

7）umap(const umap<K,V>& m); // 拷贝构造函数。

8）umap(umap<K,V>&& m); // 移动构造函数（C++11标准）。

示例：

#include <iostream> #include <unordered_map> using namespace std; template<class K, class V> using umap = std::unordered_map<K, V>; int main() { // 1）umap(); // 创建一个空的map容器。 umap<int, string> m1; // 2）umap(initializer_list<pair<K, V>> il); // 使用统一初始化列表。 umap<int, string> m2({ { 8,"冰冰" }, { 3,"西施" }, { 1,"幂幂" }, { 7,"金莲" }, { 5,"西瓜" } }); // umap<int, string> m2={ { 8,"冰冰" }, { 3,"西施" }, { 1,"幂幂" }, { 7,"金莲" }, { 5,"西瓜" } }; // umap<int, string> m2 { { 8,"冰冰" }, { 3,"西施" }, { 1,"幂幂" }, { 7,"金莲" }, { 5,"西瓜" } }; for (auto& val : m2) cout << val.first << "," << val.second << " "; cout << endl; // 3）umap(const map<K, V>&m); // 拷贝构造函数。 umap<int, string> m3 = m2; for (auto& val : m3) cout << val.first << "," << val.second << " "; cout << endl; // 4）umap(Iterator first, Iterator last); // 用迭代器创建map容器。 auto first = m3.begin(); first++; auto last = m3.end(); last--; umap<int, string> m4(first, last); for (auto& val : m4) cout << val.first << "," << val.second << " "; cout << endl; // 5）umap(map<K, V> && m); // 移动构造函数（C++11标准）。 }

8,冰冰  3,西施  1,幂幂  7,金莲  5,西瓜 8,冰冰  3,西施  1,幂幂  7,金莲  5,西瓜 3,西施  1,幂幂  7,金莲

2）特性操作

1）size_t size() const; // 返回容器中元素的个数。

2）bool empty() const; // 判断容器是否为空。

3）void clear(); // 清空容器。

4）size_t max_bucket_count(); // 返回容器底层最多可以使用多少桶，无意义。

5）size_t bucket_count(); // 返回容器桶的数量，空容器有8个桶。

6）float load_factor(); // 返回容器当前的装填因子，load_factor() = size() / bucket_count()。

7）float max_load_factor(); // 返回容器的最大装填因子，达到该值后，容器将扩充，缺省为1。

8）void max_load_factor (float z ); // 设置容器的最大装填因子。

9）iterator begin(size_t n); // 返回第n个桶中第一个元素的迭代器。

10）iterator end(size_t n); // 返回第n个桶中最后一个元素尾后的迭代器。

11）void reserve(size_t n); // 将容器设置为至少n个桶。

12）void rehash(size_t n); // 将桶的数量调整为>=n。如果n大于当前容器的桶数，该方法会将容器重新哈希；如果n的值小于当前容器的桶数，该方法可能没有任何作用。

13）size_t bucket_size(size_t n); // 返回第n个桶中元素的个数，0 <= n < bucket_count()。

14）size_t bucket(K &key); // 返回值为key的元素对应的桶的编号。

3）元素操作

V &operator; // 用给定的key访问元素。

const V &operator const; // 用给定的key访问元素，只读。

V &at(K key); // 用给定的key访问元素。

const V &at(K key) const; // 用给定的key访问元素，只读。

注意：

1）[ ]运算符：如果指定键不存在，会向容器中添加新的键值对；如果指定键不存在，则读取或修改容器中指定键的值。

2）at()成员函数：如果指定键不存在，不会向容器中添加新的键值对，而是直接抛出out_of_range 异常。

示例：

#include <iostream> #include <unordered_map> using namespace std; template<class K, class V> using umap = std::unordered_map<K, V>; int main() { umap<string, string> m( { { "08","冰冰" }, { "03","西施" }, { "01","幂幂" }, { "07","金莲" }, { "05","西瓜" } } ); cout << "m[08]=" << m["08"] << endl; // 显示key为08的元素的value。 cout << "m[09]=" << m["09"] << endl; // 显示key为09的元素的value。key为09的元素不存在，将添加新的键值对。 m["07"] = "花花"; // 把key为07的元素的value修改为花花。 m["12"] = "小乔"; // 将添加新的键值对。 for (auto& val : m) cout << val.first << "," << val.second << " "; cout << endl; }

m[08]=冰冰 m[09]= 08,冰冰  03,西施  12,小乔  09,  01,幂幂  07,花花  05,西瓜

4）赋值操作

给已存在的容器赋值，将覆盖容器中原有的内容。

1）umap<K,V> &operator=(const umap<K,V>& m); // 把容器m赋值给当前容器。

2）umap<K,V> &operator=(initializer_list<pair<K,V>> il); // 用统一初始化列表给容器赋值。

5）交换操作

void swap(umap<K,V>& m); // 把当前容器与m交换。

交换的是树的根结点。

6）比较操作

bool operator == (const umap<K,V>& m) const;

bool operator != (const umap<K,V>& m) const;

7）查找操作

1）查找键值为key的键值对

在umap容器中查找键值为key的键值对，如果成功找到，则返回指向该键值对的迭代器；失败返回end()。

iterator find(const K &key);

const_iterator find(const K &key) const; // 只读。

2）统计键值对的个数

统计umap容器中键值为key的键值对的个数。

size_t count(const K &key) const;

8）插入和删除

1）void insert(initializer_list<pair<K,V>> il); // 用统一初始化列表在容器中插入多个元素。

2）pair<iterator,bool> insert(const pair<K,V> &value); // 在容器中插入一个元素，返回值pair：first是已插入元素的迭代器，second是插入结果。

3）void insert(iterator first,iterator last); // 用迭代器插入一个区间的元素。

4）pair<iterator,bool> emplace (...); // 将创建新键值对所需的数据作为参数直接传入，map容器将直接构造元素。返回值pair：first是已插入元素的迭代器，second是插入结果。

例：mm.emplace(piecewise_construct, forward_as_tuple(8), forward_as_tuple("冰冰", 18));

5）iterator emplace_hint (const_iterator pos,...); // 功能与第4）个函数相同，第一个参数提示插入位置，该参数只有参考意义。对哈希容器来说，此函数意义不大。

6）size_t erase(const K & key); // 从容器中删除指定key的元素，返回已删除元素的个数。

7）iterator erase(iterator pos); // 用迭代器删除元素，返回下一个有效的迭代器。

8）iterator erase(iterator first,iterator last); // 用迭代器删除一个区间的元素，返回下一个有效的迭代器。

示例：

#include <iostream> #include <unordered_map> using namespace std; template<class K, class V> using umap = std::unordered_map<K, V>; class CGirl // 超女类。 { public: string m_name; // 超女姓名。 int m_age; // 超女年龄。 /*CGirl() : m_age(0) { cout << "默认构造函数。\n"; }*/ CGirl(const string name, const int age) : m_name(name), m_age(age) { cout << "两个参数的构造函数。\n"; } CGirl(const CGirl& g) : m_name(g.m_name), m_age(g.m_age) { cout << "拷贝构造函数。\n"; } }; int main() { //umap<int, CGirl> mm; mm.insert (pair<int, CGirl>(8, CGirl("冰冰", 18))); // 一次构造函数，两次拷贝构造函数。 mm.insert (make_pair<int, CGirl>(8, CGirl("冰冰", 18))); // 一次构造函数，两次拷贝构造函数。 mm.emplace(pair<int, CGirl>(8, CGirl("冰冰", 18))); // 一次构造函数，两次拷贝构造函数。 mm.emplace(make_pair<int, CGirl>(8, CGirl("冰冰", 18))); // 一次构造函数，两次拷贝构造函数。 mm.emplace(8, CGirl("冰冰", 18)); // 一次构造函数，一次拷贝构造函数。 // mm.emplace(8, "冰冰", 18); // 错误。 //mm.emplace(piecewise_construct, forward_as_tuple(8), forward_as_tuple("冰冰", 18)); // 一次构造函数。 //for (const auto& val : mm) // cout << val.first << "," << val.second.m_name << "," << val.second.m_name << " "; //cout << endl; //return 0; umap<int, string> m; // 1）void insert(initializer_list<pair<K,V>> il); // 用统一初始化列表在容器中插入多个元素。 m.insert({ { 8,"冰冰" }, { 3,"西施" } }); m.insert({ pair<int,string>(1,"幂幂"), make_pair<int,string>(7,"金莲"), {5,"西瓜"} }); m.insert({ { 18,"冰冰" }, { 3,"西施" } }); // 2）pair<iterator,bool> insert(const pair<K,V> &value); // 在容器中插入一个元素，返回值pair：first是已插入元素的迭代器，second是插入结果。 auto ret = m.insert(pair<int, string>(18, "花花")); if (ret.second == true) cout << "插入成功：" << ret.first->first << "," << ret.first->second << endl; else cout << "插入失败。\n"; // 3）void insert(iterator first, iterator last); // 用迭代器插入一个区间的元素。 // 4）pair<iterator, bool> emplace(...); // 将创建新键值对所需的数据作为参数直接传入，umap容器将直接构造元素。 // 返回值pair：first是已插入元素的迭代器，second是插入结果。 auto ret1 = m.emplace(20, "花花"); if (ret1.second == true) cout << "插入成功：" << ret1.first->first << "," << ret1.first->second << endl; else cout << "插入失败。\n"; // 5）iterator emplace_hint(const_iterator pos, ...); m.emplace_hint(m.begin(), piecewise_construct, forward_as_tuple(23), forward_as_tuple("冰棒")); for (auto& val : m) cout << val.first << "," << val.second << " "; cout << endl; }

插入失败。 插入成功：20,花花 8,冰冰  3,西施  1,幂幂  23,冰棒  7,金莲  5,西瓜  18,冰冰  20,花花

9、queue容器

queue容器的逻辑结构是队列，物理结构可以是数组或链表，主要用于多线程之间的数据共享。

包含头文件： #include<queue>

queue类模板的声明：

template <class T, class _Container = deque<T>>

class queue{

……

}

第一个模板参数T：元素的数据类型。

第二个模板参数_Container：底层容器的类型，缺省是std::deque，可以用std::list，还可以用自定义的类模板。

queue容器不支持迭代器。

1）构造函数

1）queue(); // 创建一个空的队列。

2）queue(const queue<T>& q); // 拷贝构造函数。

3）queue(queue<T>&& q); // 移动构造函数（C++11标准）。

析构函数~queue()释放内存空间。

2）常用操作

1）void push(const T& value); // 元素入队。

2）void emplace(…); // 元素入队，…用于构造元素。C++11

3）size_t size() const; // 返回队列中元素的个数。

4）bool empty() const; // 判断队列是否为空。

5）T &front(); // 返回队头元素。

6）const T &front(); // 返回队头元素，只读。

7）T &back(); // 返回队尾元素。

8）const T &back(); // 返回队头元素，只读。

9）void pop(); // 出队，删除队头的元素。

示例：

#include <iostream> #include <queue> #include <deque> #include <list> using namespace std; class girl // 超女类。 { public: int m_bh; // 编号。 string m_name; // 姓名。 girl(const int& bh, const string& name) : m_bh(bh), m_name(name) {} }; int main() { // template <class T, class _Container = deque<T>> // class queue { // …… // } // 第一个模板参数T：元素的数据类型。 // 第二个模板参数_Container：底层容器的类型，缺省是std::deque，可以用std::list，还可以用自定义的类模板。 queue<girl, list<girl>> q; // 物理结构为链表。 //queue<girl, deque<girl>> q; // 物理结构为数组。 //queue<girl> q; // 物理结构为数组。 //queue<girl, vector<girl>> q; // 物理结构为vector，不可以。 q.push(girl(3, "西施")); // 效率不高。 q.emplace(8, "冰冰"); // 效率更高。 q.push(girl(5, "幂幂")); q.push(girl(2, "西瓜")); while (q.empty() == false) { cout << "编号：" << q.front().m_bh << "，姓名：" << q.front().m_name << endl; q.pop(); } }

编号：3，姓名：西施 编号：8，姓名：冰冰 编号：5，姓名：幂幂 编号：2，姓名：西瓜

3）其它操作

1）queue &operator=(const queue<T> &q); // 赋值。

2）void swap(queue<T> &q); // 交换。

3）bool operator == (const queue<T> & q) const; // 重载==操作符。

4）bool operator != (const queue<T> & q) const; // 重载!=操作符。

10、STL其它容器 1）array（静态数组）

① 物理结构

在栈上分配内存，创建数组的时候，数组长度必须是常量，创建后的数组大小不可变。

template<class T, size_t size>

class array{

private:

T elems_[size];

……

};

② 迭代器

随机访问迭代器。

③ 特点

部分场景中，比常规数组更方便（能用于模板），可以代替常规数组。

④ 各种操作

1）void fill(const T & val); // 给数组填充值（清零）。

2）size_t size(); // 返回数组的大小。

3）bool empty() const; // 无意义。

4）T &operator;

5）const T &operator const; // 只读。

6）T &at(size_t n);

7）const T &at(size_t n) const; // 只读。

8）T *data(); // 返回数组的首地址。

9）const T *data() const; // 返回数组的首地址。

10）T &front(); // 第一个元素。

11）const T &front(); // 第一个元素，只读。

12）const T &back(); // 最后一个元素，只读。

13）T &back(); // 最后一个元素。

示例：

#include <iostream> #include <array> using namespace std; void func(int arr[][6],int len) //void func(int (* arr)[6], int len) //{ // for (int ii = 0; ii < len; ii++) // { // for (int jj = 0; jj < 6; jj++) // cout << arr[ii][jj] << " "; // cout << endl; // } //} //void func(const array < array<int, 5>, 10 >& arr) //{ // for (int ii = 0; ii < arr.size(); ii++) // { // for (int jj = 0; jj < arr[ii].size(); jj++) // cout << arr[ii][jj] << " "; // cout << endl; // } //} template <typename T> void func(const T& arr) { for (int ii = 0; ii < arr.size(); ii++) { for (int jj = 0; jj < arr[ii].size(); jj++) cout << arr[ii][jj] << " "; cout << endl; } } int main() { //int aa[11] = {1,2,3,4,5,6,7,8,9,10,11}; // 一维数组。 //array<int, 10> aa = { 1,2,3,4,5,6,7,8,9,10 }; // 一维数组。 //for (int ii = 0; ii < 10; ii++) // 传统的方法。 // cout << aa[ii] << " "; //cout << endl; // //for (int ii = 0; ii < aa.size(); ii++) // 利用array的size()方法。 // cout << aa[ii] << " "; //cout << endl; // //for (auto it= aa.begin(); it < aa.end(); it++) // 使用迭代器。 // cout << *it << " "; //cout << endl; //for (auto val : aa) // 基于范围的for循环。 // cout << val << " "; //cout << endl; //int bb[10][6]; //for (int ii = 0; ii < 10; ii++) // 对二维数组赋值。 //{ // for (int jj = 0; jj < 6; jj++) // bb[ii][jj] = jj * 10 + ii; //} //func(bb,10); // 把二维数组传给函数。 array< array<int, 5>, 10 > bb; // 二维数组，相当于int bb[10][5]。 for (int ii = 0; ii < bb.size(); ii++) // 对二维数组赋值。 { for (int jj = 0; jj < bb[ii].size(); jj++) bb[ii][jj] = jj * 10 + ii; } func(bb); // 把二维数组传给函数。 }

0 10 20 30 40 1 11 21 31 41 2 12 22 32 42 3 13 23 33 43 4 14 24 34 44 5 15 25 35 45 6 16 26 36 46 7 17 27 37 47 8 18 28 38 48 9 19 29 39 49

2）deque（双端队列）

① 物理结构

deque容器存储数据的空间是多段等长的连续空间构成，各段空间之间并不一定是连续的。

为了管理这些连续空间的分段，deque容器用一个数组存放着各分段的首地址。

通过建立数组，deque容器的分段的连续空间能实现整体连续的效果。

当deque容器在头部或尾部增加元素时，会申请一段新的连续空间，同时在数组中添加指向该空间的指针。

② 迭代器

随机访问迭代器。

③ 特点

提高了在两端插入和删除元素的效率，扩展空间的时候，不需要拷贝以前的元素。

在中间插入和删除元素的效率比vector更糟糕。

随机访问的效率比vector容器略低。

④ 各种操作

与vector容器相同。

3）forward_list（单链表）

① 物理结构

单链表。

② 迭代器

正向迭代器。

③ 特点

比双链表少了一个指针，可节省一丢丢内存，减少了两次对指针的赋值操作。

如果单链表能满足业务需求，建议使用单链表而不是双链表。

④ 各种操作

与list容器相同。

4）multimap

底层是红黑树。

multimap和map的区别在：multimap允许关键字重复，而map不允许重复。

各种操作与map容器相同。

5）set&multiset

底层是红黑树。

set和map的区别在：map中存储的是键值对，而set只保存关键字。

multiset和set的区别在：multiset允许关键字重复，而set不允许重复。

各种操作与map容器相同。

6）unordered_multimap

底层是哈希表。

unordered_multimap和unordered_map的区别在：unordered_multimap允许关键字重复，而unordered_map不允许重复。

各种操作与unordered_map容器相同。

7）unordered_set&unorderedmultiset

底层是哈希表。

unordered_set和unordered_map的区别在：unordered_map中存储的是键值对，而unordered_set只保存关键字。

unordered_multiset和unordered_set的区别在：unordered_multiset允许关键字重复，而unordered_set不允许重复。

各种操作与unordered_map容器相同。

8）priority_queue（优先队列）

优先级队列相当于一个有权值的单向队列queue，在这个队列中，所有元素是按照优先级排列的。

底层容器可以用deque和list。

各种操作与queue容器相同。

9）stack（栈）

底层容器可以用deque和list。