网站交互式体验,wordpress html5 支持,做课件的网站,wordpress学校主题目录 一、关联式容器二、键值对三、树形结构的关联式容器3.1 set3.1.1 模板参数列表3.1.2 构造3.1.3 迭代器3.1.4 容量3.1.5 修改操作 3.2 multiset3.3 map3.3.1 模板参数列表3.3.2 构造3.3.3 迭代器3.3.4 容量3.3.5 修改操作3.3.6 operator[] 3.4 multimap 一、关联式容器
谈… 目录 一、关联式容器二、键值对三、树形结构的关联式容器3.1 set3.1.1 模板参数列表3.1.2 构造3.1.3 迭代器3.1.4 容量3.1.5 修改操作 3.2 multiset3.3 map3.3.1 模板参数列表3.3.2 构造3.3.3 迭代器3.3.4 容量3.3.5 修改操作3.3.6 operator[] 3.4 multimap 一、关联式容器
谈到关联式容器先来说说序列式容器以前学习的vector、list、deque等就是序列式容器它们的特点是底层为线性序列的数据结构存储的是元素本身。关联式容器也是存储数据的不同的是里面存储的是key, value结构的键值对在数据检索时比序列式容器效率更高。
二、键值对
键值对是用来表示一一对应关系的结构该结构中一般只包含两个成员变量key和valuekey代表键值value表示与key对应的信息比如汉英互译字典查中文就可以找到对应的英文是有对应关系的。
键值对的定义
template class T1, class T2
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(): first(T1()), second(T2())
{}
pair(const T1 a, const T2 b): first(a), second(b)
{}
};三、树形结构的关联式容器
STL总共有两种结构的关联式容器分别是哈希结构和树形结构。树形结构主要有4种set、multiset、map、multimap它们的共同点是底层是平衡搜索树即红黑树实现的且容器中的元素是一个有序的序列。
3.1 set
特点
遍历set中的元素可以得到一个有序序列因为它的底层实现是红黑树再底层是二叉搜索树遍历方式是中序遍历。set中的元素不可以重复因此可以用set去重。与map/multimap不同map/multimap中存储的是真正的键值对key, valueset中只放value但在底层实际存放的是由value, value构成的键值对。set中插入元素时只需要插入value即可不需要构造键值对。set中的元素默认按照小于来比较。set中查找某个元素时间复杂度为logN即最多高度次。在内部set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。set容器通过key访问单个元素的速度通常比unordered_set容器慢但它们允许根据顺序对子集进行直接迭代。set中的元素不允许修改因为修改了其中的一个元素会改变内部的结构从而影响有序性。set在底层是用二叉搜索树(红黑树)实现的。
3.1.1 模板参数列表 T: set中存放元素的类型实际在底层存储value, value的键值对。Compareset中元素默认按照小于来比较。Allocset中元素空间的管理方式使用STL提供的空间配置器管理。
3.1.2 构造
1️⃣构造空的set
setint s;2️⃣用迭代器区间构造
setint s1(s.begin(), s.end());3️⃣拷贝构造
setint s2(s);3.1.3 迭代器
1️⃣beginend 正向遍历 setint s;s.insert(1);s.insert(3);s.insert(3);s.insert(3);s.insert(5);s.insert(2);setint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;这里顺便检验下是否去重且有序
2️⃣rbeginrend 与上面类似只不过是反向遍历 setint::reverse_iterator rit s.rbegin();while (rit ! s.rend()){cout *rit ;rit;}cout endl;3.1.4 容量
1️⃣empty 判断set是否为空空返回true否则返回true setint s;cout s.empty() endl;//12️⃣size 返回set中有效元素的个数
setint s;
s.insert(1);
s.insert(3);
s.insert(3);
s.insert(3);
s.insert(5);
s.insert(2);
cout s.size() endl;//43.1.5 修改操作
1️⃣insert pairiterator,bool insert ( const value_type x ) 在set中插入元素x实际插入的是x, x构成的键值对如果插入成功返回该元素在set中的位置true,如果插入失败说明x在set中已经存在返回x在set中的位置false。
setint s;
s.insert(1);
s.insert(3);
s.insert(3);
s.insert(3);
s.insert(5);
s.insert(2);
for (auto e : s)
{cout e ;
}
cout endl;2️⃣erase 删除有三种方式
删除set中position位置上的元素 void erase ( iterator position ) setint s;
s.insert(1);
s.insert(3);
s.insert(5);
s.insert(2);
for (auto e : s)
{cout e ;
}
cout endl;
setint::iterator pos s.begin();
s.erase(pos);
for (auto e : s)
{cout e ;
}删除set中值为x的元素返回删除的元素的个数 size_type erase ( const key_type x ) setint s;
s.insert(1);
s.insert(3);
s.insert(5);
s.insert(2);
for (auto e : s)
{cout e ;
}
cout endl;
s.erase(3);
for (auto e : s)
{cout e ;
}删除set中[first, last)区间中的元素 void erase ( iterator first, iterator last ) setint s;
s.insert(1);
s.insert(3);
s.insert(5);
s.insert(2);
for (auto e : s)
{cout e ;
}
cout endl;
s.erase(s.begin(), s.end());
for (auto e : s)
{cout e ;
}3️⃣swap 交换set中的元素 void swap ( setKey,Compare,Allocator st ); setint s1;s1.insert(1);s1.insert(3);s1.insert(5);for (auto e : s1){cout e ;//1 3 5}cout endl;setint s2;s2.insert(7);s2.insert(8);s2.insert(6);for (auto e : s2){cout e ; //6 7 8}cout endl;s2.swap(s1);for (auto e : s1){cout e ;//6 7 8}cout endl;for (auto e : s2){cout e ;//1 3 5}4️⃣clear 将set中的元素清空 void clear ( ) setint s1;
s1.insert(1);
s1.insert(3);
s1.insert(5);
s1.clear();
for (auto e : s1)
{cout e ;// 空
}5️⃣find 找到了返回set中值为x的元素的位置如果每找到返回最后一个元素的下一个位置 iterator find ( const key_type x ) const setint s1;
s1.insert(1);
s1.insert(3);
s1.insert(5);
//s1.clear();
setint::iterator pos s1.find(3);
if (pos ! s1.end())cout 找到了 endl;//找到了
elsecout 没找到 endl;6️⃣count 返回set中值为x的元素的个数因为set是去重的所以存在返回1不存在返回0 size_type count ( const key_type x ) const setint s1;
s1.insert(1);
s1.insert(3);
s1.insert(5);
cout s1.count(3) endl;//1
cout s1.count(33) endl;//03.2 multiset
multiset与set的区别是存储的元素可以重复
void test_set8()
{multisetint s;s.insert(1);s.insert(3);s.insert(3);s.insert(5);s.insert(5);s.insert(5);s.insert(2);for (auto e : s){cout e ;//1 2 3 3 5 5 5}
}还有接口与set的不同分别是find和count set的find与multiset的find set不能有重复元素所以找到了返回该元素的位置multiset有重复元素找到了返回该元素的第一个的位置。找不到都是返回end() multisetint s;
s.insert(1);
s.insert(3);
s.insert(3);
multisetint::iterator pos s.find(3);//返回第一个3的位置
while (pos ! s.end())
{cout *pos ;// 3 3pos;
}
cout endl;
}set的count与multiset的count set没有重复元素所以存在的元素返回1不存在返回0multiset有重复元素所以存在返回该元素的个数不存在返回0 multisetint s;
s.insert(1);
s.insert(3);
s.insert(3);
s.insert(3);
s.insert(3);
cout s.count(3) endl;//43.3 map
与sert一样map可以使容器的元素有序且去重 特点
map中的元素是键值对由key和value组成在map中键值key通常用于排序和惟一地标识元素而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同并且在map的内部key与value通过成员类型value_type绑定在一起为其取别名称为pair—— typedef pairconst key, T value_type;在内部map中的元素总是按照键值key进行比较排序的map中的key是唯一的并且不能修改map中通过键值访问单个元素的速度通常比unordered_map容器慢但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时可以得到一个有序的序列)。map支持下标访问符可以进行插入、查找和修改map的底层为平衡搜索树(红黑树)
3.3.1 模板参数列表 key: 键值对中key的类型T 键值对中value的类型Compare: 比较器的类型map中的元素是按照key来比较的缺省情况下按照小于来比较一般情况下(内置类型元素)该参数不需要传递如果无法比较时(自定义类型)需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)Alloc通过空间配置器来申请底层空间不需要用户传递除非用户不想使用标准库提供的空间配置器
3.3.2 构造
1️⃣构造空的map
mapstring, string m;2️⃣用迭代器区间进行构造
mapstring, string m1(m.begin(), m.end());3️⃣拷贝构造
mapstring, string m2(m);3.3.3 迭代器
1️⃣begin和end 正向遍历
mapstring, string m;
m.insert(pairstring, string(sort, 排序));
m.insert(pairstring, string(apple, 苹果));
m.insert(pairstring, string(left, 左边));
mapstring, string::iterator it m.begin();
while (it ! m.end())
{cout *it ;//错误写法编译报错it;
}因为map的每个元素是键值对由key和value组成即pair而且它们的类型不一定相同所以要用 . 或者 - 指向对应的成员
mapstring, string m;
m.insert(pairstring, string(sort, 排序));
m.insert(pairstring, string(sort, 排序));
m.insert(pairstring, string(sort, 排序));
m.insert(pairstring, string(apple, 苹果));
m.insert(pairstring, string(left, 左边));
mapstring, string::iterator it m.begin();
while (it ! m.end())
{//cout (*it).first (*it).second endl;cout it-first it-second endl;it;
}2️⃣rbegin和rend 反向遍历
mapstring, string::reverse_iterator rit m.rbegin();
while (rit ! m.rend())
{//cout (*rit).first (*rit).second endl;cout rit-first rit-second endl;rit;
}3.3.4 容量
1️⃣empty 检测map中的元素是否为空是返回true否则返回false
mapstring, string m;
cout m.empty() endl;//12️⃣size 返回map中有效元素的个数
m.insert(pairstring, string(left, 左边));
cout m.size() endl;//13.3.5 修改操作
1️⃣insert pairiterator,bool insert ( const value_type x ) 在map中插入的是键值对返回值也是键值对如果插入成功则返回当前元素(键值对)的位置和true插入失败则返回原来已有的元素的位置和false
插入的方式有三种写法
mapstring, string m;
m.insert(pairstring, string(sort, 排序));//C98
m.insert(make_pair(apple, 苹果));//C98
m.insert({ left, 左边 }); //C11 多参数隐式类型转换2️⃣erase 删除有3种方式与set相同
删除position位置上的元素 void erase ( iterator position ) mapstring, string m;
m.insert(make_pair(sort, 排序));
m.insert(make_pair(apple, 苹果));
m.insert(make_pair(left, 左边));
for (auto e : m)
{cout e.first e.second ;
}
cout endl;
mapstring, string::iterator pos m.begin();
m.erase(pos);
for (auto e : m)
{cout e.first e.second ;
}删除键值为x的元素 size_type erase ( const key_type x ) m.erase(sort);删除[first, last)区间中的元素 void erase ( iterator first, iterator last ) m.erase(m.begin(), m.end());3️⃣swap 交换两个map中的元素 void swap ( mapKey,T,Compare,Allocator mp ) mapstring, string m1;
m1.insert(make_pair(sort, 排序));
m1.insert(make_pair(apple, 苹果));
for (auto e : m1)
{cout e.first e.second ;
}
mapstring, string m2;
m2.insert(make_pair(left, 左边));
m2.insert(make_pair(right, 右边));
for (auto e : m2)
{cout e.first e.second ;
}
m2.swap(m1);
for (auto e : m1)
{cout e.first e.second ;
}
for (auto e : m2)
{cout e.first e.second ;
}4️⃣clear 将map中的元素清空 void clear ( ) mapstring, string m;
m.insert(make_pair(sort, 排序));
m.clear();
cout m.empty() endl;//15️⃣find 查找key为x的元素找到了返回该元素的迭代器找不到返回end iterator find ( const key_type x ) mapstring, string m;
m.insert(make_pair(sort, 排序));
mapstring, string::iterator pos m.find(sort);
if (pos ! m.end())cout 找到了 endl;//找到了
elsecout 没找到 endl;6️⃣count 返回key为x在map中的个数由于map会去重所以存在返回1不存在返回0 size_type count ( const key_type x ) const mapstring, string m;
m.insert(make_pair(sort, 排序));
m.insert(make_pair(sort, 排序));
cout m.count(sort) endl;//1
cout m.count(apple) endl;//03.3.6 operator[] mapped_type operator[] (const key_type k); 该函数的参数是key返回值是value。可以用来插入、查找、修改和计数。先来看看使用
1️⃣插入如果key没有重复插入成功
mapstring, string m;
m.insert(make_pair(sort, 排序));
m[left];//插入
for (auto e : m)
{cout e.first e.second endl;
}2️⃣查找插入的key已经存在查找到该key对应的value
mapstring, string m;
m.insert(make_pair(sort, 排序));
m.insert(make_pair(apple, 苹果));
cout m[apple] endl;//苹果3️⃣修改插入的key已经存在同时右边如下代码所示将该key对应的value修改
mapstring, string m;
m.insert(make_pair(sort, 排序));
m.insert(make_pair(apple, 苹果));
m[sort] 排序的英文;
for (auto e : m)
{cout e.first e.second endl;
}4️⃣插入修改插入key没有重复且右边如下代码所示修改对应的value(其实是补上)
mapstring, string m;
m.insert(make_pair(sort, 排序));
m.insert(make_pair(apple, 苹果));
m[left] 左边;
for (auto e : m)
{cout e.first e.second endl;
}5️⃣统计次数
mapstring, int m;
string arr[] { sort,sort ,apple ,apple, banana,one };
for (auto e : arr)
{m[e];
}
for (auto e : m)
{cout e.first e.second ;cout endl;
}接下来看看operator[]是如何实现以上操作的
operator[]内部其实调用了insert函数 我们再来看看insert函数 回顾下insert函数的要插入的数据类型是键值对 它的返回类型也是键值对operator[]调用insert函数得到的返回值是迭代器对迭代器解引用然后点访问迭代器的第二个成员最后返回该成员。
梳理下 首先看operator[]调用insert函数而insert里面的make_pair是(k, mapped_type())也就是说key值是要输入的而value我们不写编译器帮我们默认构造出来int类型是0。接着insert函数就要返回了返回的是键值对插入成功返回该位置的迭代器和true插入失败返回该位置的迭代器和false。.first得到返回值的第一个成员即迭代器。迭代器的本质是指针指针指向的是该位置的key和对应的value解引用指针然后最后的 .second 得到是该迭代器的value即插入的key对应的value
3.4 multimap
multimap与map的区别和multiset与set的区别相同都能形成有序但是multimap可以允许元素重复
multimapstring, string m;
m.insert(make_pair(sort, 排序));
m.insert(make_pair(sort, 排序));
m.insert(make_pair(left, 左边));
m.insert(make_pair(sort, 排序));
m.insert(make_pair(apple, 苹果));
m.insert(make_pair(apple, 苹果));
for (auto e : m)
{cout e.first e.second ;cout endl;
}还有find和count: map的find与multimap的find map返回该元素的迭代器multimap返回该元素的第一个的迭代器 multimapstring, string m;
m.insert(make_pair(sort, 排序));
m.insert(make_pair(sort, 排序));
m.insert(make_pair(apple, 苹果));
multimapstring, string::iterator pos m.find(sort);
while (pos ! m.end())
{cout pos-first pos-second endl;pos;
}map的count与multimap的count map没有重复元素所以该元素存在返回1不存在返回0multimap可以有重复元素存在返回该元素的个数不存在返回0 multimapstring, string m;
m.insert(make_pair(sort, 排序));
m.insert(make_pair(sort, 排序));
m.insert(make_pair(apple, 苹果));
cout m.count(sort) endl;//2
cout m.count(apple) endl;//1
cout m.count(left) endl;//0
