Some summaries of the set containers in the STL
- 2020-04-02 01:37:15
- OfStack
1. On the set
C++ STL is widely praised and used by many people. It not only provides convenient containers such as vector, string and list, but also encapsulates many complex data structure algorithms and a large number of commonly used data structure operations. Vector encapsulates array, list encapsulates linked list, map and set encapsulates binary tree, etc. When encapsulating these data structures, STL provides common operations in the form of member functions according to the usage habits of programmers, such as: insert, sort, delete, find, etc. Let the user in the use of STL, will not feel strange.
One thing that must be said about sets is that they are set associative containers. Set, as a container, is also used to store data types of the same data type, and can fetch data from a data set. The value of each element in set is unique, and the system can automatically sort according to the value of the element. It should be noted that the value of a number element in a set cannot be changed directly. The standard relational containers set, multiset, map, and multimap in the C++ STL use a very efficient balanced retrieval binary Tree: the red-black Tree, also known as the RB Tree. The RB tree has better statistical performance than the general balanced binary tree, so it is selected as the internal structure of the association container by STL.
There are several questions about set:
(1) why is the insertion and deletion efficiency of map and set higher than that of other sequence containers?
Most people say it's easy because there is no need to copy and move memory for the associated container. Yes, indeed. All the elements in the set container are stored as nodes, which have a similar structure to a linked list, pointing to parent and child nodes. The structure diagram may be as follows:
a.
/ \
B, C
/ \ \
D, E, F, G
So when you insert, you just have to do a little bit of a transformation, and you just point to the new node. Similar to delete, a little bit of transformation to the delete node pointer to other nodes is OK. All we do here is move the pointer back and forth, nothing to do with moving the memory.
(2) why doesn't the previously saved iterator fail after each insert?
Iterator is the equivalent of a pointer to a node, memory is unchanged, how can the pointer to memory be invalidated (of course the deleted element itself is invalidated). Compared to a vector, the pointer is likely to fail with each delete and insert, as is the case with the push_back call to insert at the tail. Because in order to keep the internal data continuous, the block that iterator points to may have been overwritten or freed by other memory during deletion and insertion. Even when push_back, the internal space of the container may not be enough, and a new and larger memory is needed. Only by releasing the previous memory, applying for a new and larger memory, copying the existing data elements to the new memory, and finally putting the elements to be inserted at the end, the previous memory pointer is naturally unavailable. Especially when working with algorithms like find, keep this in mind: don't use out-of-date iterators.
(3) when data elements increase, how does the insertion and search speed of set change?
If you know the log2 relationship you should know the answer completely. Search in set is binary search, that is, if there are 16 elements, it takes up to 4 comparisons to find the result, there are 32 elements, it takes up to 5 comparisons. How about 10,000? The maximum number of comparisons is log 10,000, the maximum number of comparisons is 14. What if it's 20,000 elements? No more than 15. See, when you double the amount of data, you only get one more search, 1/14 more search time. Once you understand this, you can safely put elements in it.
2. Common methods in set
--------------------------------------------------------------------------------
The begin () , returns the first element of the set container
End (), returns the last element of the set container
Clear () , delete all the elements in the set container
Empty (), which determines whether the set container is empty
Max_size (), which returns the maximum number of elements the set container can contain
Size (), which returns the number of elements in the current set container
Rbegin, which returns the same value as end()
Rend (), returns the same value as rbegin()
Write a program to practice these simple operations:
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> s;
s.insert(1);
s.insert(2);
s.insert(3);
s.insert(1);
cout<<"set the size A value of : "<<s.size()<<endl;
cout<<"set the maxsize The value of : "<<s.max_size()<<endl;
cout<<"set The first element in the : "<<*s.begin()<<endl;
cout<<"set And then the last element is :"<<*s.end()<<endl;
s.clear();
if(s.empty())
{
cout<<"set Is empty !!!!!!!!! "<<endl;
}
cout<<"set the size A value of : "<<s.size()<<endl;
cout<<"set the maxsize The value of : "<<s.max_size()<<endl;
return 0;
}
Operation results:
< img Alt = "" border = 0 SRC =" / / files.jb51.net/file_images/article/201309/201309260837054.jpg ">
Summary: After inserting 3, we insert a 1, but we find that the last value in the set is still 3 ha, that's the set. Also note that the begin() and end() functions do not check if the set is empty. It is best to check if the set is empty using empty() before using it.
--------------------------------------------------------------------------------
Count () is used to find the number of occurrences of a certain key value in a set. This function is not very useful in set, because a key value can only appear 0 or 1 times in set, so it becomes to judge whether a key value has appeared in set or not.
Sample code:
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> s;
s.insert(1);
s.insert(2);
s.insert(3);
s.insert(1);
cout<<"set In the 1 The number of times it occurs is : "<<s.count(1)<<endl;
cout<<"set In the 4 The number of times it occurs is : "<<s.count(4)<<endl;
return 0;
}
Operation results:
< img Alt = "" border = 0 SRC =" / / files.jb51.net/file_images/article/201309/201309260837055.jpg ">
Equal_range (), returns a pair of locators representing the first element greater than or equal to the given key value and the first element greater than the given key value, respectively, which is of type pair and is equal to the value of end() if one of these locators fails. What is the specific use of this I have not come across ~~~
Sample code:
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> s;
set<int>::iterator iter;
for(int i = 1 ; i <= 5; ++i)
{
s.insert(i);
}
for(iter = s.begin() ; iter != s.end() ; ++iter)
{
cout<<*iter<<" ";
}
cout<<endl;
pair<set<int>::const_iterator,set<int>::const_iterator> pr;
pr = s.equal_range(3);
cout<<" The first one is greater than or equal to 3 The number is : "<<*pr.first<<endl;
cout<<" The first one is greater than 3 The number is : "<<*pr.second<<endl;
return 0;
}
Operation results:
< img Alt = "" border = 0 SRC =" / / files.jb51.net/file_images/article/201309/201309260837056.jpg ">
Erase (iterator) , deletes the value pointed to by the locator iterator
Erase (first,second), delete the value between the locator first and second
Erase (key_value), deleting the value of the key value key_value
Check out the program:
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> s;
set<int>::const_iterator iter;
set<int>::iterator first;
set<int>::iterator second;
for(int i = 1 ; i <= 10 ; ++i)
{
s.insert(i);
}
//The first deletion
s.erase(s.begin());
//The second deletion
first = s.begin();
second = s.begin();
second++;
second++;
s.erase(first,second);
//Third deletion
s.erase(8);
cout<<" After deleting set The element is : ";
for(iter = s.begin() ; iter != s.end() ; ++iter)
{
cout<<*iter<<" ";
}
cout<<endl;
return 0;
}
Operation results:
< img Alt = "" border = 0 SRC =" / / files.jb51.net/file_images/article/201309/201309260837057.jpg ">
Summary: The delete operation in set is not to do any error checking, such as whether the locator is legal and so on, so you must pay attention when using.
--------------------------------------------------------------------------------
The find () , returns the given value value value locator, or if it is not found, returns end().
Sample code:
#include <iostream>
#include <set>
using namespace std;
int main()
{
int a[] = {1,2,3};
set<int> s(a,a+3);
set<int>::iterator iter;
if((iter = s.find(2)) != s.end())
{
cout<<*iter<<endl;
}
return 0;
}
Insert (key_value); Insert key_value into a set, and the return value is pair < The set < int > : : iterator, bool > , bool indicates whether the insert was successful, while iterator represents the insertion position. If key_value is already in set, then the position of key_value represented by iterator is in set.
An inset (first, second); Insert the element between the locator first and second into the set and the return value is void.
Sample code:
#include <iostream>
#include <set>
using namespace std;
int main()
{
int a[] = {1,2,3};
set<int> s;
set<int>::iterator iter;
s.insert(a,a+3);
for(iter = s.begin() ; iter != s.end() ; ++iter)
{
cout<<*iter<<" ";
}
cout<<endl;
pair<set<int>::iterator,bool> pr;
pr = s.insert(5);
if(pr.second)
{
cout<<*pr.first<<endl;
}
return 0;
}
Operation results:
< img Alt = "" border = 0 SRC =" / / files.jb51.net/file_images/article/201309/201309260837058.jpg ">
Lower_bound (key_value), which returns the first locator greater than or equal to key_value
Upper_bound (key_value), which returns the last locator greater than or equal to key_value
Sample code:
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> s;
s.insert(1);
s.insert(3);
s.insert(4);
cout<<*s.lower_bound(2)<<endl;
cout<<*s.lower_bound(3)<<endl;
cout<<*s.upper_bound(3)<<endl;
return 0;
}
Operation results:
< img Alt = "" border = 0 SRC =" / / files.jb51.net/file_images/article/201309/201309260837059.jpg ">