map brief introduction

      map yes STL An associated container of , Store data with key value pairs , Its type can be defined by itself , Each keyword is in map in Only once , Keywords cannot be modified , Value can be modified ,map It is mainly used for data one-to-one mapping .map It is internally orderly （ Automatic sorting , Words are sorted alphabetically ）, Look for Time complexity by O(logn).

One 、map The definition of （ Statement ）

The basic structure is map< Key type , Value type >

map<string,int>  my_map1;

map<int,int> my_map2;

Two 、 Basic operation

1. insert data

The first one is ： use insert Function insertion pair data ：
map<int,string> my_map;
my_map.insert(pair<int,string>(1,"first"));
my_map.insert(pair<int,string>(2,"second"));

The second kind ： Array directly assigns values ：
map<int,string> my_map;
my_map[1]="first";
my_map[4]="second";
  Traverse ：
map<int,string>::iterator it;
for(it=my_map.begin();it!=my_map.end();it++)
    cout<<it->first<<it->second<<endl;

For the second method of inserting data , An example is given as follows ：

This is a program for counting the number of letters in a string （ Case sensitive ） ：

#include <iostream>
#include <map>
#include <cstring>

using namespace std;

int main()
{

    char str[100] = { 0 };

    cin.getline(str, sizeof(str));

    map<char,int> maps;

    for(int i=0;i<strlen(str);i++)
    {
        if(isalpha(str[i]))
            maps[str[i]]++;              
    }

    for(auto it = maps.begin();it!=maps.end();it++)
    {
        cout<<it->first<<":"<<it->second<<endl;
    }
    

    return 0;
}

2. Look for the element

The first one is ： use count( keyword ) Function to determine whether the keyword appears , Its disadvantage is that it cannot locate the location where the element appears .count The return value of the function is either 0, Or 1.

map<string,int> m;
m["first"]=1;
cout<<m.count("first")<<endl;    // Output 1, For keywords “first” There is

The second kind ： use find( keyword ) Function to locate where the element appears , It returns an iterator ( The pointer ), When data appears , What is returned is the iterator where the data is located ; if map No data to find in , The iterator returned is equal to end() Iterator returned by function . 

iterator it->first Represent keyword   it->second Representative value

// find Returns the iterator pointing to the location of the current lookup element. Otherwise, it returns m.end() Location
iter = m.find("123");
if(iter != m.end())  //m.end() return map End address of , In fact, the address is out of bounds .
       cout<<"Find, the value is"<<iter->second<<endl;
else
   cout<<"Cannot Find"<<endl;

3. Delete elements and empty elements

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

4.map Size

int Size = m.size();

3、 ... and .unordered_map

unordered_map The underlying layer of is based on Hashtable Realized , Basic operation and map Agreement . The difference is that unordered_map The interior is disordered .
advantage ：  lookup , Delete It's fast to add , The time complexity is constant 0（c)

The following is an example of using hash table ：

Given an array of integers nums  And an integer target value target, Please find... In the array And is the target value target   the   Two   Integers , And return their array subscripts .

You can assume that each input corresponds to only one answer . however , The same element in the array cannot be repeated in the answer .

You can return the answers in any order .

Example 1：

Input ：nums = [2,7,11,15], target = 9
Output ：[0,1]
explain ： because nums[0] + nums[1] == 9 , return [0, 1] .
Example 2：

Input ：nums = [3,2,4], target = 6
Output ：[1,2]
Example 3：

Input ：nums = [3,3], target = 6
Output ：[0,1]

source ： Power button LeetCode1. Sum of two numbers
link ：https://leetcode.cn/problems/two-sum

The code is as follows (C++)：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashtable;
        for (int i = 0; i < nums.size(); ++i) {
            auto it = hashtable.find(target - nums[i]);
            if (it != hashtable.end()) {
                return {it->second, i};
            }
            hashtable[nums[i]] = i;
        }
        return {};
    }
};

map The traversal

Iterators can be used to traverse ：

    for(auto it = maps.begin();it!=maps.end();it++)
    {
               cout<<it->first<<":"<<it->second<<endl;
    }