SoFunction
Updated on 2025-03-02

Detailed explanation of the usage example of C++ set

1. Serial containers and associated containers

Previously, we have contacted some containers in STL such as string, vector, list, deque, array, forward_list, etc. These containers are collectively called sequential containers. Because the logical structure is a linear sequence data structure, there is generally no close correlation between the values ​​stored at the two positions. For example, after exchange, it is still a sequential container. Elements in sequential containers are saved and accessed sequentially in their storage locations in the container.

Associated containers are also used to store data. Unlike sequential containers, the logical structure of the associated container is usually a nonlinear structure, and the two positions have a close correlation. After exchange, their storage structure will be destroyed. Elements in the sequential container are saved and accessed by keywords. The associated containers include map/set series and unordered_map/unordered_set series.

The bottom layer of the map explained in this chapter is a red and black tree, which is a balanced fork search tree. set is the structure of the key search scenario, and map is the structure of the key/value search scenario.

2. Use of set series

2.1 set and multiset reference documentation

/reference/set/

2.2 Introduction to set class

  • The declaration of set is as follows, T is the type of the underlying keyword of set
  • Set defaults to set, support T less than comparison. If it is not supported or you want to follow your own needs, you can implement the functor to pass it to the second template parameter by yourself.
  • Set's memory for storing data from the bottom layer is applied from the space configurator. If necessary, you can implement the memory pool yourself and pass it to the third parameter
  • Generally speaking, we do not need to pass the last two template parameters.
  • The bottom layer of set is implemented using a red tree. The efficiency of adding, deleting and searching is , and iterator traversal is the middle order of the search tree, so it is ordered O(logN)
  • In the previous part, we have learned the use of vector/list and other containers. The STL container interface design is highly similar, so here we will not introduce one interface or one interface, but will directly take you to read the document and select more important interfaces to introduce it.
template < class T, // set::key_type/value_type
            class Compare = less<T>, // set::key_compare/value_compare
            class Alloc = allocator<T> // set::allocator_type
            > class set;

2.3 Set construction and iterator

Let’s focus on the following interfaces for the construction of set.

Set supports forward and reverse iteration traversal, and traversals are in ascending order by default, because the underlying layer is the fork search tree, and iterator traversal in the middle order; supporting iterators means supporting scope for, set iterator and const_iterator do not support iterator modifying data and modifying keyword data, which destroys the structure of the underlying search tree.

// empty (1) Default construct without parametersexplicit set (const key_compare&amp; comp = key_compare(),
const allocator_type&amp; alloc = allocator_type());
// range (2) Iterator interval constructiontemplate &lt;class InputIterator&gt;
set (InputIterator first, InputIterator last,
const key_compare&amp; comp = key_compare(),
const allocator_type&amp; = allocator_type());
// copy (3) copy constructset (const set&amp; x);
// initializer list (5) initializer list constructionset (initializer_list&lt;value_type&gt; il,
const key_compare&amp; comp = key_compare(),
const allocator_type&amp; alloc = allocator_type());
// Iterator is a bidirectional iteratoriterator -&gt; a bidirectional iterator to const value_type
// Forward iteratoriterator begin();
iterator end();
// Reverse iteratorreverse_iterator rbegin();
reverse_iterator rend();

2.4 Set's addition and deletion

Set's add, delete and check the following interfaces:

Member types
key_type -&gt; The first template parameter (T)
value_type -&gt; The first template parameter (T)
// Insert a single data, if it already exists, the insertion failspair&lt;iterator,bool&gt; insert (const value_type&amp; val);
// List insertion, values ​​that already exist in the container will not be insertedvoid insert (initializer_list&lt;value_type&gt; il);
// Iterator interval is inserted, and values ​​that already exist in the container will not be insertedtemplate &lt;class InputIterator&gt;
void insert (InputIterator first, InputIterator last);
// Find val, return the iterator where val is located, and return end() is not founditerator find (const value_type&amp; val);
// Find val and return the number of Valsize_type count (const value_type&amp; val) const;
// Delete the value of the position of an iteratoriterator erase (const_iterator position);
// Delete val, val does not exist and returns 0, and returns 1 if it existssize_type erase (const value_type&amp; val);
// Delete the value of an iterator intervaliterator erase (const_iterator first, const_iterator last);
// Return an iterator greater than or equal val positioniterator lower_bound (const value_type&amp; val) const;
// Returns an iterator greater than the val positioniterator upper_bound (const value_type&amp; val) const;

2.5 Examples of insert and iterator traversal use:

#include&lt;iostream&gt;
#include&lt;set&gt;
using namespace std;
int main()
{
    // Deduplication + ascending order    set&lt;int&gt; s;
    // Deduplication + descending order sort (give a functor greater than)    //set&lt;int, greater&lt;int&gt;&gt; s;
    (5);
    (2);
    (7);
    (5);
    //set&lt;int&gt;::iterator it = ();
    auto it = ();
    while (it != ())
    {
        // error C3892: "it": Cannot assign values ​​to constants        // *it = 1;
        cout &lt;&lt; *it &lt;&lt; " ";
        ++it;
    }
    cout &lt;&lt; endl;
    // Insert an initializer_list list value, the existing value failed to be inserted    ({ 2,8,3,9 });
    for (auto e : s)
    {
        cout &lt;&lt; e &lt;&lt; " ";
    }
    cout &lt;&lt; endl;
    set&lt;string&gt; strset = { "sort", "insert", "add" };
    // traversal string compares ascll code size traversal    for (auto&amp; e : strset)
    {
        cout &lt;&lt; e &lt;&lt; " ";
    }
    cout &lt;&lt; endl;
}

2.6 Examples of use of find and erase:

#include&lt;iostream&gt;
#include&lt;set&gt;
using namespace std;
int main()
{
    set&lt;int&gt; s = { 4,2,7,2,8,5,9 };
    for (auto e : s)
    {
        cout &lt;&lt; e &lt;&lt; " ";
    }
    cout &lt;&lt; endl;
    // Delete the minimum value    (());
    for (auto e : s)
    {
        cout &lt;&lt; e &lt;&lt; " ";
    }
    cout &lt;&lt; endl;
    // Delete x directly    int x;
    cin &gt;&gt; x;
    int num = (x);
    if (num == 0)
    {
        cout &lt;&lt; x &lt;&lt; "Not exists!" &lt;&lt; endl;
    }
    for (auto e : s)
    {
        cout &lt;&lt; e &lt;&lt; " ";
    }
    cout &lt;&lt; endl;
    // Directly search and delete x using iterator    cin &gt;&gt; x;
    auto pos = (x);
    if (pos != ())
    {
        (pos);
    }
    else
    {
        cout &lt;&lt; x &lt;&lt; "Not exists!" &lt;&lt; endl;
    }
    for (auto e : s)
    {
        cout &lt;&lt; e &lt;&lt; " ";
    }
    cout &lt;&lt; endl;
    // Finding of algorithm library O(N)    auto pos1 = find((), (), x);
    // Set's own implementation of search O(logN)    auto pos2 = (x);
    // Use count to indirectly realize quick search    cin &gt;&gt; x;
    if ((x))
    {
        cout &lt;&lt; x &lt;&lt; "exist!" &lt;&lt; endl;
    }
    else
    {
        cout &lt;&lt; x &lt;&lt; "Not exists!" &lt;&lt; endl;
    }
    return 0;
}
#include&lt;iostream&gt;
#include&lt;set&gt;
using namespace std;
int main()
{
    std::set&lt;int&gt; myset;
    for (int i = 1; i &lt; 10; i++)
    (i * 10); // 10 20 30 40 50 60 70 80 90
    for (auto e : myset)
    {
        cout &lt;&lt; e &lt;&lt; " ";
    }
    cout &lt;&lt; endl;
    // The [itlow,itup) found in the implementation contains the [30, 60] interval    // Return >= 30    auto itlow = myset.lower_bound(30);
    // Return > 60    auto itup = myset.upper_bound(60);
    // Delete the value of this interval    (itlow, itup);
    for (auto e : myset)
    {
        cout &lt;&lt; e &lt;&lt; " ";
    }
    cout &lt;&lt; endl;
    return 0;
}

2.7 Differences between multiset and set

The use of multiset and set is basically exactly similar. The main difference is that multiset supports redundancy. Then insert/find/count/erase has differences in support value redundancy. For details, please refer to the following sample code to understand.

#include&lt;iostream&gt;
#include&lt;set&gt;
using namespace std;
int main()
{
    // What's different from set is that multiset is sorting, but does not repetition    multiset&lt;int&gt; s = { 4,2,7,2,4,8,4,5,4,9 };
    auto it = ();
    while (it != ())
    {
        cout &lt;&lt; *it &lt;&lt; " ";
        ++it;
    }
    cout &lt;&lt; endl;
    // Compared to set, there may be multiple x, find to find the first in the order    int x;
    cin &gt;&gt; x;
    auto pos = (x);
    while (pos != () &amp;&amp; *pos == x)
    {
        cout &lt;&lt; *pos &lt;&lt; " ";
        ++pos;
    }
    cout &lt;&lt; endl;
    // What's different from set is that count will return the actual number of x    cout &lt;&lt; (x) &lt;&lt; endl;
    // What's different from set is that when erase gives value, all x will be deleted    (x);
    for (auto e : s)
    {
        cout &lt;&lt; e &lt;&lt; " ";
    }
    cout &lt;&lt; endl;
    return 0;
}

This article introduces the use of associated container sets. Welcome to leave a message to share and communicate.

This is the end of this article about the detailed explanation of the use examples of C++ set. For more related content on using C++ set, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!