文章目录
- 前言
- 1、set
- 1.1 set的构造
- 1.2 set的迭代器
- 1.3 set的容量
- 1.4 set修改操作
- 1.5 使用举例
- 2、multiset
- 3、set和multiset小总结
- 4、map
- 4.1 map的构造
- 4.2 map的迭代器
- 4.3 map的容量与元素访问
- 4.4 map中元素的修改
- 4.5 举例说明
- 5、multimap
- 6、map和multimap小总结
前言
在C++STL中，树型结构的关联式容器有4种，分别是set，multiset，map，multimap，它们的底层都是用红黑树实现的，set和multiset包含在<>头文件中，map和multimap包含在<
如果想了解更详细请查看文档-》cplusplus
1、set
1.1 set的构造
| 函数声明 | 功能介绍 |
|---|
| set (const Compare& comp = Compare(), const Allocator& = Allocator() ); | 构造空的set |
| set (InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& = Allocator() ); | 用[first, last)区间中的元素构造set |
| set ( const set& x); | set的拷贝构造 |
1.2 set的迭代器
| 函数声明 | 功能介绍 |
|---|
| iterator begin() | 返回set中起始位置元素的迭代器 |
| iterator end() | 返回set中最后一个元素后面的迭代器 |
| const_iterator cbegin() const | 返回set中起始位置元素的const迭代器 |
| const_iterator cend() const | 返回set中最后一个元素后面的const迭代器 |
| reverse_iterator rbegin() | 返回set第一个元素的反向迭代器，即end() |
| reverse_iterator rend() | 返回set最后一个元素下一个位置的反向迭代器，即rbegin() |
| const_reverse_iterator crbegin() const | 返回set第一个元素的反向const迭代器，即cend() |
| const_reverse_iterator crend() const | 返回set最后一个元素下一个位置的反向const迭代器，即crbegin() |
1.3 set的容量
| 函数声明 | 功能介绍 |
|---|
| bool empty ( ) const | 检测set是否为空，空返回true，否则返回true |
| size_type size() const | 返回set中有效元素的个数 |
1.4 set修改操作
| 函数声明 | 功能介绍 |
|---|
| pair insert ( const value_type& x ) | 在set中插入元素x，实际插入的是构成的键值对，如果插入成功，返回<该元素在set中的位置，true>,如果插入失败，说明x在set中已经存在，返回 |
| void erase ( iterator position ) | 删除set中position位置上的元素 |
| size_type erase ( const key_type& x ) | 删除set中值为x的元素，返回删除的元素的个数 |
| void erase ( iterator first, iterator last ) | 删除set中[first, last)区间中的元素 |
| void swap ( set& st ); | 交换set中的元素 |
| void clear ( ) | 将set中的元素清空 |
| iterator find ( const key_type& x ) const | 返回set中值为x的元素的位置 |
| size_type count ( const key_type& x ) const | 返回set中值为x的元素的个数 |
1.5 使用举例
int main()
{
set s;
s.insert(5);
s.insert(8);
s.insert(1);
s.insert(3);
s.insert(2);
s.insert(2);
s.insert(4);
for (auto& key : s)
cout << key << " ";
cout << endl;
set::iterator pos = s.find(3);//查找值为3的key，找到了就返回迭代器
if (pos != s.end())
s.erase(pos);
s.erase(1);//也可以直接删除
s.erase(30);//set中没有为30的key也不会报错
for (auto& key : s)
cout << key << " ";
cout << endl;
//count可以用来判断在set是否存在key
int count1 = s.count(2);
cout << "出现2的次数: "<< count1 << endl;
int count2 = s.count(100);
cout << "出现100的次数: " << count2 << endl;
//使用迭代器遍历
set::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
2、multiset
mulitset和set的使用基本上一致，接口也大体相同，只是mulitset允许插入多个相同的key。
对于find而言，返回的是一个key的迭代器。
对于erase而言，如果参数是迭代器，则会删除这个迭代器所对应的数据，如果参数是一个key，则会删除multiset中所有的key
使用举例：
int main()
{
multiset s;
s.insert(5);
s.insert(8);
s.insert(1);
s.insert(3);
s.insert(3);
s.insert(2);
s.insert(2);
s.insert(2);
s.insert(2);
s.insert(4);
s.insert(4);
for (auto& key : s)
cout << key << " ";
cout << endl;
set::iterator pos = s.find(3);//查找值为3的key，找到了就返回迭代器
//删除迭代器所对应的key
if (pos != s.end())
s.erase(pos);
s.erase(4);//删除s中所有的4
s.erase(30);//multiset中没有为30的key也不会报错
cout << "删除了一个3和所有的4-->";
for (auto& key : s)
cout << key << " ";
cout << endl;
//count可以用来判断在multiset是否存在key，但是一般用find来判断
int count1 = s.count(2);
cout << "出现2的次数: "<< count1 << endl;
int count2 = s.count(100);
cout << "出现100的次数: " << count2 << endl;
//使用迭代器遍历
cout << "使用迭代器遍历: ";
set::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
3、set和multiset小总结
- set/multiset中只放key(value)，但在底层实际存放的是由构成的键值对
- set/multiset中插入元素时，只需要插入key(value)即可，不需要构造键值对
- set中的元素不可以重复(因此可以使用set进行去重)，而multiset中的元素可以重复
- 使用set/multiset的迭代器遍历set中的元素，可以得到有序序列
- set/multiset中的元素默认按照小于来比较
- 中查找某个元素，时间复杂度为：log2(n)
4、map
4.1 map的构造
| map (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); | 构造空的map |
|---|
| map (InputIterator first, InputIterator last, key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type()); | 用[first, last)区间中的元素构造set |
| map (const map& x) | map的拷贝构造 |
4.2 map的迭代器
| 函数声明 | 功能介绍 |
|---|
| iterator begin() | 返回map中起始位置元素的迭代器 |
| iterator end() | 返回map中最后一个元素后面的迭代器 |
| const_iterator cbegin() const | 返回map中起始位置元素的const迭代器 |
| const_iterator cend() const | 返回map中最后一个元素后面的const迭代器 |
| reverse_iterator rbegin() | 返回map第一个元素的反向迭代器，即end() |
| reverse_iterator rend() | 返回map最后一个元素下一个位置的反向迭代器，即rbegin() |
| const_reverse_iterator crbegin() const | 返回map第一个元素的反向const迭代器，即cend() |
| const_reverse_iterator crend() const | 返回最后一个元素下一个位置的反向const迭代器，即crbegin() |
4.3 map的容量与元素访问
| 函数声明 | 功能介绍 |
|---|
| bool empty ( ) const | 检测map中的元素是否为空，是返回true，否则返回 false |
| size_type size() const | 返回map中有效元素的个数 |
| mapped_type& operator[] (const key_type& k) | 返回去key对应的value |
4.4 map中元素的修改
| 函数声明 | 功能介绍 |
|---|
| pair insert ( const value_type& x ) | 在map中插入键值对x，注意x是一个键值对，返回值也是键值对：iterator代表新插入元素的位置，bool代表释放插入成功 |
| void erase ( iterator position ) | 删除position位置上的元素 |
| size_type erase ( const key_type& x ) | 删除键值为x的元素 |
| void erase ( iterator first, iterator last ) | 删除[first, last)区间中的元素 |
| void swap ( map& mp ) | 交换两个map中的元素 |
| void clear ( ) | 将map中的元素清空 |
| iterator find ( const key_type& x ) | 在map中插入key为x的元素，找到返回该元素的位置的迭代器，则返回end |
| const_iterator find ( const key_type& x ) const | 在map中插入key为x的元素，找到返回该元素的位置的const迭代器，否则返回cend |
| size_type count ( const key_type& x ) const | 返回key为x的键值在map中的个数，注意map中key是唯一的，因此该函数的返回值要么为0，要么为1，因此也可以用该函数来检测一个key是否在map中 |
4.5 举例说明
int main()
{
map m;
//第一种插入方式
m.insert(pair(4, 4));
m.insert(pair(6, 6));
//第二种插入方式
m.insert(make_pair(1, 1));
m.insert(make_pair(3, 3));
m.insert(make_pair(2, 2));
//第三种插入方式
m.insert({ 5, 5 });
//第四种插入方式,使用[]
//operator[]的原理是：
//用构造一个键值对，然后调用insert()函数将该键值对插入到map中
//如果key已经存在，插入失败，insert函数返回该key所在位置的迭代器
//如果key不存在，插入成功，insert函数返回新插入元素所在位置的迭代器
//operator[]函数最后将insert返回值键值对中的value引用
//value& operator[] (const key_type& k);
//(*((this->insert(make_pair(k,mapped_type()))).first)).second
m[7] = 7;
for (auto & num : m)
{
cout << num.first << " " << num.second << " ";
}
cout << endl;
map::iterator pos = m.find(3);//查找3是否在map中，如果在则返回3的迭代器
if (pos != m.end())
m.erase(pos);
m.erase(4);//删除map中的key为4的键值对
m.erase(100);//如果key不存在也不会报错
for (auto & num : m)
{
cout << num.first << " " << num.second << " ";
}
cout << endl;
//修改key所对应的val
m[3] = 100;
//如果map中不存在，则会添加
m[50] = 50;
for (auto & num : m)
{
cout << num.first << " " << num.second << " ";
}
cout << endl;
//使用迭代器遍历
map::iterator it = m.begin();
while (it != m.end())
{
cout << it->first << " " << it->second << " ";
++it;
}
cout << endl;
}
5、multimap
multimap和map的使用基本上一致，接口也大体相同，只是multimap允许插入多个相同的key。
对于find而言，返回的是一个key的迭代器。
对于erase而言，如果参数是迭代器，则会删除这个迭代器所对应的数据，如果参数是一个key，则会删除multimap中key所对应的所有键值对。
使用举例：
int main()
{
multimap m;
//第一种插入方式
m.insert(pair(4, 4));
m.insert(pair(6, 6));
//第二种插入方式
m.insert(make_pair(1, 1));
m.insert(make_pair(3, 3));
m.insert(make_pair(2, 2));
m.insert(make_pair(2, 2));
m.insert(make_pair(2, 2));
//第三种插入方式
m.insert({ 5, 5 });
m.insert({ 4, 4 });
m.insert({ 4, 4 });
m.insert({ 4, 4 });
//mulitmap不支持[]
for (auto & num : m)
{
cout << num.first << " " << num.second << " ";
}
cout << endl;
map::iterator pos = m.find(3);//查找3是否在multimap中，如果在则返回3的迭代器
if (pos != m.end())
m.erase(pos);
//连续删除，将key为2的键值对全部删除
pos = m.find(2);
while (pos != m.end() && pos->first == 2)
{
//先保存下一个迭代器，因为将pos删除则会导致迭代器失效
auto next = pos;
++next;
m.erase(pos);
pos = next;
}
m.erase(4);//删除multimap中key为4的键值对,如果存在多个，则全部删除
m.erase(100);//如果key不存在也不会报错
//使用迭代器遍历
map::iterator it = m.begin();
while (it != m.end())
{
cout << it->first << " " << it->second << " ";
++it;
}
cout << endl;
}
6、map和multimap小总结
- map中的key是不可以重复的，multimap中的key是可以重复的
- 使用set/multiset的迭代器遍历set中的元素，可以得到有序序列
- multimap中的元素默认将key按照小于来比较
- map支持[]的重载，multimap不支持[]的重载
