std::map是一个排序的关联容器，具有唯一键值特性。其实现底层数据结构为红黑树。在红黑树上的查找、插入、删除操作的算法复杂度为O(logN)。本文将对std::map的有关容器修改的函数进行说明和总结。

1 std::map常见函数

1.1 std::map容器修改操作函数

1.1.1 clear

clear的作用主要是清除std::map中的所有元素。

#include <iostream>
#include <map>
#include <string>

void PrintMap(const std::map<int, std::string>& inMap)
{
    std::map<int, std::string>::const_iterator const_iter = inMap.begin();

    while (const_iter != inMap.end())
    {
        std::cout << const_iter->first << " " << const_iter->second << std::endl;

        const_iter++;
    }
}

int main()
{
    std::cout << "original map:" << std::endl;

    std::map<int, std::string> myMap;
    for (int i = 0; i < 5; ++i)
    {
        myMap[i] = std::to_string(i);
    }
    PrintMap(myMap);


    std::cout << "modifed map:" << std::endl;
    myMap.clear();
    PrintMap(myMap);

    return 0;
}

结果：

original map:
0 0
1 1
2 2
3 3
4 4
modifed map:

1.1.2 insert

insert的作用主要是向std::map容器中插入元素。

如果容器中未包含插入数据对的键值，则将数据对插入容器中；如果容器中已包含插入数据对的键值，则不将数据对插入容器中。具体区别可查看以下代码：

#include <iostream>
#include <map>
#include <string>

void PrintMap(const std::map<int, std::string>& inMap)
{
    std::map<int, std::string>::const_iterator const_iter = inMap.begin();

    while (const_iter != inMap.end())
    {
        std::cout << const_iter->first << " " << const_iter->second << std::endl;

        const_iter++;
    }
}

int main()
{
    std::cout << "original map:" << std::endl;

    std::map<int, std::string> myMap;
    for (int i = 0; i < 5; ++i)
    {
        myMap[i] = std::to_string(i);
    }
    PrintMap(myMap);


    std::cout << "modifed map:" << std::endl;
    myMap.insert({1,"2"});
    PrintMap(myMap);

    std::cout << "modifed map:" << std::endl;
    myMap.insert({ 6,"6" });
    PrintMap(myMap);

    return 0;
}

结果：

original map:
0 0
1 1
2 2
3 3
4 4
modifed map:
0 0
1 1
2 2
3 3
4 4
modifed map:
0 0
1 1
2 2
3 3
4 4
6 6

我们在向容器中插入元素时可以使用以下方式：

  • 初始化列表
  • std::pair
  • std::make_pair
  • 根据迭代器位置插入
  • 其他高级方式，如左值，右值等

通过初始化列表插入

myMap.insert({1,"2"});
myMap.insert({ {1,"a"},{2,"b"} });

通过std::pair插入

myMap.insert(std::pair<int,std::string>(1,"a"));

通过std::make_pair插入

myMap.insert(std::make_pair(1,"a"));

在容器迭代器指定的位置插入

myMap.insert(myMap.begin(), std::make_pair(6,"a"));

1.1.3 insert_or_assign(C++17)

insert_or_assign作用主要是向std::map容器中插入元素，元素是就地构造的，即不执行赋值和移动操作。

insert_or_assign与上述的insert函数不同的是，如果容器中存在于插入数据对相同的键值，则将数据对的值赋值给容器中响应的键值对，覆盖原有键值对中的值；如果容器中不存在插入数据对相同的键值，则插入新的数据对，作用与insert函数一样。

#include <iostream>
#include <map>
#include <string>
#include <iomanip>

void PrintMap(const std::map<int, std::string>& inMap)
{
    std::map<int, std::string>::const_iterator const_iter = inMap.begin();

    while (const_iter != inMap.end())
    {
        std::cout << const_iter->first << " " << const_iter->second << std::endl;

        const_iter++;
    }
}

int main()
{
    std::cout << "original map:" << std::endl;

    std::map<int, std::string> myMap;
    for (int i = 0; i < 5; ++i)
    {
        myMap[i] = std::to_string(i);
    }
    PrintMap(myMap);


    std::cout << "modifed map:" << std::endl;
    myMap.insert_or_assign(1, "a");

    PrintMap(myMap);


    return 0;
}

结果：

original map:
0 0
1 1
2 2
3 3
4 4
modifed map:
0 0
1 a
2 2
3 3
4 4

1.1.4 emplace(C++11)

emplace函数主要作用是如果容器中没有相同键的元素，则将新元素就地构造插入到容器中。

#include <iostream>
#include <map>
#include <string>
#include <iomanip>

void PrintMap(const std::map<int, std::string>& inMap)
{
    std::map<int, std::string>::const_iterator const_iter = inMap.begin();

    while (const_iter != inMap.end())
    {
        std::cout << const_iter->first << " " << const_iter->second << std::endl;

        const_iter++;
    }
}

int main()
{
    std::cout << "original map:" << std::endl;

    std::map<int, std::string> myMap;
    for (int i = 0; i < 5; ++i)
    {
        myMap[i] = std::to_string(i);
    }
    PrintMap(myMap);


    std::cout << "modifed map:" << std::endl;
    myMap.emplace(6, "a");

    PrintMap(myMap);


    return 0;
}

结果：

original map:
0 0
1 1
2 2
3 3
4 4
modifed map:
0 0
1 1
2 2
3 3
4 4
6 a

也可通过以下方式进行插入：

  • std::pair
  • std::make_pair

使用std::pair进行emplace

myMap.emplace(std::pair<int,std::string>(6,"a"));

使用std::make_pair进行emplace

myMap.emplace(std::make_pair(6,"a"));

1.1.5 emplace_hint(C++11)

1.1.6 try_emplace(C++17)

try_emplace函数主要作用是如果容器中没有相同键的元素，则将新元素插入到容器中，其新元素使用给定的args构造。

#include <iostream>
#include <map>
#include <string>
#include <iomanip>

void PrintMap(const std::map<int, std::string>& inMap)
{
    std::map<int, std::string>::const_iterator const_iter = inMap.begin();

    while (const_iter != inMap.end())
    {
        std::cout << const_iter->first << " " << const_iter->second << std::endl;

        const_iter++;
    }
}

int main()
{
    std::cout << "original map:" << std::endl;

    std::map<int, std::string> myMap;
    for (int i = 0; i < 5; ++i)
    {
        myMap[i] = std::to_string(i);
    }
    PrintMap(myMap);


    std::cout << "modifed map:" << std::endl;
    myMap.try_emplace(6,"a");
    PrintMap(myMap);

    std::cout << "modifed map:" << std::endl;
    myMap.try_emplace(6, "b");
    PrintMap(myMap);

    return 0;
}

结果：

original map
0 0
1 1
2 2
3 3
4 4
modifed map:
0 0
1 1
2 2
3 3
4 4
6 a
modifed map:
0 0
1 1
2 2
3 3
4 4
6 a

1.1.7 erase

erase函数的作用主要是从std::map中移除指定的元素。

#include <iostream>
#include <map>
#include <string>
#include <iomanip>

void PrintMap(const std::map<int, std::string>& inMap)
{
    std::map<int, std::string>::const_iterator const_iter = inMap.begin();

    while (const_iter != inMap.end())
    {
        std::cout << const_iter->first << " " << const_iter->second << std::endl;

        const_iter++;
    }
}

int main()
{
    std::cout << "original map:" << std::endl;

    std::map<int, std::string> myMap;
    for (int i = 0; i < 5; ++i)
    {
        myMap[i] = std::to_string(i);
    }
    PrintMap(myMap);


    std::cout << "modifed map:" << std::endl;
    for (auto iter = myMap.begin(); iter != myMap.end();)
    {
        if (iter->first == 2)
        {
            iter = myMap.erase(iter);
        }
        else
        {
            iter++;
        }
    }
    PrintMap(myMap);


    return 0;
}

结果：

original map:
0 0
1 1
2 2
3 3
4 4
modifed map:
0 0
1 1
3 3
4 4

1.1.8 swap

swap函数的作用主要是与其它容器的内容进行对换。

#include <iostream>
#include <string>
#include <utility>
#include <map>

// print out a std::pair
template <class Os, class U, class V>
Os& operator<<(Os& os, const std::pair<U, V>& p) {
    return os << p.first << ":" << p.second;
}

// print out a container
template <class Os, class Co>
Os& operator<<(Os& os, const Co& co) {
    os << "{";
    for (auto const& i : co) { os << ' ' << i; }
    return os << " }\n";
}

int main()
{
    std::map<std::string, std::string>
        m1 { {"γ", "gamma"}, {"β", "beta"}, {"α", "alpha"}, {"γ", "gamma"}, },
        m2 { {"ε", "epsilon"}, {"δ", "delta"}, {"ε", "epsilon"} };

    const auto& ref = *(m1.begin());
    const auto iter = std::next(m1.cbegin());

    std::cout << "──────── before swap ────────\n"
              << "m1: " << m1 << "m2: " << m2 << "ref: " << ref
              << "\niter: " << *iter << '\n';

    m1.swap(m2);

    std::cout << "──────── after swap ────────\n"
              << "m1: " << m1 << "m2: " << m2 << "ref: " << ref
              << "\niter: " << *iter << '\n';

    // Note that every iterator referring to an element in one container before
    // the swap refers to the same element in the other container after the swap.
    // Same is true for references.
}

结果：

──────── before swap ────────
m1: { α:alpha β:beta γ:gamma }
m2: { δ:delta ε:epsilon }
ref: α:alpha
iter: β:beta
──────── after swap ────────
m1: { δ:delta ε:epsilon }
m2: { α:alpha β:beta γ:gamma }
ref: α:alpha
iter: β:beta

1.1.9 extract(C++17)

extract函数的作用主要是将给定位置或者给定键值的元素节点取消在当前容器中的链接，并返回该元素的节点句柄。如果没有给定键值的元素，则返回空的节点句柄。此操作不会复制或者拷贝元素，只是重新调整容器内部的节点指针指向。extract函数只会使得当前提取的元素的迭代器无效，提取元素的指针和引用仍然有效，但在元素由节点句柄拥有时不能使用：如果元素被插入容器，它们将变得可用。

#include <algorithm>
#include <iostream>
#include <map>

int main()
{
    std::map<int, char> cont{{1, 'a'}, {2, 'b'}, {3, 'c'}};

    auto print = [](std::pair<const int, char>& n) { 
        std::cout << " " << n.first << '(' << n.second << ')'; 
    };

    std::cout << "Start:";
    std::for_each(cont.begin(), cont.end(), print);
    std::cout << '\n';

    // Extract node handle and change key
    auto nh = cont.extract(1);
    nh.key() = 4; 

    std::cout << "After extract and before insert:";
    std::for_each(cont.begin(), cont.end(), print);
    std::cout << '\n';

    // Insert node handle back
    cont.insert(move(nh));

    std::cout << "End:";
    std::for_each(cont.begin(), cont.end(), print);
    std::cout << '\n';
}

结果：

Start: 1(a) 2(b) 3(c)
After extract and before insert: 2(b) 3(c)
End: 2(b) 3(c) 4(a)

1.1.10 merge(C++17)

merge函数的作用主要是将输入容器的所有元素重新合并到当前容器中，如果输入容器中有与当前容器键值相同元素，则不进行合并。在这一过程中没有元素拷贝和移动操作，只是要合并的元素从输入容器指向当前容器。

#include <map>
#include <iostream>
#include <string>

int main()
{
  std::map<int, std::string> ma {{1, "apple"}, {5, "pear"}, {10, "banana"}};
  std::map<int, std::string> mb {{2, "zorro"}, {4, "batman"}, {5, "X"}, {8, "alpaca"}};
  std::map<int, std::string> u;
  u.merge(ma);
  std::cout << "ma.size(): " << ma.size() << '\n';
  u.merge(mb);
  std::cout << "mb.size(): " << mb.size() << '\n';
  std::cout << "mb.at(5): " << mb.at(5) << '\n';
  for(auto const &kv: u)
    std::cout << kv.first << ", " << kv.second << '\n';
}

结果：

ma.size(): 0
mb.size(): 1
mb.at(5): X
1, apple
2, zorro
4, batman
5, pear
8, alpaca
10, banana