当前位置：首页 > news >正文

【C++】set

news 2025/8/10 10:42:39

概念

set是一种关联式容器，底层由红黑树组成，set通常用于key搜索场景的结构

声明

set的声明如下，T是底层关键字的类型

set默认要求T支持小于比较，如果输入的类型不支持或者想要根据自己的需求可以自行实现仿函数传给第二个模板参数

set底层储存数据的空间是从空间配置器申请的，有需要可以自己实现内存池，传给第三个参数

通常使用时不需要传后面两个模板参数

set的增删改查效率是O（logN），迭代器遍历走的是搜索树的中序遍历，是有序的

template < class T,                        // set::key_type/value_typeclass Compare = less<T>,        // set::key_compare/value_compareclass Alloc = allocator<T>      // set::allocator_type> class set;

构造和迭代器

无参默认构造

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

迭代器区间构造

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

拷贝构造

set (const set& x);

列表构造

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

迭代器是一个双向迭代器，包含正向和反向两种迭代器

iterator   -> a bidirectional iterator to const value_typeiterator begin();
iterator end();reverse_iterator rbegin();
reverse_iterator rend();

增删查

Member types
key_type   -> The first template parameter (T)
value_type -> The first template parameter (T)// 单个数据插⼊，如果已经存在则插⼊失败
pair<iterator,bool> insert (const value_type& val);// 列表插⼊，已经在容器中存在的值不会插⼊
void insert (initializer_list<value_type> il);// 迭代器区间插⼊，已经在容器中存在的值不会插⼊
template <class InputIterator>void insert (InputIterator first, InputIterator last);// 查找val，返回val所在的迭代器，没有找到返回end() 
iterator find (const value_type& val);// 查找val，返回Val的个数
size_type count (const value_type& val) const;// 删除⼀个迭代器位置的值
iterator  erase (const_iterator position);// 删除val，val不存在返回0，存在返回1 
size_type erase (const value_type& val);// 删除⼀段迭代器区间的值
iterator  erase (const_iterator first, const_iterator last);// 返回⼤于等val位置的迭代器
iterator lower_bound (const value_type& val) const;// 返回⼤于val位置的迭代器
iterator upper_bound (const value_type& val) const;