C++set & multiset – SyntaxBug

Article directory

Preface
1.set introduction
2.Use of set
3.Introduction to multiset
4.Use of multiset

Foreword

Knowledge foundation: associative containers and value-key pair concepts
Link-[C++] Associative container & key-value pair (concept introduction)

1.set introduction

setdocument

translate:

Set is a container that stores elements in a certain order (from small to large)
In the set, the value of the element also identifies it (value is the key, type is T), and each value must be unique. Elements in a set cannot be modified in the container (elements are always const), but they can be inserted or deleted from the container.
Internally, the elements in a set are always ordered according to specific strict weak ordering criteria dictated by their internal comparison object (type comparison).
Set containers are generally slower than unordered_set containers in accessing individual elements by key, but they allow direct iteration of subsets based on order.
Set is implemented using a binary search tree (red-black tree) at the bottom level.

Notice:

Different from map/multimap, map/multimap stores real key-value pairs . Only value is placed in set, but the key-value pair composed of is actually stored at the bottom.

When inserting an element into a set, you only need to insert the value, and there is no need to construct a key-value pair.

The elements in the set cannot be repeated (so the set can be used for deduplication).

Using the iterator of set to traverse the elements in the set, you can get an ordered sequence

By default, elements in a set are compared based on less than

To find an element in set, the time complexity is:

l

o

g

2

n

log_2 n

log2?n

Elements in set are not allowed to be modified (why?)

The bottom layer in the set is implemented using a binary search tree (red-black tree).

Usage of 2.set

(1)set template parameter list

T: The type of element stored in the set. The key-value pair of is actually stored at the bottom layer.

Compare: By default, elements in the set are compared based on less than.

Alloc: The management method of element space in set, which is managed using the space configurator provided by STL.

(2)Set construction, set iterator, set capacity, set modification operation

Omit (you can check the document yourself)

(3)Examples of use of set

Example 1

#include <set>
void TestSet()
{<!-- -->
// Construct a set using the elements in the array
int array[] = {<!-- --> 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4,
6, 8, 0 };
set<int> s(array, array + sizeof(array) / sizeof(array[0]));
cout << s.size() << endl;
//Print the elements in the set in the forward direction. It can be seen from the printing results that the set can remove duplicates.
for (auto & e : s)
cout << e << " ";
cout << endl;
//Use an iterator to reversely print the elements in the set
for (auto it = s.rbegin(); it != s.rend(); + + it)
cout << *it << " ";
cout << endl;
//How many times does the element with value 3 appear in the set?
cout << s.count(3) << endl;
}

Example 2

#include<iostream>
#include<set>
using namespace std;

void test_set1()
{<!-- -->
set<int> s;
s.insert(3);
s.insert(1);
s.insert(4);
s.insert(7);
s.insert(2);
s.insert(1);

// Sorting + Deduplication (searching binary tree - mid-order insertion)
//set<int>::iterator it = s.begin();
auto it = s.begin();
while (it != s.end())
{<!-- -->
cout << *it << " ";
+ + it;
}
cout << endl;

for (auto e : s)
{<!-- -->
cout << e << " ";
}
cout << endl;

// auto pos = s.find(3); // O(logN)
auto pos = find(s.begin(), s.end(), 3); // O(N)
if (pos != s.end())
{<!-- -->
s.erase(pos);
}
cout << s.erase(1) << endl;
cout << s.erase(3) << endl; //Return 0 if deletion fails
for (auto e : s)
{<!-- -->
cout << e << " ";
}
cout << endl;

if (s.count(3)) //If 3 is present, return 1, if not return 0
{<!-- -->
//...
}
}


int main()
{<!-- -->
test_set1();

return 0;
}

3.multiset introduction

multiset documentation

Translation:

A multiset is a container that stores elements in a specific order, where elements can be repeated.
In a multiset, the value of the element will also identify it (because the multiset itself stores key-value pairs composed of , so the value itself is the key, the key is the value, and the type is T). The value of the multiset element cannot Modifications are done within the container (because elements are always const), but can be inserted or removed from the container.
Internally, elements in a multiset are always ordered according to specific strict weak ordering criteria dictated by its internal comparison rules (type comparisons).
Multiset containers are generally slower than unordered_multiset containers when accessing individual elements by key, but when traversed using iterators, an ordered sequence will be obtained.
The underlying structure of multiset is a binary search tree (red-black tree).

Notice:

The key-value pairs of are stored in the bottom layer of multiset.

You only need to insert it into the insertion interface of mtltiset

The difference from set is that the elements in multiset can be repeated, but the value in set is unique.

Use an iterator to traverse the elements in a multiset to get an ordered sequence.

Elements in multiset cannot be modified

To find an element in a multiset, the time complexity is
O

(

l

o

g

2

N

)

O(log_2 N)

O(log2?N)

The role of multiset: you can sort elements

4.Use of multiset

Here we only briefly demonstrate the difference between set and multiset. Other interfaces are the same as set. Students can refer to set.

Example 1

#include <set>
void TestSet()
{<!-- -->
int array[] = {<!-- --> 2, 1, 3, 9, 6, 0, 5, 8, 4, 7 };

// Note: Multiset actually stores the key-value pairs of <int, int> at the bottom layer.
multiset<int> s(array, array + sizeof(array) / sizeof(array[0]));
for (auto & e : s)
cout << e << " ";
cout << endl;
}

Example 2

void test_set2()
{<!-- -->
multiset<int> s;
s.insert(3);
s.insert(1);
s.insert(4);
s.insert(7);
s.insert(2);
s.insert(1);
s.insert(1);
s.insert(3);
s.insert(1);
s.insert(3);
s.insert(2);
s.insert(1);
s.insert(1);


// sort
//multiset<int>::iterator it = s.begin();
auto it = s.begin();
while (it != s.end())
{<!-- -->
cout << *it << " ";
+ + it;
}
cout << endl;

for (auto e : s)
{<!-- -->
cout << e << " ";
}
cout << endl;

auto pos = s.find(3); // O(logN)
while (pos != s.end()) //The 3 found by find is the first 3 in the mid-order, + + still points to the same element in the tree after + +
{<!-- -->
cout << *pos << " ";
+ + pos;
}
cout << endl;

/*if (pos != s.end()) //Test code to delete a certain element
{
s.erase(pos);
}
cout << s.erase(1) << endl;
cout << s.erase(3) << endl;
for (auto e : s)
{
cout << e << " ";
}
cout << endl;

cout << s.count(1) << endl; //count is used to determine the number of the same element in the container
*/
}

int main()
{<!-- -->
test_set2();

return 0;
}

[C++]set & multiset That’s all for today. If you are interested, you can click on the blogger’s column to check out more previous articles. At the same time, the blogger will continue to update more C++ related knowledge in the future, and it is full of useful information. If you think the blogger’s writing is not bad, I hope you friends will not be stingy with the Sanlian in your hands! Your support is the motivation for bloggers to continue creating!