Summary of the use of hash table set and map when leetcode brushes questions

leetcode When brushing questions, check the hash table set and map Summary of use

In fact, in the process of writing questions , Many times I encounter problems about hash table , Generally, disordered set and map To achieve , Here are some records of these two containers , Facilitate the follow-up questions and better understand

C++ There are many containers , The associated containers include set、map
（ The sequence container includes vector、deque、list、forward_list、array、string, All sequential containers provide fast sequential access to elements .）

There's a fundamental difference between associative containers and sequential containers ： The elements in the associated container are saved and accessed by keywords . In contrast , The elements in a sequential container are saved and accessed sequentially according to their position in the container .

Associated containers do not support operations related to the location of sequential containers . The reason is that the elements in the associated container are stored according to keywords , These operations have no meaning for the associated container . and , Associative containers also do not support constructors or insert operations, which accept an element value and a number of value operations .

The associated container supports efficient keyword search and access . Two main associated containers (associative
container) The type is map and set.map The elements in are keywords ---- value (key–value) Yes ： Keywords play the role of index , The value represents the data associated with the index .set Each element in contains only one keyword ：set Support efficient keyword query operation ---- Check if a given keyword is in set in .

set

Provided by standard library set The associated containers are divided into ：

1, Save elements in order by keyword ：
set( The key word is the value , That is to say, only the container of keywords is saved );
multiset( Keywords are repeatable set);

2, unordered set ：
unordered_set( Organized by hash functions set);
unordered_multiset( Hash organized set, Keywords can be repeated ).

set It's a simple set of keywords . When you just want to know if a value exists ,set Is the most useful .

stay set The value of each element in is unique , And the system can sort elements automatically according to their values .set The values of elements in cannot be changed directly .set Internally, a very efficient balanced search binary tree is used ： Red and black trees , Also known as RB Trees (Red-Black-Tree).RB The statistical performance of the tree is better than that of the general balanced binary tree .

set Two characteristics of ：

set The elements in are sorted
set All elements in are unique , No repeat

set The implementation of the

It is generally created in the following form set Containers

set<type> name;

stay set Some common functions are provided in
1、set Data in can only be passed through insert() Function to insert .

set.insert(v.begin(), v.end());
set.insert(k);

2、 from set Search for using count() Functions and find() function

set.count(k)
*(set.find(k))

3、 from set The function used to delete elements in is erase() function , There are mainly the following forms ：

erase（k);
erase （p);
erase（b, e);
among ,p Represents the element pointed to by the iterator ,b and e They are the beginning and end of the iterator .

4、 set Can only be accessed through iterators

set<typename>::iterator it;

    eg :
set<int>::iterator it;
set<double>::iterator it;
 So you get the iterator  it , And through  *it  To visit  set  Inside the element .

Example ：

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

int main()
{
    
    int myints[] = {
     75,23,65,42,13 };
    set<int> myset(myints, myints + 5);

    cout << "myset contains:";
    for (set<int>::iterator it = myset.begin(); it != myset.end(); ++it)
        cout <<" " << *it;

    cout << '\n';
    myset.insert(200);
    myset.insert(1);
    myset.erase(23);
    set<int>::iterator it = myset.begin();
    cout << *it << endl;
    for (set<int>::iterator it1 = myset.begin(); it1 != myset.end(); it1++)
        cout << *it1 << endl;
 
    return 0;
}

map

map yes STL An associated container of , It provides one-on-one hash.

The first can be called a keyword (key), Each keyword can only be in map Once in ;
The second value may be called the keyword (value);

map The implementation of the

It is generally created in the following form map Containers

map<type, type> name;

stay map Some common functions are provided in
1、map Insert data into .

  Define a map object 
map<int, string> mapStudent;
//  The first one is   use insert Function insert pair
mapStudent.insert(pair<int, string>(000, "student_zero"));
//  The second kind   use insert Function insertion value_type data 
mapStudent.insert(map<int, string>::value_type(001, "student_one"));
//  The third kind of   use "array" Way to insert 
mapStudent[123] = "student_first";
mapStudent[456] = "student_second";

Here's a description , When brushing questions , The third kind is most commonly used , Generally, there can be such an initialization method

for(int num:nums)
map[num]++;

2、 from map Search for , When the key you are looking for key When it appears , It returns the location of the object where the data is located , If not , return iter And end The value of the function is the same .

map.count(k)
Express k Does the key exist , Either for 0 Either for 1, Often used for true and false Judge

// find  Returns the iterator pointing to the location of the current lookup element. Otherwise, it returns map::end() Location 
iter = mapStudent.find("123");
 
if(iter != mapStudent.end())
       cout<<"Find, the value is"<<iter->second<<endl;
else
   cout<<"Do not Find"<<endl;

3、 from map The function used to delete elements in is erase() function , There are generally three kinds

// Iterator deletion 
iter = mapStudent.find("123");
mapStudent.erase(iter);
 
// Delete... With keywords 
int n = mapStudent.erase("123"); // If deleted, it will return 1, Otherwise return 0
 
// Delete with iterator scope  :  The whole map Empty 
mapStudent.erase(mapStudent.begin(), mapStudent.end());
// Equate to mapStudent.clear()

4、map Can be accessed through iterators

    map<string, int> test;
    test.insert(make_pair("test1", 1));   //test["test1"]=1
    test.insert(make_pair("test2", 2));   //test["test2"]=2
    map<string, int>::iterator it = test.find("test0");
    if (it == test.end())
        cout << "test0 not found" << endl;
    else
        cout << it->second << endl;

    cout << test.count("test1") << endl;

    it = test.find("test1");
    if (it == test.end())
        cout << "test1 not found" << endl;
    else
        cout << it->second << endl;

5、map In the iterator of the container first and second

map<string, int> m;
m["one"] = 1;
map<string, int>::iterator p = m.begin();
p->first; //  This is  string  The value is  "one"
p->second; // This is  int  The value is  1

above , It's my personal records , in my opinion , The truth is infinite , Infinite progress ！

I'm a chestnut , I wish you happiness .