0%

set与map的基本使用及特性

set

  1. 实现—->目前使用搜索树实现(红黑树)
  2. 底层是一个存放KV结构的搜索树,但是此处K、V相同
  3. set中只需要存放value
  4. set中不能存放重复的元素
  5. set中的元素不能修改,不支持修改的操作
  6. set默认比较是小于,可以通过修改仿函数,修改比较逻辑
  7. 迭代器遍历有序:底层顺序是二叉搜索树的中序遍历
  8. 迭代器只能读取内容,不能修改内容
  9. 插入:如果用迭代器指定插入位置,最终实际的插入位置可能不是指定的位置,此处的位置只是一个建议,新的元素的插入位置必须符合搜索树的性质
  10. 删除会导致当前删除位置的迭代器失效,但是不影响其他位置的迭代器
  11. find:找到返回元素的迭代器,未找到返回end迭代器
  12. count:获取指定元素在set中的个数,根据性质4,只用两个值,1或0

基本使用与遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
set<int> s;

int arr[] = { 10,3,2,8,11 };
set<int> s2(arr, arr + 5);

set<int> copy(s2);

set<int>::iterator it = s2.begin();
while (it != s2.end())
{
cout << *it << " ";
it++;
}//2,3,8,10,11
cout << endl;

set<int>::const_iterator cit = s2.cbegin();

set<int>::reverse_iterator rit = s2.rbegin();//11, 10, 8, 3, 2

set元素不能被修改

遍历有序:搜索树的中序遍历

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int arr[] = { 10,3,2,8,11 };
set<int> s2(arr, arr + 5);
PrntSet(s2);//2,3,8,10,11
s2.insert(6);
PrntSet(s2);//2,3,6,8,10,11
s2.insert(s2.begin(), 15);
//itreator只是一个建议,新插入的元素不一定是指定位置,最终插入位置需要遵循搜索树的性质
PrntSet(s2);//2,3,6,8,10,11,15
int arr2[] = { 9, 7, 20, 0 };
s2.insert(arr2, arr2 + 4);
PrntSet(s2);//0,2,3,6,7,8,9,10,11,15,20
s2.insert(10);
//set不会插入重复元素
PrntSet(s2);//0,2,3,6,7,8,9,10,11,15,20

删除

1
2
3
4
5
6
7
8
9
//删除时候传入的位置必须有效
s2.erase(10);//删除10
PrntSet(s2);//0,2,3,6,7,8,9,11,15,20
s2.erase(s2.begin());//删除最左节点
PrntSet(s2);//2,3,6,7,8,9,10,11,15,20
//s2.erase(s2.end());//end指向最后一个元素的下一个位置,此时运行会报错
//PrntSet(s2);
s2.erase(s2.begin(), s2.end());
PrntSet(s2);

删除操作会导致当前位置的迭代器失效,不影响其他位置

查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int arr[] = { 10,3,2,8,11 };
set<int> s2(arr, arr + 5);

set<int>::iterator it = s2.find(2);
if (it != s2.end())
cout << *it << endl;
else
cout << "NONE" << endl;

set<int>::iterator it2 = s2.find(100);
if (it2 != s2.end())
cout << *it2 << endl;
else
cout << "NONE" << endl;

//count返回:元素个数,存在返回1,否则0
cout << s2.count(11) << endl;
cout << s2.count(100) << endl;

map

  1. 实现:通过二叉搜索树实现(红黑树)
  2. 底层结构为存放kv键值对的搜索树,k和v不一定相同
  3. map存放kv键值对,即pair数据
  4. key不能重复,value可以重复
  5. key不允许修改,value可以修改
  6. map默认比较是小于,按照key进行比较,可以通过修改仿函数,修改比较逻辑
  7. 迭代器遍历顺序:底层顺序是二叉搜索树的中序遍历,但是按照key的中序遍历进行
  8. 迭代器可以修改value,不能修改key
  9. 插入:如果用迭代器指定插入位置,最终实际的插入位置可能不是指定的位置,此处的位置只是一个建议,新的元素的插入位置必须符合搜索树的性质
  10. 删除会导致当前删除位置的迭代器失效,但是不影响其他位置的迭代器
  11. find:找到返回元素的迭代器,未找到返回end迭代器,==按照key查找==
  12. count:获取指定元素在set中的个数,根据性质4,只用两个值,1或0, ==按照key查找==
  13. operator[ ]:可读可写可插入
  14. at:如果key不存在,抛异常

基本使用以及遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<map>
void test()
{
map<string, int> m;//key:字符串,value:数值
vector<pair<string, int>> vec;
for(int i = 0; i < 10; i ++)
{
pair<string, int> p((string)"abc" + (char)(i + '0'), 5);
vec.push_back(p);
vec.push_back(pair<string, int>((string)"zzl"+ (char)(i + '0'), 14));
vec.push_back(make_pair((string)"xyz"+ (char)(i + '0'), 3));
}

map<string, int> m2(vec.begin(), vec.end());
map<string, int> copy(m2);

cout << m2.size() << endl;//30

map<string, int>::iterator it = m2.begin();
while(it != m2.end())
{
cout << it->first << "--->" << it->second << endl;
it++;
}

map<string, int>::iterator it = m2.begin();
while(it != m2.end())
{
it->second = 100;//map的非const迭代器支持修改value,但不支持修改key
it++;
}

map<int, int> mm;
cout << mm.at(2) << endl;//key不存在,抛异常
cout << mm[2] << endl;//key不存在,插入
}
  • map中key不能重复,但是value可以
  • 迭代器解引用类型:pair
  • 迭代器遍历顺序:key的递增顺序
  • 非const迭代器支持value修改,不支持key修改
  • at:key不存在,抛异常
  • operator[]:key不存在,插入

插入

1
2
3
4
5
6
7
8
map<int, int> m;
pair<map<int, int>::iterator, bool> ret = m.insert(make_pair(3, 3));//插入成功
cout << ret.first->first << "--->" << ret.first->second << endl;//3--->3
cout << ret.second << endl;//1

ret = m.insert(make_pair(3, 10));//key重复,插入失败
cout << ret.first->first << "--->" << ret.first->second << endl;//3--->3
cout << ret.second << endl;//0

pair<iterator, bool>iterator

  • map中kv键值对 对应的迭代器,bool:插入是否成功

插入成功:iterator表示新插入的kv键值对的迭代器

插入失败:iterator表示已经存在的某个kv键值对的迭代器

1
2
3
4
5
6
7
8
map(int, int) m;
m[1] = 1;//1--->1
m[2] = 2;//2--->2
m[3] = 3;//3--->3
m[4] = 4;//4--->4

m[3] = 100;
m[1] = -1;

value& operator[](key)

(*((this->insert(make_pair(k, mapped_type())).first)).second

  1. 创建一个kv键值对:key value 默认值
  2. 执行插入操作,插入第一步创建的kv键值对
  3. 获取插入接口返回值的第一个迭代器成员
    1. prir<iterator,bool>.first —-> iterator —-> 指向map中的一个键值对
    2. 插入成功:返回新的kv键值对的迭代器
    3. 插入失败:返回已经存在的键值key的kv键值对的迭代器
  4. 解引用第三步拿到的迭代器
  5. 获取迭代器指向的kv键值对的value

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
map(int, int) m;
m[1] = 1;//1--->1
m[2] = 2;//2--->2
m[3] = 3;//3--->3
m[4] = 4;//4--->4

m[3] = 100;
m[1] = -1;

map<int, int>::iterator it = m.begin();
cout << it->first << "--->" << it->second << endl;
m.erase(it);
cout << it->first << "--->" << it->second << endl;//删除会导致指向当前位置的迭代器失效

查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
map(int, int) m;
m[1] = 1;//1--->1
m[2] = 2;//2--->2
m[3] = 3;//3--->3
m[4] = 4;//4--->4

m[3] = 100;
m[1] = -1;

map<int, int>::iterator it = m.begin();
it = m.find(3);//按照key查找,存在返回指向目标的迭代器,否则返回end迭代器
it = m.find(100);

cout << m.count(3) << endl;//按照key值查找,存在返回1,否则返回0
cout << m.count(100) << endl;

multiset和multimap

与set及map最大的区别是其元素可以重复

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void testSet()
{
multiset<int> s;
s.insert(1);
s.insert(2);
s.insert(9);
s.insert(-1);
s.insert(18);
s.insert(15);

for (const auto& e : s)
cout << e << " ";
cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void testMap()
{
//multimap不提供[]操作符重载,at函数
multimap<int, int> m;
m.insert(make_pair(1, 1));
m.insert(make_pair(10, 1));
m.insert(make_pair(1, 1));
m.insert(make_pair(0, 1));
m.insert(make_pair(1, 1));

for (const auto& e : m)
cout << e.first << "--->" << e.second << endl;

//pair<multimap<int, int>::iterator, multimap<int, int>::iterator> p = m.equal_range(1);
auto p = m.equal_range(1);
multimap<int, int>::iterator it = p.first;
while (it != p.second)
{
cout << it->first << "--->" << it->second << endl;
it++;
}
}
-------------本文结束感谢您的阅读-------------