Set自定义排序与iterator的迷思

Posted on | In |

Set原型

1
2
3
4
5
6
template <class Key,
          class Compare = less <key>,
          class Alloc = alloc>
class set {
...
};

set是用红黑二叉树实现的不可存在重复元素Key的容器，默认采用Compare规则进行排序。可以快速插入和删除元素，插入删除相当于在二叉树上增加删除节点，删除节点不会返回set的iterator。

用一段代码来实现set的自定义排序，以及删除一个节点后，iterator的效果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <set>
using namespace std;

struct cmpSymbol{
	bool operator () (const int& a, const int& b){
		return a>b;
	}
};

set<int, cmpSymbol> S;

int main(){

	S.insert(1);
	S.insert(2);
	S.insert(3);
	S.insert(5);

	for(auto s:S){ //使用自动迭代器，这里的s是内容，不是iterator
		cout << s << endl;
	}
	// print 5, 3, 2, 1

	set<int>::iterator it = S.begin();
	set<int>::iterator tmp = S.begin();
	tmp++; //注意tmp = it+1是非法的

	cout << *it << endl;	          //print 5
	cout << *tmp << endl;          //print 3
	
	S.erase(it);
	cout << *S.begin() << endl;    //print 3

	cout << *it << endl;           //print 5
	it++;
	cout << *it << endl;           //print 2

	return 0;
}

结论

  1. iterator是一个泛型指针，但并不是指针。指针是一个存放有另外一个变量的地址的特殊变量，而iterator是一个对象，只是参照了指针的++，–，和修改所指变量内容的特征进行设计的专门用于指向STL容器的对象。
  2. set删除掉一个元素后，指向那个元素的迭代器并没有消失，可以想象成指针指向的空间并没有发生改变，只是二叉树的链接发生了改变。
  3. 但是删掉这个元素后，这个元素迭代器的下一个是什么元素并不确定，并不按照原来的排序进行。