C++ map与unordered_map的区别

先决条件：std::map、std::unordered_map
map和unordered_map在效率方面存在巨大差异。我们需要了解两者的内部工作原理才能决定使用哪一个。

主要区别：

                  | map             | unordered_map
---------------------------------------------------------
Ordering        | increasing  order   | no ordering
                | (by default)        |

Implementation  | Self balancing BST  | Hash Table
                | like Red-Black Tree |  

search time     | log(n)              | O(1) -> Average 
                |                     | O(n) -> Worst Case

Insertion time  | log(n) + Rebalance  | Same as search

Deletion time   | log(n) + Rebalance  | Same as search

以下情况优先考虑使用 std::map -

需要有序数据。
必须打印/访问数据(按排序顺序)。
需要元素的前身/后继。


// CPP program to demonstrate use of std::map
#include <bits/stdc++.h>

int main()
{
    // Ordered map
    std::map<int, int> order;

    // Mapping values to keys
    order[5] = 10;
    order[3] = 5;
    order[20] = 100;
    order[1] = 1;

    // Iterating the map and
    // printing ordered values
    for (auto i = order.begin(); i
         != order.end(); i++) {
        std::cout << i->first
                  << " : "
                  << i->second << '
';
    }
}

输出结果：

以下情况优先考虑使用 std::unordered_map -

需要保持一些数据的计数（例如 - 字符串）并且不需要排序。
需要单元素访问，即没有遍历。

// CPP program to demonstrate use of
// std::unordered_map
#include <bits/stdc++.h>

int main()
{
    // Unordered map
    std::unordered_map<int, int> order;

    // Mapping values to keys
    order[5] = 10;
    order[3] = 5;
    order[20] = 100;
    order[1] = 1;

    // Iterating the map and
    // printing unordered values
    for (auto i = order.begin();
         i != order.end(); i++)
    {
        std::cout << i->first
                  << " : "
                  << i->second << '
';
    }
}

输出结果：

欢迎任何形式的转载，但请务必注明出处，尊重他人劳动成果。
转载请注明：文章转载自有区别网 [http://www.vsdiffer.com]
本文标题：C++ map与unordered_map的区别
本文链接：https://www.vsdiffer.com/vs/map-vs-unordered_map-c.html
免责声明：以上内容仅是站长个人看法、理解、学习笔记、总结和研究收藏。不保证其正确性，因使用而带来的风险与本站无关！如本网站内容冒犯了您的权益，请联系站长，邮箱：，我们核实并会尽快处理。

C++ map与unordered_map的区别

相关主题

随机