C++_23_STL容器
文章目录
- STL容器
- 概念
- 常用容器
- A string
- 作用
- 构造函数
- 基本赋值操作
- 获取字符串长度
- 存取字符操作
- 拼接操作
- 查找和替换
- 注意:查找是不存在返回-1
- 比较操作
- 截取操作
- 插入与删除
- string与char * 转换
- B vector
- 概述
- 与数组区别
- 迭代器
- 构造函数
- 赋值操作
- 插入与删除
- 取值操作
- 大小相关
- 存储自定义类型
- 容器嵌套
- C deque
- 概述
- 与vector的区别
- api
- D stack
- 概念
- api
- E List
- F set/multiset
- api
- G map/multimap
- 总结
STL容器
概念
STL(Standard Template Library,标 准 模 板 库 ),是 惠 普 实 验 室 开 发 的 一 系 列 软 件 的 统称 。
STL 6大 组 件
容 器 :作 用 :容 纳 存 储 数 据分 类 :序 列 式 容 器 ：强 调 值 的 排 序 ， 每 个 元 素 均 有 固 定 的 位 置 ， 除 非 用 删 除 或 插 入 的 操
作 改 变 这 个 位 置 ，如 vector, deque/queue, list;关 联 式 容 器 :非 线 性 ， 更 准 确 的 说 是 二 叉 树 结 构 ， 各 元 素 之 间 没 有 严 格 的 物 理 上
的 顺 序 关 系 ; 在 数 据 中 选 择 一 个 关 键 字 key， 这 个 key对 数 据 起 到 索 引 的 作 用 ， 方
便 查 找 。如 ： set/multiset ， Map/multimap 容 器注 意 :容 器 可 以 嵌 套 容 器算 法 :作 用 :操 作 数 据 ,如 插 入 数 据 、 删 除 数 据 、 修 改 数 据 、 排 序 等分 类 :质 变 算 法 ： 是 指 运 算 过 程 中 会 更 改 区 间 内 的 元 素 的 内 容 。 例 如 拷 贝 ， 替
换 ， 删 除 等 等非 质 变 算 法 ： 是 指 运 算 过 程 中 不 会 更 改 区 间 内 的 元 素 内 容 ， 例 如 查 找 、
计 数 、 遍 历 、 寻 找 极 值 等 等迭 代 器作 用 :容 器 与 算 法 之 间 的 粘 合 剂注 意 :每 个 容 器 都 有 自 己 的 迭 代 器分 类 :输 入 迭 代 器 提 供 对 数 据 的 只 读 访 问 只 读 ， 支 持 ++、 ==、 ！ = 输 出 迭 代 器 提 供 对 数 据 的 只 写 访 问 只 写 ， 支 持 ++前 向 迭 代 器 提 供 读 写 操 作 ， 并 能 向 前 推 进 迭 代 器 读 写 ， 支 持 ++、
==、 ！ = 双 向 迭 代 器 提 供 读 写 操 作 ， 并 能 向 前 和 向 后 操 作 读 写 ， 支 持 ++、 --，随 机 访 问 迭 代 器 提 供 读 写 操 作 ， 并 能 以 跳 跃 的 方 式 访 问 容 器 的 任 意 数
据 ， 是 功 能 最 强 的 迭 代 器 读 写 ， 支 持 ++、 -- [n]、 - n、 <、 <=、 >、 >=仿 函 数作 用 :为 算 法 提 供 策 略适 配 器作 用 :为 算 法 提 供 更 多 的 参 数 接 口空 间 配 置 器作 用 :为 容 器 和 算 法 管 理 空 间
常用容器
A string
作用
存储字符的容器(字符串)
构造函数
语法
string();//创 建 一 个 空 的 字 符 串 例 如 : string str;string(const string& str);//使 用 一 个 string 对 象 初 始 化 另 一 个 string 对 象string(const char* s);//使 用 字 符 串 s 初 始 化string(int n, char c);//使 用 n 个 字 符 c 初 始 化 v示例:
void fun01()
{string str01;cout << "str01 = " << str01 << endl;string str02("hello");cout << "str02 = " << str02 << endl;string str03 = str02;cout << "str03 = " << str03 << endl;string str04(3,'a');cout << "str04 = " << str04 << endl;
}
基本赋值操作
语法
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个字 符 赋 值 给 字 符 串示例1
void fun02()
{string str01;cout << "str01 = " << str01 << endl;str01 = "张 十 一";cout << "str01 = " << str01 << endl;string str02;str02 = str01;cout << "str02 = " << str02 << endl;string str03;str03 = 'A';cout << "str03 = " << str03 << endl;
}
示例2
void fun03()
{// 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个 字 符 赋 值 给 字 符 串string str01 = "hello";cout << "str01 = " << str01 << endl;// str01.assign("world123");// str01.assign("world123",5);// str01.assign(3,'A');// cout << "str01 = " << str01 << endl;string str02;str02.assign(str01, 0, 2);cout << "str02 = " << str02 << endl;
}
获取字符串长度
语法
int size();
int length();
注 意 :不 包 含 \0示例
void fun04()
{string str = "hello";int size = str.size();cout << "size = " << size << endl;int len = str.length();cout << "len = " << len << endl;
}存取字符操作
语法
char& operator[](int n);//通 过 []方 式 取 字 符 ,下 标 越 界 不 会 抛 出 异 常char& at(int n);//通 过 at方 法 获 取 字 符 ,下 标 越 界 会 抛 出 异 常示例
void fun05()
{string str = "hello";cout << str[2] << endl;cout << str.at(1) << endl;
}拼接操作
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 fun06()
{string str01 = "Hi";str01+="C++";cout << "str01 = " << str01 << endl;string str02 = " STL";str01+=str02;cout << "str01 = " << str01 << endl;str01+='A';cout << "str01 = " << str01 << endl;
}
void fun07()
{// string& append(const char *s);//把 字 符 串 s连 接 到 当 前 字 符 串 结 尾string str01;str01.append("hi");cout << "str01 = " << str01 << endl;str01.append(" c++");cout << "str01 = " << str01 << endl;// string& append(const char *s, int n);//把 字 符 串 s的 前 n个 字 符 连 接 到 当 前 字 符 串 结 尾string str02;str02.append("abcdefg",5);cout << "str02 = " << str02 << endl;// string& append(const string &s);//同 operator+=()// string& append(const string &s, int pos, int n);//把 字 符 串 s中 从 pos开 始 的 n个 字 符 连 接 到 当 前 字 符 串 结 尾string str03 = "1234567890";string str04;str04.append(str03,3,2);cout << "str04 = " << str04 << endl;// string& append(int n, char c);//在 当 前 字 符 串 结 尾 添 加 n个 字 符 cstr04.append(2,'W');cout << "str04 = " << str04 << endl;
}查找和替换
语法
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注意:查找是不存在返回-1
示例
void fun08()
{string str = "123abc123";int i01 = str.find('2');cout << "i01 = " << i01 << endl;int i02 = str.find("3a");cout << "i02 = " << i02 << endl;int i03 = str.rfind('2');cout << "i03 = " << i03 << endl;str.replace(3, 3, "147258369");cout << "str = " << str << endl;
}
比较操作
/**
*compare函数在>时返回1，<时返回-1，==时返回0。
*比较区分大小写，比较时参考字典顺序，排越前面的越小。大写的A比小写的a小。
**/
int compare(const string &s) const; //与字符串s比较
int compare(const char *s) const; //与字符串s比较
截取操作
语法
string substr(int pos = 0, int n = npos) const;//返回由pos开始的n个字符组成的字符串
示例
void fun09()
{string str01 = "a.txt";string str02 = str01.substr(1,4);cout << str02 << endl;
}
插入与删除
语法
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 fun10()
{// string& insert(int pos, const char* s); //插入字符串// string& insert(int pos, const string& str); //插入字符串// string& insert(int pos, int n, char c);//在指定位置插入n个字符cstring str01 = "11";// 开始位置不要超出字符串下标范围// str01.insert(1,"abc");str01.insert(1, 3, 'A');cout << "str01 = " << str01 << endl;// string& erase(int pos, int n = npos);//删除从Pos开始的n个字符str01.erase(1, 3);cout << "str01 = " << str01 << endl;
}
string与char * 转换
语法
//string转char*
string str = "itcast";
const char* cstr = str.c_str();
//char*转string
char* s = "itcast";
string str(s);
示例
void fun11()
{string str01 = "abc";string str02("abc");char *str03 = (char *)str01.c_str();
}
B vector
概述
-
连 续 开 辟 ,单 向 开 口 ,随 机 访 问 迭 代 器 ,有 容 量 ,每 次 扩 容 是 原 来 的 2倍
-
底 层 数 据 结 构 :数 组
与数组区别
>vector的 结 构 类 同 于 数 组 ， 数 组 是 静 态 的 ， 在 定 义 时 确 定 的 数 组 的 大 小 ；而 vector是 动 态 的 ， 添 加 元 素 时 如 果 空 间 不 足 时 ， 则 会 自 动 扩 容 器 （ 2^n);这 被 称 为vector的 未 雨 绸 缪 机 制整 体 来 说 ， vector比 较 灵 活 的 ， 而 且 vector是 类 模 板 ， 可 以 存 放 任 意 类 型 的 元 素
迭代器
构造函数
语法
vector<T> v; //采用模板实现类实现，默认构造函数
vector(v.begin(), v.end());//将 v[begin(), end())区间中的元素拷贝给本身。
vector(n, elem);//构造函数将 n 个 elem 拷贝给本身。
vector(const vector &vec);//拷贝构造函数
示例
void fun01()
{vector<int> v01;v01.push_back(1); // 尾部添加v01.push_back(5);v01.push_back(3);vector<int>::iterator it = v01.begin(); // 获取开始位置的迭代器while (it != v01.end()) // end():结束位置{cout << *it << endl; //*it获取当前迭代器指向的位置的值it++; // 迭代器后移1位}
}
// =======================================
void fun02()
{vector<int> v01;v01.push_back(1); // 尾部添加v01.push_back(5);v01.push_back(3);vector<int> v02(v01.begin() + 1, v01.begin() + 2); // 包含开始位置,不包含结束位置(前闭后开)// vector<int>::iterator it = v02.begin();auto it = v02.begin(); // c++11及以上版本,编译时需加-std=c++11while (it != v02.end()){cout << *it << endl;it++;}
}
// =======================================
void fun03()
{vector<int> v(10, 5);auto it = v.begin();while (it != v.end()){cout << *it << endl;it++;}
}
赋值操作
语法
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将 n 个 elem 拷贝赋值给本身。
vector& operator=(const vector &vec);//重载等号操作符
swap(vec);// 将 vec 与本身的元素互换
示例
void fun04()
{// assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。// assign(n, elem);//将 n 个 elem 拷贝赋值给本身。// vector& operator=(const vector &vec);//重载等号操作符// swap(vec);// 将 vec 与本身的元素互换vector<int> v01;v01.push_back(1);v01.push_back(5);v01.push_back(3);v01.push_back(9);v01.push_back(7);vector<int> v02;// v02.assign(v01.begin(),v01.begin()+3);// v02.assign(5,3);// v02 = v01;v02.push_back(2);v02.push_back(4);v02.swap(v01);auto it = v02.begin();while (it != v02.end()){cout << *it << endl;it++;}cout << "---------------" << endl;auto it01 = v01.begin();while (it01 != v01.end()){cout << *it01 << endl;it01++;}
}
插入与删除
语法
push_back(ele);
//尾部插入元素 eleinsert(const_iterator pos, int count, T ele);
//迭代器指向位置 pos 插入count个元素ele.pop_back();
//删除最后一个元素erase(const_iterator start, const_iterator end);
//删除迭代器从 start到 end 之间的元素,删除[start, end)区间的所有元素erase(const_iterator pos);
//删除迭代器指向的元素clear();
//删除容器中所有元素
示例
void fun05()
{vector<int> v;// push_back(ele); //尾部插入元素 elev.push_back(1);v.push_back(3);v.push_back(5);v.push_back(7);// insert(const_iterator pos, int count, T ele); //迭代器指向位置pos 插入 count个元素ele.v.insert(v.begin(), 1, 0);// pop_back();//删除最后一个元素v.pop_back();// v.pop_back();// erase(const_iterator start, const_iterator end); //删除迭代器从start 到 end 之间的元素,删除[start, end)区间的所有元素v.erase(v.begin() + 1, v.begin() + 3);// erase(const_iterator pos); //删除迭代器指向的元素v.erase(v.begin());// clear(); //删除容器中所有元素v.clear();auto it = v.begin();while (it != v.end()){cout << *it << endl;it++;}
}
取值操作
语法
at(int idx); //返回索引 idx 所指的数据，如果 idx 越界，抛出 out_of_range异常。
operator[](int idx); //返回索引 idx 所指的数据，越界时,不会直接报错
front(); //返回容器中第一个数据元素
back(); //返回容器中最后一个数据元素
示例
void fun06()
{vector<int> v;v.push_back(1);v.push_back(3);v.push_back(5);v.push_back(7);// at(int idx); //返回索引 idx 所指的数据，如果 idx 越界，抛出out_of_range 异常。cout<< "v.at(3) = " << v.at(3) << endl;// operator[](int idx); //返回索引 idx 所指的数据，越界时，不会报错cout << "v[2] = " << v[100] << endl;// front(); //返回容器中第一个数据元素cout << v.front() << endl;// back(); //返回容器中最后一个数据元素cout << v.back() << endl;
}
大小相关
语法
int size(); // 返回容器中元素的个数
bool empty(); //判断容器是否为空， 返回bool值（0， 1）
void resize(int num); //重新指定容器的长度为 num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
void resize(int num, elem); //重新指定容器的长度为 num，若容器变长，则以elem 值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
int capacity(); //容器的容量
void reserve(int len); //容器预留 len 个元素长度
示例
void fun07()
{vector<int> v;v.push_back(1);v.push_back(3);v.push_back(5);v.push_back(7);v.push_back(9);// int size(); // 返回容器中元素的个数// cout << v.size() << endl;// bool empty(); //判断容器是否为空， 返回bool值（0， 1）// cout << v.empty() << endl;// void resize(int num); //重新指定容器的长度为 num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。// v.resize(2);// void resize(int num, elem); //重新指定容器的长度为 num，若容器变长，则以 elem 值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。// v.resize(10,10);// int capacity(); //容器的容量cout<< v.capacity() << endl;// void reserve(int len); //容器预留 len 个元素长度v.reserve(10);cout << v.capacity() << endl;// auto it = v.begin();// while(it != v.end())// {// cout << *it << endl;// it++;// }
}
void fun08()
{vector<int> v;v.push_back(1);v.push_back(3);v.push_back(5);v.push_back(7);v.push_back(9);cout << "v的大小 = " << v.size() << endl;cout << "v的容量 = " << v.capacity() << endl;vector<int>(v).swap(v);cout << "v的大小 = " << v.size() << endl;cout << "v的容量 = " << v.capacity() << endl;
}
存储自定义类型
示例
class Per
{
public:char *name;Per(char *name){this->name = name;}
};
void fun09()
{vector<Per> ps;ps.push_back(Per("张三"));ps.push_back(Per("李四"));ps.push_back(Per("王五"));for (auto it = ps.begin(); it != ps.end(); it++){cout << (*it).name << endl;}
}
容器嵌套
void fun10()
{vector<int> v1;v1.push_back(10);v1.push_back(20);v1.push_back(30);v1.push_back(40);v1.push_back(50);vector<int> v2;v2.push_back(100);v2.push_back(200);v2.push_back(300);v2.push_back(400);v2.push_back(500);vector<int> v3;v3.push_back(1000);v3.push_back(2000);v3.push_back(3000);v3.push_back(4000);v3.push_back(5000);vector<vector<int>> v;v.push_back(v1);v.push_back(v2);v.push_back(v3);vector<vector<int>>::iterator it = v.begin();for (; it != v.end(); it++){//*it == vector<int>vector<int>::iterator mit = (*it).begin();for (; mit != (*it).end(); mit++){//*mit==intcout << *mit << " ";}cout << endl;}
}
C deque
概述
>deque 则是一种双向开口的连续线性空间。所谓的双向开口，意思是可以在头尾两端分
别做元素的插入和删除操作数据结构:数组
与vector的区别
-
一 在 于 deque 允 许 使 用 常 数 项 时 间 对 头 端 进 行 元 素 的 插 入 和 删 除 操 作 。
-
二 在 于 deque 没 有 容 量 的 概 念 ， 因 为 它 是 动 态 的 以 分 段 连 续 空 间 组 合 而 成 ， 随 时 可 以
增 加 一 段 新 的 空 间 并 链 接 起 来
api
//构 造 函 数
deque<T> deqT;//默 认 构 造 形 式
deque(beg, end);//构 造 函 数 将 [beg, end)区 间 中 的 元 素 拷 贝 给 本 身 。
deque(n, elem);//构 造 函 数 将 n 个 elem 拷 贝 给 本 身 。
deque(const deque &deq);//拷 贝 构 造 函 数//赋 值 操 作
assign(beg, end);//将 [beg, end)区 间 中 的 数 据 拷 贝 赋 值 给 本 身 。
assign(n, elem);//将 n 个 elem 拷 贝 赋 值 给 本 身 。
deque& operator=(const deque &deq); //重 载 等 号 操 作 符
swap(deq);// 将 deq 与 本 身 的 元 素 互 换//大 小 操 作
deque.size();//返 回 容 器 中 元 素 的 个 数
deque.empty();//判 断 容 器 是 否 为 空deque.resize(num);//重 新 指 定 容 器 的 长 度 为 num,若 容 器 变 长 ， 则 以 默 认 值 填 充 新位 置 。 如 果 容 器 变 短 ， 则 末 尾 超 出 容 器 长 度 的 元 素 被 删 除 。deque.resize(num, elem); //重 新 指 定 容 器 的 长 度 为 num,若 容 器 变 长 ， 则 以 elem 值 填 充 新 位 置 ,如 果 容 器 变 短 ， 则 末 尾 超 出 容 器 长 度 的 元 素 被 删 除 。//双 端 插 入 和 删 除 操 作
push_back(elem);//在 容 器 尾 部 添 加 一 个 数 据
push_front(elem);//在 容 器 头 部 插 入 一 个 数 据
pop_back();//删 除 容 器 最 后 一 个 数 据
pop_front();//删 除 容 器 第 一 个 数 据//数 据 存 取
at(idx);//返 回 索 引 idx 所 指 的 数 据 ， 如 果 idx 越 界 ， 抛 出 out_of_range。
operator[];//返 回 索 引 idx 所 指 的 数 据 ， 如 果 idx 越 界 ， 不 抛 出 异 常 ， 直 接 出错 。front();//返 回 第 一 个 数 据 。
back();//返 回 最 后 一 个 数 据//插 入 操 作
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 位 置 的 数 据 ， 返 回 下 一 个 数 据 的 位 置 。
D stack
概念
栈 (先 进 后 出 ,又 名 水 桶 ),单 向 开 口 ,没 有 迭 代 器
api
构 造 函 数
stack<T> stkT;//stack 采 用 模 板 类 实 现 ， stack 对 象 的 默 认 构 造 形 式 ：
stack(const stack &stk);//拷 贝 构 造 函 数赋 值 操 作
stack& operator=(const stack &stk);//重 载 等 号 操 作 符数 据 存 取 操 作
push(elem);//向 栈 顶 添 加 元 素
pop();//从 栈 顶 移 除 第 一 个 元 素
top();//返 回 栈 顶 元 素大 小 操 作
empty();//判 断 堆 栈 是 否 为 空
size();//返 回 堆 栈 的 大 小
示例
#include <iostream>
#include <stack>
using namespace std;
int main(int argc, char const *argv[])
{stack<int> s;s.push(1);s.push(5);s.push(3);s.push(7);// while(s.size() != 0)// {// cout << s.top() << endl;// s.pop();// }while (!s.empty()){cout << s.top() << endl;s.pop();}return 0;
}
E queue
概念
- 队 列 (先 进 先 出 ),又 名 水 管 ,双 向 开 口 ,没 有 迭 代 器
- 队 头 :出 数 据
- 队 尾 :入 数 据
api
构 造 函 数queue<T> queT;//queue 采 用 模 板 类 实 现 ， queue 对 象 的 默 认 构 造 形 式 ：
queue(const queue &que);//拷 贝 构 造 函 数存 取 、 插 入 和 删 除 操 作push(elem);//往 队 尾 添 加 元 素
pop();//从 队 头 移 除 第 一 个 元 素
back();//返 回 最 后 一 个 元 素
front();//返 回 第 一 个 元 素赋 值 操 作queue& operator=(const queue &que);//重 载 等 号 操 作 符大 小 操 作empty();//判 断 队 列 是 否 为 空
size();//返 回 队 列 的 大 小
示例
#include <iostream>
#include <queue>
using namespace std;
int main(int argc, char const *argv[])
{queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);while (!q.empty()){cout << q.front() << endl;q.pop();}return 0;
}
E List
概念
- 基 于 双 向 链 表 的 ,离 散 存 储 的 ,双 向 迭 代 器 ,元 素 可 重 复
- 数 据 结 构 :链 表
双 向 迭 代 器 :可 以 ++,–,但 是 不 能 +,-
api
构 造 函 数list<T> lstT;//list 采 用 采 用 模 板 类 实 现 ,对 象 的 默 认 构 造 形 式 ：list(beg,end);//构 造 函 数 将 [beg, end)区 间 中 的 元 素 拷 贝 给 本 身 。list(n,elem);//构 造 函 数 将 n 个 elem 拷 贝 给 本 身 。list(const list &lst);//拷 贝 构 造 函 数 。数 据 元 素 插 入 和 删 除 操 作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 值 匹 配 的 元 素 。大 小 操 作size();//返 回 容 器 中 元 素 的 个 数empty();//判 断 容 器 是 否 为 空resize(num);//重 新 指 定 容 器 的 长 度 为 num， 若 容 器 变 长 ， 则 以 默 认 值 填 充 新 位置 。 如 果 容 器 变 短 ， 则 末 尾 超 出 容 器 长 度 的 元 素 被 删 除 。resize(num, elem);//重 新 指 定 容 器 的 长 度 为 num,若 容 器 变 长 ， 则 以 elem 值填 充 新 位 置 。 如 果 容 器 变 短 ， 则 末 尾 超 出 容 器 长 度 的 元 素 被 删 除 。赋 值 操 作assign(beg, end);//将 [beg, end)区 间 中 的 数 据 拷 贝 赋 值 给 本 身 。assign(n, elem);//将 n 个 elem 拷 贝 赋 值 给 本 身 。list& operator=(const list &lst);//重 载 等 号 操 作 符swap(lst);//将 lst 与 本 身 的 元 素 互 换 。数 据 的 存 取front();//返 回 第 一 个 元 素 。back();//返 回 最 后 一 个 元 素 。反 转 排 序reverse();//反 转 链 表 ， 比 如 lst 包 含 1,3,5 元 素 ， 运 行 此 方 法 后 ， lst 就 包含 5,3,1元 素 sort(); //list 排 序
示例
#include <iostream>
#include <list>
#include <string>
using namespace std;
void showList(list<int> nums)
{list<int>::iterator it = nums.begin();for (; it != nums.end(); it++){cout << *it << endl;}
}
void fun01()
{list<int> nums;nums.push_back(1);nums.push_back(5);nums.push_back(3);nums.push_back(7);nums.reverse();showList(nums);
}
void fun02()
{list<int> nums;nums.push_back(1);nums.push_back(5);nums.push_back(3);nums.push_back(7);nums.sort();showList(nums);
}
void fun03()
{list<int> nums;nums.push_back(1);nums.push_back(5);nums.push_back(3);nums.push_back(7);nums.sort();nums.reverse();showList(nums);
}
class Person
{
private:string name;public:Person(){name = "";}Person(char *name){this->name = name;}Person(const Person &p){this->name = p.name;}string &getName(){return name;}
};
int main(int argc, char const *argv[])
{list<Person> ps;ps.push_back(Person("张三"));ps.push_back(Person("李四"));ps.push_back(Person("王五"));list<Person>::iterator it;for (it = ps.begin(); it != ps.end(); it++){cout << (*it).getName() << endl;}return 0;
}
F set/multiset
set特点
- Set 的 特 性 是 。 所 有 元 素 都 会 根 据 元 素 的 键 值 自 动 被 排 序 。
- Set 容 器 的 键 值 和 实 值 是 同 一 个 值 。
- Set 不 允 许 两 个 元 素 有 相 同 的 键 值 。
- Set容 器 的 迭 代 器 是 只 读 迭 代 器 。 插 入 数 据 后 不 允 许 修 改 set的 键 值 。
- 数 据 结 构 :红 黑 树
注 意 :
如 果 存 入 的 值 大 于 原 有 的 值 ,此 时 x > y 为 真 ,存 入 的 值 在 原 有 值 左 边
如 果 存 储 的 值 小 于 原 有 的 值 ,此 时 x > y 为 假 ,交 换 在 比 较
如 果 交 换 后 ,存 储 的 值 为 y,原有值的为 x,此 时 x > y 为真 ,存入的值不应该在原有值 左 边
如 果 交 换 后 ,存 储 的 值 为 y,原 有 值 的 为 x,此 时 x > y 为 假 ,此时证明不符合其存储 原 则
multiset特点
- multiset 特 性 及 用 法 和 set 完 全 相 同 ， 唯 一 的 差 别 在 于 它 允 许 键 值 重 复 。
- 数 据 结 构 :红 黑 树
api
构 造 函 数set<T> st;//set 默 认 构 造 函 数 ：
mulitset<T> mst; //multiset 默 认 构 造 函 数 :
set(const set &st);//拷 贝 构 造 函 数赋 值 操 作set& operator=(const set &st);//重 载 等 号 操 作 符
swap(st);//交 换 两 个 集 合 容 器大 小 操 作size();//返 回 容 器 中 元 素 的 数 目
empty();//判 断 容 器 是 否 为 空插 入 和 删 除 操 作insert(elem);//在 容 器 中 插 入 元 素 。
clear();//清 除 所 有 元 素
erase(pos);//删 除 pos 迭 代 器 所 指 的 元 素 ， 返 回 下 一 个 元 素 的 迭 代 器 。
erase(beg, end);//删 除 区 间 [beg,end)的 所 有 元 素 ， 返 回 下 一 个 元 素 的 迭 代 器 。
erase(elem);//删 除 容 器 中 值 为 elem 的 元 素 。查 找 操 作find(key);//查 找 键 key 是 否 存 在 ,若 存 在 ， 返回该键的元素的迭代器；若不存在返回set.end();
count(key);//查 找 键 key 的 元 素 个 数
lower_bound(keyElem);//下 限 返 回 第 一 个 key>=keyElem 元 素 的 迭 代 器 。
upper_bound(keyElem);//上 限 返 回 第 一 个 key>keyElem 元 素 的 迭 代 器 。
equal_range(keyElem);//返 回 容 器 中 key 与 keyElem 相 等 的 上 下 限 的 两 个 迭 代器 。
示例
#include <iostream>
#include <set>
using namespace std;
void fun01()
{set<int> s;s.insert(3);s.insert(2);s.insert(6);s.insert(5);s.insert(1);s.insert(1); // 存储的元素不允许重复set<int>::const_iterator it = s.begin();while (it != s.end()){cout << *it << endl;it++;}
}
void fun02()
{multiset<int> s;s.insert(3);s.insert(2);s.insert(6);s.insert(5);s.insert(1);s.insert(1); // 存储的元素允许重复multiset<int>::const_iterator it = s.begin();while (it != s.end()){cout << *it << endl;it++;}
}
class MyCompare
{
public:bool operator()(int x, int y){return x > y;}
};
void fun03()
{// 自定义比较器set<int, MyCompare> s;s.insert(3);s.insert(4);// s.insert(2);// s.insert(5);set<int>::const_iterator it = s.begin();while (it != s.end()){cout << *it << endl;it++;}
}
class MyCompareP;
class Person
{friend class MyCompareP;friend void fun04();private:string name;int age;public:Person(){name = "";}Person(char *name, int age){this->name = name;this->age = age;}Person(const Person &p){this->name = p.name;this->age = p.age;}string &getName(){return name;}
};
class MyCompareP
{
public:bool operator()(Person p1, Person p2){return p1.age <= p2.age;}
};
void fun04()
{set<Person, MyCompareP> s;s.insert(Person("张三", 18));s.insert(Person("李四", 16));s.insert(Person("王五", 19));s.insert(Person("赵六", 18));cout << "size = " << s.size() << endl;set<Person>::const_iterator it;for (it = s.begin(); it != s.end(); it++){cout << (*it).name << endl;}
}
int main(int argc, char const *argv[])
{fun04();return 0;
}
#include <iostream>
#include <set>
#include <map>
using namespace std;
int main(int argc, char const *argv[])
{set<int> ns;ns.insert(10);ns.insert(20);ns.insert(30);ns.insert(40);// lower_bound(keyElem);//下限返回第一个 key>=keyElem 元素的迭代器。auto it01 = ns.lower_bound(30);cout << *it01 << endl;// upper_bound(keyElem);//上限返回第一个 key>keyElem 元素的迭代器auto it02 = ns.upper_bound(30);cout << *it02 << endl;pair<set<int>::iterator, set<int>::iterator> p = ns.equal_range(30);cout << *(p.first) << endl; // 键是下限cout << *(p.second) << endl; // 值是上限return 0;
}
G map/multimap
map概述
-
键 值 对 的 形 式 存 储 数 据 ,一 个 键 值 对 称 为 一 个 对 组
-
这 一 对 值 可 以 具 有 不 同 的 数 据 类 型 ， 两 个 值 可 以 分 别 用 pair(对 组 ) 的 两 个 公 共 的 成 员
变 量 first(键 ) 和 second(值 )访 问 。
不 允 许 键 重 复
multimap概述
允 许 键 重 复
api
map 构 造 函 数
map<T1, T2> mapTT;//map 默 认 构 造 函 数 : T1:键 的 数 据 类 型 ,要 有 可 比 较 性 ,基 本 数 据 类 型 都 有 可 比 性T2:值 的 数 据 类 型
map(const map &mp);//拷 贝 构 造 函 数map 赋 值 操 作
map& operator=(const map &mp);//重 载 等 号 操 作 符
swap(mp);//交 换 两 个 集 合 容 器map 大 小 操 作
size();//返 回 容 器 中 元 素 的 数 目
empty();//判 断 容 器 是 否 为 空map 插 入 数 据 元 素 操 作
map.insert(...); //往 容 器 插 入 元 素 ， 返 回 pair<iterator,bool>map 删 除 操 作
clear();//删 除 所 有 元 素
erase(pos);//删 除 pos 迭 代 器 所 指 的 元 素 ， 返 回 下 一 个 元 素 的 迭 代 器 。
erase(beg,end);//删 除 区 间 [beg,end)的 所 有 元 素 ， 返 回 下 一 个 元 素 的 迭 代 器 。
erase(keyElem);//删 除 容 器 中 key 为 keyElem 的 对 组 。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 相 等 的 上 下 限 的 两 个 迭 代
器 。
总结
vector 单 端 动 态 数 组 随 机 访 问 迭 代 器 (重 点 )
比 如 软 件 历 史 操 作 记 录 的 存 储 ， 我 们 经 常 要 查 看 历 史 记 录 ， 比 如 上 一 次 的 记 录 ， 上 上 次
的 记 录 ， 但 却 不 会 去 删 除 记 录 ， 因 为 记 录 是 事 实 的 描 述 。
数 据 结 构 :数 组
deque： 双 端 动 态 数 组 随 机 访 问 迭 代 器
deque 的 使 用 场 景 ： 比 如 排 队 购 票 系 统 ， 对 排 队 者 的 存 储 可 以 采 用 deque， 支 持 头 端
的 快 速 移 除 ， 尾 端 的 快 速 添 加
stack栈 容 器 没 有 迭 代 器 先 进 后 出
queue队 列 容 器 没 有 迭 代 器 先 进 先 出
list 链 表 容 器 双 向 迭 代 器 (重 点 )
比 如 公 交 车 乘 客 的 存 储 ， 随 时 可 能 有 乘 客 下 车 ， 支 持 频 繁 的 不 确 实 位 置 元 素 的 移 除 插 入
数 据 结 构 :双 链 表
set 容 器 只 有 键 值 键 值 不 能 重 复 自 动 排 序 只 读 迭 代 器
比 如 对 手 机 游 戏 的 个 人 得 分 记 录 的 存 储 ， 存 储 要 求 从 高 分 到 低 分 的 顺 序 排 列 。
数 据 结 构 :红 黑 树
map容 器 ： 键 值 -实 值 成 对 出 现 键 值 不 能 重 复 自 动 排 序 只 读 迭 代 器 (重 点 )
比 如 按 ID 号 存 储 十 万 个 用 户 ， 想 要 快 速 要 通 过 ID 查 找 对 应 的 用 户 。
数 据 结 构 :红 黑 树
