C++STL(5) set container summary

C++ STL(5) set container summary

1. Introduction

std::set in C++ is a container that provides an ordered, non-repeating collection of elements. The following is some introduction to the std::set container:

Ordering: The elements in std::set are sorted in ascending order. By default, the comparison operator of the elements (<) is used for sorting. You can also define how elements are sorted by providing a custom comparison function or comparison object.
Uniqueness: The elements in std::set are unique, that is, duplicate elements are not allowed in the set. When you try to insert a duplicate element, std::set ignores the insertion.
Underlying implementation: std::set is usually implemented using a Red-Black Tree, which is an efficient self-balancing binary search tree. The characteristics of red-black trees make the time complexity of insertion, deletion and search operations all logarithmic time O(logN), where N is the number of elements in the set.
Insertion and deletion operations: You can use the insert() function of std::set to insert elements, and the erase() function to delete elements. Insertion and deletion operations automatically maintain the order and uniqueness of the collection.
Search operation: std::set provides efficient search operation. You can use the find() function to find a specified element and return an iterator pointing to the element. In addition, std::set also provides other search functions, such as lower_bound(), upper_bound() and equal_range(), used to obtain elements that meet specific conditions in an ordered collection.
Iterator support: std::set supports forward iterators and reverse iterators, and you can use iterators to traverse elements in the set.
Other member functions: In addition to the common operations mentioned earlier, std::set also provides some other member functions, such as size() for obtaining the contents of a set The number of elements, empty() is used to check whether the collection is empty, and clear() is used to clear all elements in the collection.

std::set is one of the very useful and commonly used containers in the C++ Standard Template Library (STL). It provides efficient ordered set operations and is widely used in many scenarios, such as deduplication operations, element storage and search, etc.

I hope these introductions can help you understand the std::set container in C++. If you have any further questions, please feel free to ask.

2. Constructors and member functions

When it comes to the constructors and member functions of the std::set library in C++, here are some basic introductions:

Constructor:

Default constructor: set< T > mySet; creates an empty std::set object, where T is the element type.
Range constructor: set< T > mySet(begin, end); Create a std::set object and set the range [begin, end) are copied to the new collection.



Copy constructor: set< T > mySet(otherSet);Creates a new std::set object and copies another std::set code>Elements in the object otherSet.


Move constructor: set< T > mySet(std::move(otherSet)); creates a new std::set object and uses another  The elements in the std::set object otherSet. After the move constructor, otherSet will be empty.

Constructor example:

#include <iostream>
#include <set>

int main() {<!-- -->
    //The default constructor creates an empty set
    std::set<int> mySet;

    // range constructor creates set from array
    int arr[] = {<!-- -->5, 2, 8, 1, 9};
    std::set<int> mySet2(arr, arr + 5);

    //Copy constructor creates set
    std::set<int> mySet3(mySet2);

    return 0;
}


Member functions:


begin() and end(): Return an iterator pointing to the position after the first and last element in std::set.


size() and empty(): size() returns the number of elements in std::set, empty()Checks whether std::set is empty.


insert(val): Insert the value val into std::set. If the value already exists in the collection, the insertion operation will be ignored.



erase(val): Delete the element with value val from std::set.


find(val): Returns an iterator pointing to the element whose value is val. If the element does not exist, returns the end() iterator of std::set.


count(val): Returns the number of elements in the set that are equal to val. Since the elements in std::set are unique, therefore The return value of this function can only be 0 or 1.


lower_bound(val) and upper_bound(val): lower_bound(val) returns a pointer to the first value not less than val >An iterator of elements, upper_bound(val) returns an iterator pointing to the first element greater than val.


clear(): Clear all elements in std::set.


These are some common constructors and member functions of std::set. std::set also provides some other member functions, such as intersection, union and difference operations.
Please note that std::set is one of C++'s standard library containers and therefore can be used in different C++ compilers and environments. For specific usage and syntax, please refer to the relevant documents and information of C++.

Member function example:

#include <iostream>
#include <set>

int main() {<!-- -->
    std::set<int> mySet = {<!-- -->5, 2, 8, 1, 9};

    // Use insert to insert elements
    mySet.insert(4);
    mySet.insert(1); // Duplicate elements will not be inserted

    // Use erase to delete elements
    mySet.erase(8);

    // Use find to find elements
    std::set<int>::iterator it = mySet.find(5);
    if (it != mySet.end()) {<!-- -->
        std::cout << "Element 5 exists in set" << std::endl;
    }

    // Use size to get the number of elements
    std::cout << "Number of elements in set: " << mySet.size() << std::endl;

    // Use an iterator to traverse the set
    for (auto it = mySet.begin(); it != mySet.end(); + + it) {<!-- -->
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // Use clear to clear the set
    mySet.clear();

    // Check if set is empty
    if (mySet.empty()) {<!-- -->
        std::cout << "set is empty" << std::endl;
    }

    return 0;
}

These examples show the use of std::set's constructor and some commonly used member functions. You can use these functions to manipulate and manage the elements in the std::set object according to your specific needs and situations.
3. Conclusion
std::set, as one of the containers in the C++ standard library, has the following advantages and disadvantages:
advantage:


Element uniqueness: The elements in std::set are unique, and each element can only appear once. This makes std::set ideal for situations where unique elements need to be stored.


Automatic sorting: The elements in std::set are automatically sorted according to specific sorting rules. By default, elements are sorted in ascending order, but custom sorting can also be achieved through custom comparison functions.


Fast search: The elements in std::set are implemented based on data structures such as red-black trees, which makes search operations in sets very efficient. The time complexity of the find function is O(logN), where N is the number of elements in the set.


Dynamic expansion: std::set is dynamically expanded and elements can be added or removed dynamically as needed without knowing the size of the set in advance.


shortcoming:


Insertion and deletion are less efficient: Since the elements in std::set need to be kept in order, when inserting and deleting elements, the tree structure may need to be adjusted, which will cause some additional overhead. The average time complexity of insertion and deletion is O(logN).


Does not support random access: Since std::set is implemented through a tree structure, it does not support random access like an array. To access a specific element in a collection, you need to use an iterator for sequential access.


Additional memory overhead: In order to maintain the uniqueness and ordering of elements, std::set requires additional memory to store and manage the tree structure. This can result in relatively high memory overhead, especially when storing a large number of elements.


Not suitable for frequent modifications: Due to the low efficiency of insertion and deletion operations, std::set is not suitable for use when frequent modifications to the collection are required. If the set needs to be modified frequently, you may want to consider other data structures, such as std::unordered_set.


To sum up, std::set has advantages in element uniqueness, automatic sorting and fast search, but there are some limitations in insertion and deletion efficiency, random access and memory overhead. Therefore, when choosing a data structure, these advantages and disadvantages need to be weighed based on specific needs and scenarios.