set

时间：2024-10-14 07:31:52

认识

set底层是红黑树，也就是平衡二叉搜索树，所以set的增删查效率是Ο(logN)；
set不允许修改，因为修改key会破坏容器结构；
set不能插入重复键值，但是set的另外一个版本multiset可以插入重复键值；

set类：

template<class T, class Compare = less<T>, class Alloc = allocator<T>>
class set;

这里的T就是key值，由于是平衡二叉搜索树，所以默认是升序，如果需要降序，可以传仿函数.

使用

set的构造：

  • 无参默认构造

    explicit set(const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());

    set<int> examples;

  • 迭代器区间构造：

    template<class InputIterator>
set(InputIterator first, InputIterator last,  const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());

    vector<int> v({1,2,3,4,5});

set<int> examples(v.begin(),v.end());

  • 初始化列表构造：

    set(initializer_list<value_type> il,  const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());

    set<int> examples({1,2,3,4,5});

  • 拷贝构造：

    set(const set& x);

set的增删查

首先我们需要了解一下pair类

template<class T1, class T2>
struct pair
{
	//函数........
T1 first;
T2 second;
}

构造pair对象方式：

pair<int,int> pr1(1,1);	//直接定义
make_pair(2,2);	 //使用函数模板
pair<int,int>(3,3); //使用匿名对象

void func(const pair<int,int>& tmp);
func({5,5});	//隐式类型转换

Insert

  • 直接插入一个元素

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

    如果插入的值不存在，则返回的pair对象的first是刚插入元素的迭代器，它的second为true;
    如果插入的值存在，则返回的pair对象的first是已近存在元素的迭代器，它的second为false;

    而multiset不同，由于multiset可以重复键值，所以返回值仅是一个刚插入元素位置的迭代器；

    set<int> examples;
pair<set<int>::iterator,bool>   ret = examples.insert(7);

if(ret.second == true)
	{
	cout << "插入成功" << endl;
	cout << *(ret.first) << endl;
	}
else
	cout << "插入失败" << endl;

  • 插入一段区间

    template<class InputIterator>
void insert(InputIterator first, InputIterator last);

    已经存在的key值不会插入；
    而multiset可以插入相同的key；

    set<int> examples;
vector<int> v({1,2,3,4,5});

examples.insert(v.begin(), v.end());

  • 插入一段初始化列表；

    void insert(initializer_list<value_type> il);

    已经存在的key值不会插入；
    而multiset可以插入相同的key；

    set<int> examples;
examples.insert({1,2,3,4,5});

Erase

  • 删除指定位置的key值；

    iterator erase(const_iterator position);

    删除后返回下一个位置迭代器；

    set<int> examples({1,2,3,4,5});
auto it = examples.erase(examples.begin());
cout << *it << endl;	//打印2

  • 删除key值；

    size_t erase(const value_type& val);

    删除指定key值；
    删除成功返回1，否则返回0；

    而multiset返回的是指定的key值元素个数，既把所有指定key值删除；

    set<int> examples({1,2,3,4,5});
size_t ret = examples.erase(3);
if(ret == 0)
	cout << "删除失败" << endl;
else
	cout << "删除成功" << endl;

  • 删除一段迭代器区间

    iterator erase(const_iterator first, const_iterator last);

    删除后返回下一个位置迭代器；

    set<int> examples({1,2,3,4,5});
examples.erase(examples.begin(), examples.end());

Find

  • 查找
    iterator find(const value_type& val);
    找到返回对应迭代器，否则返回end();
    而multiset返回的是指定key值的中序第一个位置的迭代器；
    set<int> examples({1,2,3,4,5});
if(examples.find(5) != examples.end())
	cout << "找到了" << endl;
else
	cout << "没找到" << endl;

Count

  • 计数：
    size_type count(const value_type& val)const;
    返回val的个数；
    set<int> examples({1,2,3,4,5});
cout << examples.count(5) << endl;

set的小函数

  • 下界：

    iterator lower_bound(const value_type& val) const;

    返回等于val元素位置的迭代器，如果没有相等的返回中序中第一个大于val位置的迭代器，如果还没有则返回end();

  • 上界：

    iterator upper_bound(const value_type& val) const;

    返回中序中第一个大于val元素位置的迭代器，否则返回end();

    	set<int> myset({10, 20, 30, 40, 50, 60, 70, 80, 90});
	//删除30-60
	auto itlow = myset.lower_bound(30); //返回 大于等于 30的第一个元素位置的迭代器
	auto itup = myset.upper_bound(60);	//返回 大于 60的第一个元素位置的迭代器


	myset.erase(itlow, itup);	//[itlow,itup)
	
	for (auto e : myset)
	{
		cout << e << " ";
	}
	cout << endl;

set总结

set可以排序并且去重，而multiset只支持排序；

增删查效率高，都是Ο(logN);

set的迭代器是双向迭代器；

相关文章