第 18.9 節

set / multiset 容器

0瀏覽次數0訪問次數--跳出率--平均停留

set/multiset containers

Set Basic Concepts

A set is a well-defined collection of distinct objects, called the elements or members of the set. Sets are typically denoted by uppercase letters (e.g., A, B, C), and their elements are enclosed in curly braces. For example:

  • A = {1, 2, 3} is a set containing the numbers 1, 2, and 3.
  • B = {"apple", "banana", "cherry"} is a set of strings.

Key properties:

  1. Uniqueness: Each element in a set is unique (no duplicates).
  2. Unordered: The arrangement of elements does not matter (e.g., {1, 2, 3} = {3, 1, 2}).

Common notation:

  • Element of: x ∈ A means "x is an element of set A."
  • Empty set: ∅ or {} represents a set with no elements.
  • Subset: A ⊆ B means "A is a subset of B" (all elements of A are in B).

Sets are fundamental in mathematics and computer science for grouping and organizing data.

Introduction:

  • All elements will be automatically sorted upon insertion.

Essence:

  • Sets and multisets are associative containers, implemented using binary trees as their underlying structure.

Difference between set and multiset:

  • set: Stores unique elements; each value appears only once.
  • multiset: Allows duplicate elements; the same value can appear multiple times.

Example: In a set, inserting "apple", "banana", "apple" results in {"apple", "banana"}. In a multiset, the same insertion yields {"apple", "apple", "banana"}.

  • Sets do not allow duplicate elements in a container.
  • A multiset permits duplicate elements in the container.

Set construction and assignment

Functional Description: Creating a set container and assigning values to it.

Structure:

  • set<T> st; //Default constructor:
  • set(const set &st); //copy constructor

Assignment:

  • set& operator=(const set &st); //overloading the equality operator

Example:

#include <iostream>
#include <set>

using namespace std;

void printSet(set<int> & s)
{
    for (set<int>::iterator it = s.begin(); it != s.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}

//构造和赋值
void test01()
{
    set<int> s1;

    s1.insert(10);
    s1.insert(30);
    s1.insert(20);
    s1.insert(40);
    printSet(s1);

    //拷贝构造
    set<int>s2(s1);
    printSet(s2);

    //赋值
    set<int>s3;
    s3 = s2;
    printSet(s3);
}

int main() {

    test01();


    return 0;
}

运行结果：

10 20 30 40
10 20 30 40
10 20 30 40

Summary:

  • When adding data to a set container, use the insert method.
  • The data inserted into a set container is automatically sorted.

set size and swap

Description:

  • Counting the size of set containers and swapping set containers.

Function prototype:

  • size(); //Returns the number of elements in the container
  • empty(); //Determine whether the container is empty
  • swap(st); //Swap two collection containers

Example:

#include <iostream>
#include <set>

using namespace std;

void printSet(set<int> & s)
{
    for (set<int>::iterator it = s.begin(); it != s.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}

//大小
void test01()
{

    set<int> s1;
    
    s1.insert(10);
    s1.insert(30);
    s1.insert(20);
    s1.insert(40);

    if (s1.empty())
    {
        cout << "s1为空" << endl;
    }
    else
    {
        cout << "s1不为空" << endl;
        cout << "s1的大小为： " << s1.size() << endl;
    }

}

//交换
void test02()
{
    set<int> s1;

    s1.insert(10);
    s1.insert(30);
    s1.insert(20);
    s1.insert(40);

    set<int> s2;

    s2.insert(100);
    s2.insert(300);
    s2.insert(200);
    s2.insert(400);

    cout << "交换前" << endl;
    printSet(s1);
    printSet(s2);
    cout << endl;

    cout << "交换后" << endl;
    s1.swap(s2);
    printSet(s1);
    printSet(s2);
}

int main() {

    //test01();

    test02();


    return 0;
}

运行结果：

交换前
10 20 30 40
100 200 300 400

交换后
100 200 300 400
10 20 30 40

Summary:

  • size
  • Check if empty --- empty
  • Exchange Container --- swap

Insertion and deletion in a set.

Description:

  • Set container for inserting and deleting data

In C++, std::set is an associative container that stores unique elements in a specific order (typically implemented as a balanced binary search tree). Here’s how to perform insertions and deletions:

Insertion

  1. insert: Adds an element if it’s not already present.
    std::set<int> mySet;
mySet.insert(10);          // Inserts 10
mySet.insert(20);          // Inserts 20
mySet.insert(10);          // Duplicate, no effect
  2. emplace: Constructs the element in-place (useful for complex objects).
    mySet.emplace(30);         // Inserts 30
  3. Insert range (from another container):
    std::set<int> anotherSet = {40, 50};
mySet.insert(anotherSet.begin(), anotherSet.end());

Return value: insert returns a pair where:

  • first: iterator to the inserted element (or existing element if duplicate).
  • second: true if insertion took place, false otherwise.

Deletion

  1. erase by key (removes all elements matching the key):
    mySet.erase(10);           // Removes the element with value 10
  2. erase by iterator (removes a specific element):
    auto it = mySet.find(20);
if (it != mySet.end()) {
    mySet.erase(it);       // Removes 20
}
  3. erase range:
    mySet.erase(mySet.begin(), mySet.end()); // Clears the set
  4. clear: Removes all elements.
    mySet.clear();             // Empties the set

Example

#include <iostream>
#include <set>

int main() {
    std::set<int> nums = {1, 2, 3};
    
    nums.insert(4);           // {1, 2, 3, 4}
    nums.erase(2);            // {1, 3, 4}
    
    for (int n : nums) {
        std::cout << n << " ";
    }
    // Output: 1 3 4
    return 0;
}

Complexity

  • Insert/Erase by key: O(log n)
  • Insert/Erase by iterator: Amortized O(1) (but still O(log n) for rebalancing)
  • Search (find): O(log n)

All operations maintain the sorted order of elements. Duplicates are automatically ignored.

Function prototype:

  • insert(elem); //Insert an element into the container.
  • clear(); // Clear all elements
  • erase(pos); //Deletes the element pointed to by the iterator and returns an iterator to the next element.
  • erase(beg, end); //Erases all elements in the range [beg, end), and returns the iterator to the next element.
  • erase(elem); //Delete the element with value elem from the container.

Example:

#include <iostream>
#include <set>

using namespace std;

void printSet(set<int> & s)
{
    for (set<int>::iterator it = s.begin(); it != s.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}

//插入和删除
void test01()
{
    set<int> s1;
    //插入
    s1.insert(10);
    s1.insert(30);
    s1.insert(20);
    s1.insert(40);
    printSet(s1);

    //删除
    s1.erase(s1.begin());
    printSet(s1);

    s1.erase(30);
    printSet(s1);

    //清空
    //s1.erase(s1.begin(), s1.end());
    s1.clear();
    printSet(s1);
}

int main() {

    test01();


    return 0;
}

运行结果：

10 20 30 40
20 30 40
20 40

Summary:

  • insert
  • erase
  • clear

set lookup and statistics

Description:

  • Performing data search and statistics operations on a set container.

Function prototype:

  • find(key); //Check if the key exists; if present, return the iterator to the element with that key; if not, return set.end().
  • count(key); //Count the number of elements in key

Example:

#include <iostream>
#include <set>

using namespace std;

//查找和统计
void test01()
{
    set<int> s1;
    //插入
    s1.insert(10);
    s1.insert(30);
    s1.insert(20);
    s1.insert(40);
    
    //查找
    set<int>::iterator pos = s1.find(30);

    if (pos != s1.end())
    {
        cout << "找到了元素 ： " << *pos << endl;
    }
    else
    {
        cout << "未找到元素" << endl;
    }

    //统计
    int num = s1.count(30);
    cout << "num = " << num << endl;
}

int main() {

    test01();


    return 0;
}

运行结果：

找到了元素 ： 30
num = 1

Summary:

  • 查找 --- find （返回的是迭代器）
  • Count --- count (for set operations, the result is either 0 or 1)

Set and multiset are both associative containers in C++ that store elements in a sorted order, but they differ in how they handle duplicate elements:

  • Set: Each element must be unique. If you try to insert a duplicate, the operation is ignored.
  • Multiset: Allows duplicate elements. You can insert multiple identical values.

Example:

  • std::set<int> mySet → {1, 2, 3} (inserting another 1 has no effect).
  • std::multiset<int> myMultiSet → {1, 1, 2, 3} (all inserts are stored).

Both provide efficient lookup (typically logarithmic time complexity) and maintain elements in sorted order. Use set when uniqueness is required, and multiset when duplicates are allowed.

Learning Objectives:

  • Master the differences between set and multiset.

Difference:

  • Sets do not allow the insertion of duplicate data, whereas multisets do.
  • The SET command does return an insertion result when inserting data, indicating whether the insertion was successful. Specifically, it returns "OK" when the insertion is successful. When using SET with the NX option, if the key already exists, the operation fails and returns nil. Similarly, with the XX option, if the key does not exist, the operation also fails and returns nil.
  • A multiset does not check the data, therefore duplicate data can be inserted.

Example:

#include <iostream>
#include <set>

using namespace std;

//set和multiset区别
void test01()
{
    set<int> s;
    pair<set<int>::iterator, bool>  ret = s.insert(10);
    if (ret.second) {
        cout << "第一次插入成功!" << endl;
    }
    else {
        cout << "第一次插入失败!" << endl;
    }

    ret = s.insert(10);
    if (ret.second) {
        cout << "第二次插入成功!" << endl;
    }
    else {
        cout << "第二次插入失败!" << endl;
    }
    
    //multiset
    multiset<int> ms;
    ms.insert(10);
    ms.insert(10);

    for (multiset<int>::iterator it = ms.begin(); it != ms.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {

    test01();


    return 0;
}

运行结果：

第一次插入成功!
第二次插入失败!
10 10

Summary:

  • If duplicate data insertion is not allowed, you can use a set.
  • If you need to insert duplicate data, you can use a multiset. Unlike a set, a multiset allows duplicate elements and automatically sorts them. Here's how you can use it:

Example Code:

#include <iostream>
#include <set>

int main() {
    std::multiset<int> ms;

    // Insert duplicate elements
    ms.insert(5);
    ms.insert(3);
    ms.insert(5); // Duplicate allowed
    ms.insert(7);
    ms.insert(3); // Another duplicate

    // Display elements
    std::cout << "Elements in multiset: ";
    for (const auto& elem : ms) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // Count occurrences of an element
    std::cout << "Count of 5: " << ms.count(5) << std::endl;

    return 0;
}

Output:

Elements in multiset: 3 3 5 5 7 
Count of 5: 2

Key Features:

  1. Allows Duplicates: Can store multiple identical values.
  2. Automatic Sorting: Elements are sorted in ascending order by default.
  3. Search Operations: Provides efficient find(), count(), and lower_bound()/upper_bound() methods.
  4. Erase Operations: Can erase all instances of a value with erase(value) or a specific iterator.

When to Use:

  • When you need a sorted container that allows duplicates.
  • When you need efficient lookup and iteration over ordered data with duplicates.

Alternatives:

  • Set: If duplicates are not needed.
  • Map: If you need key-value pairs with unique keys.
  • Unordered containers: For faster average-case performance without sorting.

Use multiset when sorted, duplicate-friendly storage is required!

Creating pair groups

Description:

  • When dealing with paired data, tuples can be used to return two data items.

Two creation methods:

  • pair<type, type> p ( value1, value2 );
  • pair<type, type> p = make_pair( value1, value2 );

Example:

#include <iostream>
#include <string>

using namespace std;

//对组创建
void test01()
{
    pair<string, int> p(string("Tom"), 20);
    cout << "姓名： " <<  p.first << " 年龄： " << p.second << endl;

    pair<string, int> p2 = make_pair("Jerry", 10);
    cout << "姓名： " << p2.first << " 年龄： " << p2.second << endl;
}

int main() {

    test01();


    return 0;
}

运行结果：

姓名： Tom 年龄： 20
姓名： Jerry 年龄： 10

Summary:

Both methods can be used to create groups; just keep one in mind.

Sorting a set container

In C++, the std::set container is inherently sorted by its key according to the comparison function used. It maintains elements in ascending order by default, so explicit sorting is not required. If you need to change the sorting order, you can provide a custom comparator at the time of declaration.

Learning Objectives:

  • The default sorting rule for set containers is in ascending order; learn how to change the sorting rule.

主要技术点：

  • By using functors, you can change the sorting rules.

Example 1 set stores built-in data types

#include <iostream>
#include <set>

using namespace std;

class MyCompare 
{
public:
    bool operator()(int v1, int v2) {
        return v1 > v2;
    }
};
void test01() 
{    
    set<int> s1;
    s1.insert(10);
    s1.insert(40);
    s1.insert(20);
    s1.insert(30);
    s1.insert(50);

    //默认从小到大
    for (set<int>::iterator it = s1.begin(); it != s1.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;

    //指定排序规则
    set<int,MyCompare> s2;
    s2.insert(10);
    s2.insert(40);
    s2.insert(20);
    s2.insert(30);
    s2.insert(50);

    for (set<int, MyCompare>::iterator it = s2.begin(); it != s2.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {

    test01();


    return 0;
}

运行结果： 编译失败：比较仿函数的 operator() 缺少 const 限定，现代标准库无法在常量比较器对象上调用它。

In summary: functors can be used to specify the sorting rules for a set container.

Example 2 using a set to store custom data types

#include <iostream>
#include <set>
#include <string>

using namespace std;

class Person
{
public:
    Person(string name, int age)
    {
        this->m_Name = name;
        this->m_Age = age;
    }

    string m_Name;
    int m_Age;

};
class comparePerson
{
public:
    bool operator()(const Person& p1, const Person &p2)
    {
        //按照年龄进行排序  降序
        return p1.m_Age > p2.m_Age;
    }
};

void test01()
{
    set<Person, comparePerson> s;

    Person p1("刘备", 23);
    Person p2("关羽", 27);
    Person p3("张飞", 25);
    Person p4("赵云", 21);

    s.insert(p1);
    s.insert(p2);
    s.insert(p3);
    s.insert(p4);

    for (set<Person, comparePerson>::iterator it = s.begin(); it != s.end(); it++)
    {
        cout << "姓名： " << it->m_Name << " 年龄： " << it->m_Age << endl;
    }
}
int main() {

    test01();


    return 0;
}

运行结果： 编译失败：比较仿函数的 operator() 缺少 const 限定，现代标准库无法在常量比较器对象上调用它。

Summary:

For custom data types, a set must specify a sorting rule before data can be inserted.

音乐页