专栏首页Visual CodexSTL学习笔记(9)常用容器 set/multiset

STL学习笔记(9)常用容器 set/multiset

set/multiset 容器基本概念

Set 的特性是:所有元素都会根据元素的键值自动被排序。Set 的元素不像 map 那样可以同时拥有实值和键值,set 的元素即是键值又是实值。Set 不允许两个元素有相同的键值。 我们可以通过 set 的迭代器改变 set 元素的值吗?不行,因为 set 元素值就是其键值,关系到 set 元素的排序规则。 如果任意改变 set 元素值,会严重破坏 set 组织。换句话说,set 的 iterator 是一种 const_iterator. set 拥有和 list 某些相同的性质,当对容器中的元素进行插入操作或者删除操作的时候,操作之前所有的迭代器, 在操作完成之后依然有效,被删除的那个元素的迭代器必然是一个例外。

multiset 特性及用法和 set 完全相同,唯一的差别在于它允许键值重复。set 和 multiset 的底层实现是红黑树,红黑 树为平衡二叉树的一种。

树的简单知识:

二叉树就是任何节点最多只允许有两个字节点。分别是左子结点和右子节点。

二叉搜索树,是指二叉树中的节点按照一定的规则进行排序,使得对二叉树中元素访问更加高效。二叉搜索树的 放置规则是:任何节点的元素值一定大于其左子树中的每一个节点的元素值,并且小于其右子树的值。因此从根 节点一直向左走,一直到无路可走,即得到最小值,一直向右走,直至无路可走,可得到最大值。那么在儿茶搜 索树中找到最大元素和最小元素是非常简单的事情。下图为二叉搜索树:

上面我们介绍了二叉搜索树,那么当一个二叉搜索树的左子树和右子树不平衡的时候,那么搜索依据上图表示, 搜索 9 所花费的时间要比搜索 17 所花费的时间要多,由于我们的输入或者经过我们插入或者删除操作,二叉树失 去平衡,造成搜索效率降低。 所以我们有了一个平衡二叉树的概念,所谓的平衡不是指的完全平衡。

set 常用操作

1. set 构造函数
set<T> st;//set 默认构造函数: 
mulitset<T> mst; //multiset 默认构造函数: 
set(const set &st);//拷贝构造函数 
2. set 赋值操作
set& operator=(const set &st);//重载等号操作符
swap(st);//交换两个集合容器 
3. set 大小操作
size();//返回容器中元素的数目 
empty();//判断容器是否为空 
4. set 插入和删除操作
insert(elem);//在容器中插入元素。 
clear();//清除所有元素 
erase(pos);//删除 pos 迭代器所指的元素,返回下一个元素的迭代器。 
erase(beg, end);//删除区间[beg,end)的所有元素 ,返回下一个元素的迭代器。 
erase(elem);//删除容器中值为 elem 的元素。 
5. set 查找操作
find(key);//查找键 key 是否存在,若存在,返回该键的元素的迭代器;若不存在,返回 set.end(); 
count(key);//查找键 key 的元素个数 
lower_bound(keyElem);//返回第一个 key>=keyElem 元素的迭代器。 
upper_bound(keyElem);//返回第一个 key>keyElem 元素的迭代器。 
equal_range(keyElem);//返回容器中 key 与 keyElem 相等的上下限的两个迭代器。

例子

//插入操作返回值
void test01()
{
    set<int> s;
    pair<set<int>::iterator, bool> ret = s.insert(10);
    if (ret.second)
    {
        cout << "插入成功:" << *ret.first << endl;
    }
    else
    {
        cout << "插入失败:" << *ret.first << endl;
    }
    ret = s.insert(10);
    if (ret.second)
    {
        cout << "插入成功:" << *ret.first << endl;
    }
    else
    {
        cout << "插入失败:" << *ret.first << endl;
    }
}
struct MyCompare02
{
    bool operator()(int v1, int v2) { return v1 > v2; }
};

//set 从大到小
void test02()
{
    srand((unsigned int)time(NULL)); //我们发现 set 容器的第二个模板参数可以设置排序规则,默认规则是 less<_Kty>
    set<int, MyCompare02> s;
    for (int i = 0; i < 10; i++)
    {
        s.insert(rand() % 100);
    }
    for (set<int, MyCompare02>::iterator it = s.begin(); it != s.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}

//set 容器中存放对象
class Person
{
public:
    Person(string name, int age)
    {
        this->mName = name;
        this->mAge = age;
    }
public:
    string mName;
    int mAge;
};

struct MyCompare03
{
    bool operator()(const Person &p1, const Person &p2)
    {
        return p1.mAge > p2.mAge;
    }
};

void test03()
{
    set<Person, MyCompare03> s;
    Person p1("aaa", 20);
    Person p2("bbb", 30);
    Person p3("ccc", 40);
    Person p4("ddd", 50);
    s.insert(p1);
    s.insert(p2);
    s.insert(p3);
    s.insert(p4);
    for (set<Person, MyCompare03>::iterator it = s.begin(); it != s.end(); it++)
    {
        cout << "Name:" << it->mName << " Age:" << it->mAge << endl;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C++ STL学习之容器set和multiset (补充材料)

    一、set和multiset基础 set和multiset会根据特定的排序准则,自动将元素进行排序。不同的是后者允许元素重复而前者不允许。 ? 需要包含头文件:...

    Angel_Kitty
  • STL学习笔记(6)常用容器 stack

    stack 是一种先进后出(First In Last Out, FILO)的数据结构,它只有一个出口,形式如图所示。stack 容器允许新增元素, 移除元素,...

    轻舞飞扬SR
  • STL学习笔记(5)常用容器 deque

    Vector 容器是单向开口的连续内存空间,deque 则是一种双向开口的连续线性空间。所谓的双向开口,意思是可以在头尾两端分别做元素的插入和删除操作,当然,v...

    轻舞飞扬SR
  • STL学习笔记(10)常用容器 pair

    对组(pair)将一对值组合成一个值,这一对值可以具有不同的数据类型,两个值可以分别用 pair 的两个公有属性 first 和 second 访问。

    轻舞飞扬SR
  • STL学习笔记(8)常用容器 list

    链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以...

    轻舞飞扬SR
  • STL学习笔记(7)常用容器 queue

    Queue 是一种先进先出(First In First Out,FIFO)的数据结构,它有两个出口,queue 容器允许从一端新增元素,从另 一端移除元素。 ...

    轻舞飞扬SR
  • STL学习笔记(11)常用容器 map/multimap

    Map 的特性是,所有元素都会根据元素的键值自动排序。Map 所有的元素都是 pair,同时拥有实值和键值,pair 的 第一元素被视为键值,第二元素被视为实值...

    轻舞飞扬SR
  • STL学习笔记(4)常用容器 vector

    vector 的数据安排以及操作方式,与 array 非常相似,两者的唯一差别在于空间的运用的灵活性。Array 是静态空间, 一旦配置了就不能改变,要换大一点...

    轻舞飞扬SR
  • STL学习笔记(3)常用容器 string

    C风格字符串(以空字符结尾的字符数组)太过复杂难于掌握,不适合大程序的开发,所以C++标准库定义了一种string 类,定义在头文件。

    轻舞飞扬SR

扫码关注云+社区

领取腾讯云代金券