第 18.10 節

map / multimap 容器

0瀏覽次數0訪問次數--跳出率--平均停留

In robotics, a map is a representation of the environment that a robot uses to understand its surroundings and navigate. It is typically created using data from sensors like LiDAR, cameras, or ultrasonic sensors. Maps can be represented in various ways, such as occupancy grids, which divide the space into cells and mark them as occupied, free, or unknown, or topological maps, which focus on connectivity between key points. A good map is essential for localization, path planning, and obstacle avoidance. In the context of a Robot Operating System, maps are often generated and managed as part of the robot's environmental setup for autonomous operation.

Introduction:

map中所有元素都是pair。
The first element in a pair serves as the key for indexing, while the second element is the actual value.
All elements will automatically sort by their key values.

Essence:

Map and multimap are associative containers implemented using binary tree structures.

Pros:

Based on the key value, you can quickly find the corresponding value.

Difference between map and multimap: Both are associative containers in C++ that store key-value pairs, typically implemented as balanced binary trees (like red-black trees). The primary distinction is that map enforces unique keys, while multimap allows duplicate keys. Consequently, map::operator[] provides direct access to a key's value, whereas in multimap, keys with duplicates must be accessed via iterators (e.g., equal_range or lower_bound).

Map does not allow duplicate key elements in the container.
Multimap allows duplicate key values for elements in the container.

Map construction and assignment.

Description:

Construction and assignment operations on the map container.

Function prototype:

Construction:

map<T1, T2> mp; //map default constructor:
map(const map &mp); //copy constructor

Assignment:

map& operator=(const map &mp); //overloading the equality operator

Example:

#include <iostream>
#include <map>

using namespace std;

void printMap(map<int,int>&m)
{
    for (map<int, int>::iterator it = m.begin(); it != m.end(); it++)
    {
        cout << "key = " << it->first << " value = " << it->second << endl;
    }
    cout << endl;
}

void test01()
{
    map<int,int>m; //默认构造
    m.insert(pair<int, int>(1, 10));
    m.insert(pair<int, int>(2, 20));
    m.insert(pair<int, int>(3, 30));
    printMap(m);

    map<int, int>m2(m); //拷贝构造
    printMap(m2);

    map<int, int>m3;
    m3 = m2; //赋值
    printMap(m3);
}

int main() {

    test01();


    return 0;
}

运行结果：

key = 1 value = 10
key = 2 value = 20
key = 3 value = 30

key = 1 value = 10
key = 2 value = 20
key = 3 value = 30

key = 1 value = 10
key = 2 value = 20
key = 3 value = 30

Summary: All elements in a map appear in pairs, so you need to use pair groups when inserting data.

Map size and exchange

Description:

Counting map container size and swapping map containers.

Function prototype:

size(); //Returns the number of elements in the container
empty(); //Determine whether the container is empty
swap(st); //Swap two collection containers

Example:

#include <iostream>
#include <map>

using namespace std;

void printMap(map<int,int>&m)
{
    for (map<int, int>::iterator it = m.begin(); it != m.end(); it++)
    {
        cout << "key = " << it->first << " value = " << it->second << endl;
    }
    cout << endl;
}

void test01()
{
    map<int, int>m;
    m.insert(pair<int, int>(1, 10));
    m.insert(pair<int, int>(2, 20));
    m.insert(pair<int, int>(3, 30));

    if (m.empty())
    {
        cout << "m为空" << endl;
    }
    else
    {
        cout << "m不为空" << endl;
        cout << "m的大小为： " << m.size() << endl;
    }
}

//交换
void test02()
{
    map<int, int>m;
    m.insert(pair<int, int>(1, 10));
    m.insert(pair<int, int>(2, 20));
    m.insert(pair<int, int>(3, 30));

    map<int, int>m2;
    m2.insert(pair<int, int>(4, 100));
    m2.insert(pair<int, int>(5, 200));
    m2.insert(pair<int, int>(6, 300));

    cout << "交换前" << endl;
    printMap(m);
    printMap(m2);

    cout << "交换后" << endl;
    m.swap(m2);
    printMap(m);
    printMap(m2);
}

int main() {

    test01();

    test02();


    return 0;
}

运行结果：

m不为空
m的大小为： 3
交换前
key = 1 value = 10
key = 2 value = 20
key = 3 value = 30

key = 4 value = 100
key = 5 value = 200
key = 6 value = 300

交换后
key = 4 value = 100
key = 5 value = 200
key = 6 value = 300

key = 1 value = 10
key = 2 value = 20
key = 3 value = 30

Summary:

size
Check if empty --- empty
Exchange Container --- swap

map insertion and deletion

Description:

Insert data and delete data from map container.

Function prototype:

insert(elem); //Insert an element into the container.
clear(); // Clear all elements
erase(pos); //Deletes the element pointed to by the iterator and returns an iterator to the next element.
erase(beg, end); //Erases all elements in the range [beg, end), and returns the iterator to the next element.
erase(key); //Remove the element with value 'key' from the container.

Example:

#include <iostream>
#include <map>

using namespace std;

void printMap(map<int,int>&m)
{
    for (map<int, int>::iterator it = m.begin(); it != m.end(); it++)
    {
        cout << "key = " << it->first << " value = " << it->second << endl;
    }
    cout << endl;
}

void test01()
{
    //插入
    map<int, int> m;
    //第一种插入方式
    m.insert(pair<int, int>(1, 10));
    //第二种插入方式（常用）
    m.insert(make_pair(2, 20));
    //第三种插入方式
    m.insert(map<int, int>::value_type(3, 30));
    //第四种插入方式（常用）
    m[4] = 40; 
    //第五种插入方式（常用，但需要现代C++11）
    m.insert({5, 50});

    printMap(m);

    //删除
    m.erase(m.begin());
    printMap(m);

    m.erase(3);
    printMap(m);

    //清空
    m.erase(m.begin(),m.end());
    m.clear();
    printMap(m);
}

int main() {

    test01();


    return 0;
}

运行结果：

key = 1 value = 10
key = 2 value = 20
key = 3 value = 30
key = 4 value = 40
key = 5 value = 50

key = 2 value = 20
key = 3 value = 30
key = 4 value = 40
key = 5 value = 50

key = 2 value = 20
key = 4 value = 40
key = 5 value = 50

Summary:

There are many ways to insert into a map; remembering one is sufficient.

insert
erase
clear

Map lookup and statistics

Description:

Conduct data searches and statistics on map containers.

Function prototype:

find(key); //Check if the key exists; if present, return the iterator to the element with that key; if not, return set.end().
count(key); //Count the number of elements in key

Example:

#include <iostream>
#include <map>

using namespace std;

//查找和统计
void test01()
{
    map<int, int>m; 
    m.insert(pair<int, int>(1, 10));
    m.insert(pair<int, int>(2, 20));
    m.insert(pair<int, int>(3, 30));

    //查找
    map<int, int>::iterator pos = m.find(3);    //将pos指向3 30这个元素

    if (pos != m.end())   //表示没找到元素
    {
        cout << "找到了元素 key = " << (*pos).first << " value = " << (*pos).second << endl;
    }
    else
    {
        cout << "未找到元素" << endl;
    }

    //统计
    int num = m.count(3);
    cout << "num = " << num << endl;
}

int main() {

    test01();


    return 0;
}

运行结果：

找到了元素 key = 3 value = 30
num = 1

Summary:

查找 --- find （返回的是迭代器）
Count --- count (for map, the result is 0 or 1)

Sorting a map container.

Learning Objectives:

The default sorting rule for a map container sorts elements in ascending order based on the key value; learn how to change the sorting rule.

Key Technical Points:

By using functors, you can change the sorting rules.

Example:

#include <iostream>
#include <map>

using namespace std;

class MyCompare {
public:
    bool operator()(int v1, int v2) const{
        return v1 > v2;
    }
};

void test01() 
{
    //默认从小到大排序
    //利用仿函数实现从大到小排序
    map<int, int, MyCompare> m;

    m.insert(make_pair(1, 10));
    m.insert(make_pair(2, 20));
    m.insert(make_pair(3, 30));
    m.insert(make_pair(4, 40));
    m.insert(make_pair(5, 50));

    for (map<int, int, MyCompare>::iterator it = m.begin(); it != m.end(); it++) {
        cout << "key:" << it->first << " value:" << it->second << endl;
    }
}
int main() {

    test01();


    return 0;
}

运行结果：

key:5 value:50
key:4 value:40
key:3 value:30
key:2 value:20
key:1 value:10

Summary:

Using a functor, the sorting rules for a map container can be specified.
For custom data types, the map must specify the sort ordering, just like the set container.

map / multimap 容器

map/multimap containers

map基本概念

Map construction and assignment.

Map size and exchange

map insertion and deletion

Map lookup and statistics

Sorting a map container.