有关vector/map的遍历删除unordered

有关vector/map的遍历删除unordered

小屋杂谈，记录日常

12/16补个坑，最近在刷题的时候用unordered_map之后，发现插入后去遍历顺序会打乱，只知道他底层是哈希表，不是顺序排序，map/set底层红黑树的 会自动排序，但是不知道原来插入后会打乱原来顺序，不仅仅是不排序。也怪自己没有测过，知道问题后，肯定是底层哈希表插入的问题，查了部分资料如下：

unordered_map和unordered_set的背后实现都是hash table，内部存储并不保证顺序，也不排序，也就是说你插入多个元素时的插入顺序和你从begin到end遍历时的顺序未必是一致的，这个顺序性它是不保证的。再加上，在需要的时候比如装载因子达到某一个值的时候，所有元素会重新hash，重新hash后，各个元素的位置都会重新计算，都可能都会发生移动，就更加不保证顺序了。

这玩意是个坑，一切以下面这个代码为准

void del_vec_foreach(vector<int>& vec,int target) {for (vector<int>::iterator it = vec.begin(); it != d();) {if (*it == target) {it = ase(it);}else {++it;}}
}

 vector中erase删除元素用法及注意事项_陈 洪 伟的博客-CSDN博客_erase删除指定元素

下面两个版本的代码都是错的

因为erase之后,迭代器失效,此时的迭代器指向的是删除元素的下一个元素,然后再加上for循环的iter++/或者erase(it++)删除后的本身++,这样就会越过一个元素,导致没有被完全删除干净.

可以举个例子把三组代码测一下就知道了

0,1,2,2,2,2,2,3,4

第一版错误： 

void del_vec_foreach(vector<int>& vec,int target) {for (vector<int>::iterator it = vec.begin(); it != d();it++) {if (*it == target) {it = ase(it);}}
}

第二版错误：

void del_vec_foreach(vector<int>& vec,int target) {for (vector<int>::iterator it = vec.begin(); it != d();) {if (*it == target) {ase(it++);}else {++it;}}
}

 C++STL中，map的erase()在C++11前后不同用法

C++ for循环中vector和map的erase_