C++技巧：map和vector

一，map是有序的，unordered_map是无序的

在C++中，std::map 和 std::unordered_map 是两种不同的容器，它们都用于存储键值对，但是它们的底层实现和性能特性有所不同。以下是它们的详细介绍：

std::map

std::map 是一个有序的关联容器，它基于红黑树实现。这意味着元素会根据键自动排序，通常是按照键的升序排列。

特点：

1. 有序性：元素按照键的顺序自动排序。
2. 唯一性：每个键都是唯一的，不允许重复的键。
3. 性能：查找、插入和删除操作的时间复杂度为 O(log n)，其中 n 是容器中元素的数量。
4. 迭代器：支持双向迭代器，可以向前和向后遍历。
5. 键值对：存储的数据是键值对 <key, value> 的形式。

使用场景：

• 当需要有序遍历元素时。
• 当需要根据键的范围进行查询时。

std::unordered_map

std::unordered_map 是一个无序的关联容器，它基于哈希表实现。这意味着元素的存储是无序的，元素的顺序取决于哈希函数和冲突解决策略。

特点：

1. 无序性：元素的存储是无序的。
2. 唯一性：每个键都是唯一的，不允许重复的键。
3. 性能：在理想情况下，查找、插入和删除操作的平均时间复杂度为 O(1)。在最坏情况下，这些操作的时间复杂度为 O(n)，但这种情况很少发生。
4. 迭代器：支持向前迭代器，只能向前遍历。
5. 键值对：存储的数据是键值对 <key, value> 的形式。

使用场景：

• 当不需要有序遍历时。
• 当对查找性能有较高要求时。
• 当元素的哈希函数分布均匀，可以减少哈希冲突时。

性能比较

• 查找性能：std::unordered_map 通常比 std::map 快，因为它的平均时间复杂度为 O(1)。
• 内存使用：std::unordered_map 通常比 std::map 使用更多的内存，因为它需要存储哈希表和可能的链表或红黑树（用于解决哈希冲突）。
• 插入性能：对于 std::unordered_map，插入操作可能需要重新哈希和内存分配，这可能导致性能波动。而 std::map 的插入操作通常更稳定。

总结

选择 std::map 还是 std::unordered_map 取决于具体的应用场景。如果需要有序遍历或者对元素进行范围查询，std::map 是更好的选择。如果需要快速的查找性能，并且不关心元素的顺序，std::unordered_map 则是更合适的选择。

题目 731. 我的日程安排表 II

正确代码：

class MyCalendarTwo {map<int, int> count;
public:MyCalendarTwo() {}bool book(int startTime, int endTime) {count[startTime] ++;count[endTime] --;int cnt = 0;for(auto it: count){cnt += it.second;if(cnt > 2){count[startTime] --;count[endTime] ++;return false;}}return true;}};

错误代码：

class MyCalendarTwo {unordered_map<int, int> count;
public:MyCalendarTwo() {}bool book(int startTime, int endTime) {count[startTime] ++;count[endTime] --;int cnt = 0;for(auto it: count){cnt += it.second;if(cnt > 2){count[startTime] --;count[endTime] ++;return false;}}return true;}};

不要用for(auto it : vector)

这会因为拷贝而影响效率

根据搜索结果，我们可以得出以下结论关于遍历 vector<vector<int>>& trust 的效率：

1. 下标遍历：在某些情况下，下标遍历被认为是最快的方法，因为它直接通过索引访问元素，避免了迭代器的额外开销。在一些测试中，下标遍历比迭代器遍历快了约10倍。

2. 迭代器遍历：使用迭代器遍历 vector 也是常见的方法，但在某些测试中，迭代器遍历比下标遍历慢，尤其是在大量数据的情况下。

3. 范围基的for循环（C++11及以上）：这种遍历方式在某些情况下被认为效率最高，尤其是在优化编译后的环境中。它提供了简洁的语法，并且在某些情况下，性能与下标遍历相当，甚至在某些情况下更快。

4. std::for_each 算法：虽然 std::for_each 提供了一种通用的遍历方式，但在性能测试中，它通常不如下标遍历和迭代器遍历快。

5. auto迭代器：在某些测试中，auto迭代器的性能略低于迭代器，但高于 std::for_each。

综上所述，下标遍历和范围基的for循环在大多数情况下提供了较高的效率。然而，具体哪种方法效率最高可能还取决于具体的编译器优化和数据集的大小。在实际应用中，建议根据具体情况进行性能测试，以确定最适合你需求的遍历方法。

使用C++11的嵌套范围基的for循环

for (auto& row : trust) {for (int val : row) {cout << val << " ";}cout << endl;
}