🔥个人主页： Forcible Bug Maker

🔥专栏： STL || C++

目录

🌈前言🌈关于set🔥容量函数==empty====size==

🔥Modifiers==insert====erase====clear==

🔥Operations==find====count====lower_bound和upper_bound====equal_range==

🌈关于multiset🌈结语

🌈前言

本篇博客主要内容：STL库中set的介绍以及其用法的讲解。

set和map的底层结构是红黑树，而红黑树又是一种特殊的二叉搜索树（红黑树可以保持树的平衡）。而我们今天来学习什么是set，以及如何使用set这个容器。如果对二叉搜索树不了解，可以参考这篇：【数据结构进阶】二叉搜索树

🌈关于set

set是按照一定次序存储元素的容器在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。set在底层是用二叉搜索树(红黑树)实现的。

🔥容量函数

empty

判断set对象是否为空。

<code>#include<iostream>

#include<set>

using namespace std;

int main()

{

set<int> se;

cout << se.empty() << endl;

se.insert(1);

cout << se.empty() << endl;

return 0;

}

size

返回set对象中的元素个数。

<code>#include <iostream>

#include <set>

int main ()

{

std::set<int> myints;

std::cout << "0. size: " << myints.size() << '\n';

for (int i=0; i<10; ++i) myints.insert(i);

std::cout << "1. size: " << myints.size() << '\n';

myints.insert (100);

std::cout << "2. size: " << myints.size() << '\n';

myints.erase(5);

std::cout << "3. size: " << myints.size() << '\n';

return 0;

}

🔥Modifiers

insert

支持三种重载：

single element (1)

单个元素插入

<code>pair<iterator,bool> insert (const value_type& val);

with hint (2)

暗示插入

iterator insert (iterator position, const value_type& val);

range (3)

迭代器区间插入

template <class InputIterator>

void insert (InputIterator first, InputIterator last);

// set::insert (C++98)

#include <iostream>

#include <set>

int main ()

{

std::set<int> myset;

std::set<int>::iterator it;

std::pair<std::set<int>::iterator,bool> ret;

// set some initial values:

for (int i=1; i<=5; ++i) myset.insert(i*10); // set: 10 20 30 40 50

ret = myset.insert(20); // no new element inserted

if (ret.second==false) it=ret.first; // "it" now points to element 20

myset.insert (it,25); // max efficiency inserting

myset.insert (it,24); // max efficiency inserting

myset.insert (it,26); // no max efficiency inserting

int myints[]= { 5,10,15}; // 10 already in set, not inserted

myset.insert (myints,myints+3);

std::cout << "myset contains:";

for (it=myset.begin(); it!=myset.end(); ++it)

std::cout << ' ' << *it;

std::cout << '\n';

return 0;

}

erase

(1)

通过迭代器指向直接删除

<code>void erase (iterator position);

(2)

通过值的查找删除，同时返回删除元素的个数

size_type erase (const value_type& val);

(3)

迭代器区间删除

void erase (iterator first, iterator last);

#include <iostream>

#include <set>

int main ()

{

std::set<int> myset;

std::set<int>::iterator it;

// insert some values:

for (int i=1; i<10; i++) myset.insert(i*10); // 10 20 30 40 50 60 70 80 90

it = myset.begin();

++it; // "it" points now to 20

myset.erase (it);

myset.erase (40);

it = myset.find (60);

myset.erase (it, myset.end());

std::cout << "myset contains:";

for (it=myset.begin(); it!=myset.end(); ++it)

std::cout << ' ' << *it;

std::cout << '\n';

return 0;

}

clear

将set对象中所有的元素清空。

size变为0。

<code>#include <iostream>

#include <set>

int main ()

{

std::set<int> myset;

myset.insert (100);

myset.insert (200);

myset.insert (300);

std::cout << "myset contains:";

for (std::set<int>::iterator it=myset.begin(); it!=myset.end(); ++it)

std::cout << ' ' << *it;

std::cout << '\n';

myset.clear();

myset.insert (1101);

myset.insert (2202);

std::cout << "myset contains:";

for (std::set<int>::iterator it=myset.begin(); it!=myset.end(); ++it)

std::cout << ' ' << *it;

std::cout << '\n';

return 0;

}

🔥Operations

find

查找set对象中的某个元素，返回指向此元素的迭代器；如不存在，返回迭代器<code>set::end。

#include <iostream>

#include <set>

int main ()

{

std::set<int> myset;

std::set<int>::iterator it;

// set some initial values:

for (int i=1; i<=5; i++) myset.insert(i*10); // set: 10 20 30 40 50

it=myset.find(20);

myset.erase (it);

myset.erase (myset.find(40));

std::cout << "myset contains:";

for (it=myset.begin(); it!=myset.end(); ++it)

std::cout << ' ' << *it;

std::cout << '\n';

return 0;

}

count

查找并返回set对象中和val值相等的值的个数。

<code>#include <iostream>

#include <set>

int main ()

{

std::set<int> myset;

// set some initial values:

for (int i=1; i<5; ++i) myset.insert(i*3); // set: 3 6 9 12

for (int i=0; i<10; ++i)

{

std::cout << i;

if (myset.count(i)!=0)

std::cout << " is an element of myset.\n";

else

std::cout << " is not an element of myset.\n";

}

return 0;

}

在set中，此函数显得比较没用，因为set中每个元素最多只有一个。但是在mutiset中就大不相同了，mutiset允许数据冗余。

lower_bound和upper_bound

<code>iterator lower_bound (const value_type& val) const;

返回set对象中 大于等于（>=）val 的第一个元素的迭代器·。

<code>iterator upper_bound (const value_type& val) const;

返回set对象中 大于（>）val 的第一个元素的迭代器。

// set::lower_bound/upper_bound

#include <iostream>

#include <set>

int main ()

{

std::set<int> myset;

std::set<int>::iterator itlow,itup;

for (int i=1; i<10; i++) myset.insert(i*10); // 10 20 30 40 50 60 70 80 90

itlow=myset.lower_bound (30); // ^

itup=myset.upper_bound (60); // ^

myset.erase(itlow,itup); // 10 20 70 80 90

std::cout << "myset contains:";

for (std::set<int>::iterator it=myset.begin(); it!=myset.end(); ++it)

std::cout << ' ' << *it;

std::cout << '\n';

return 0;

}

equal_range

<code>pair<iterator,iterator> equal_range (const value_type& val) const;

返回一个pair，其中是与val值相等的set对象的迭代器区间。

// set::equal_elements

#include <iostream>

#include <set>

int main ()

{

std::set<int> myset;

for (int i=1; i<=5; i++) myset.insert(i*10); // myset: 10 20 30 40 50

std::pair<std::set<int>::const_iterator,std::set<int>::const_iterator> ret;

ret = myset.equal_range(30);

std::cout << "the lower bound points to: " << *ret.first << '\n';

std::cout << "the upper bound points to: " << *ret.second << '\n';

return 0;

}

🌈关于multiset

multiset是按照特定顺序存储元素的容器，其中元素是可以重复的。在multiset中，元素的value也会识别它(因为multiset中本身存储的就是<value, value>组成的键值对，因此value本身就是key，key就是value，类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的)，但可以从容器中插入或删除。在内部，multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭代器遍历时会得到一个有序序列。multiset底层结构为二叉搜索树(红黑树)。

总的来说，<code>multiset与set的区别是，multiset中的元素可以重复，set中value是唯一的。同时，成员函数count()和equal_range()在mutiset中也更有其意义。

这里就不再赘述关于multiset的使用了。

🌈结语

本篇博客我们介绍了STL库中set和multiset，以及set成员函数接口的使用。multiset支持数据冗余，而set中的值（value）是唯一的。感谢大家支持♥