STL Set and Multiset

Container, STL, Set

Set and Multiset

Sets and Multisets
Internal Structure of Sets and Multisets

包含头文件<set>。
定义：

1
2
3
4
5
6
7
8
9
10
namespace std {
	template <	typename T,
			typename Compare = less<T>,
			typename Allocator = allocator<T> >
			class set;
	template <typename T,
			typename Compare = less<T>,
			typename Allocator = allocator<T> >
			class multiset;
}

排序标准Compare必须满足：1.反镜像。如果op(x,y)为true，那么op(y,x)为false。2.传递性。3.不反射。op(x,x)永远为false。4.必须把<和=区分开。判断相等的条件是a<b为false，且b<a也为false。
关联容器。通常用平衡二叉树实现。自动排序。不可修改键值。不能直接存取元素，只能通过迭代器。

Set和Multiset容器的操作

Create, Copy and Destroy

Operation Effect
set c Default constructor; creates an empty set/multiset without any elements
set c(op) Creates an empty set/multiset that uses op as the sorting criterion
set c(c2) Copy constructor; creates a copy of another set/multiset of the same type (all elements are copied)
set c = c2 Copy constructor; creates a copy of another set/multiset of the same type (all elements are copied)
set c(rv) Move constructor; creates a new set/multiset of the same type, taking the contents of the rvalue rv (since C++11)
set c = rv Move constructor; creates a new set/multiset of the same type, taking the contents of the rvalue rv (since C++11)
set c(beg, end) Creates a set/multiset initialized by the elements of the range [beg,end)
set c(beg, end, op) Creates a set/multiset with the sorting criterion op initialized by the elements of the range [beg,end)
set c(initlist) Creates a set/multiset initialized with the elements of initializer list initlist (since C++11)
set c = initlist Creates a set/multiset initialized with the elements of initializer list initlist (since C++11)
c.~set() Destroys all elements and frees the memory

其中，set可以是：

set Effect
set<Elem> A set that by default sorts with less<> (operator <)
set<Elem, Op> A set that by default sorts with Op
multiset<Elem> A multiset that by default sorts with less<> (operator <)
multiset<Elem, Op> A multiset that by default sorts with Op

Nonmodifying Operations

Operation Effect
c.key_comp() Returns the comparison criterion
c.value_comp() Returns the comparison criterion for values as a whole (same as key_comp() )
c.empty() Returns whether the container is empty (equivalent to size()==0 but might be faster)
c.size() Returns the current number of elements
c.max_size() Returns the maximum number of elements possible
c1 == c2 Returns whether c1 is equal to c2 (calls == for the elements)
c1 != c2 Returns whether c1 is not equal to c2 (equivalent to !(c1==c2) )
c1 < c2 Returns whether c1 is less than c2
c1 > c2 Returns whether c1 is greater than c2 (equivalent to c2<c1)
c1 <= c2 Returns whether c1 is less than or equal to c2 (equivalent to !(c2<c1) )
c1 >= c2 Returns whether c1 is greater than or equal to c2 (equivalent to !(c1<c2) )

比较操作只发生在相同类型之间，不光元素类型，比较标准也需一致。

Special Search Operations

Operation Effect
c.count(val) Returns the number of elements with value val
c.find(val) Returns the position of the first element with value val (or end() if none found)
c.lower_bound(val) Returns the first position, where val would get inserted (the first element >= val)
c.upper_bound(val) Returns the last position, where val would get inserted (the first element > val)
c.equal_range(val) Returns a range with all elements with a value equal to val (i.e., the first and last position, where val would get inserted)

比通用算法要快。

Assignments

Operation Effect
c = c2 Assigns all elements of c2 to c
c = rv Move assigns all elements of the rvalue rv to c (since C++11)
c = initlist Assigns all elements of the initializer list initlist to c (since C++11)
c1.swap(c2) Swaps the data of c1 and c2
swap(c1, c2) Swaps the data of c1 and c2

Iterator Functions

Operation Effect
c.begin() Returns a bidirectional iterator for the first element
c.end() Returns a bidirectional iterator for the position after the last element
c.cbegin() Returns a constant bidirectional iterator for the first element (since C++11)
c.cend() Returns a constant bidirectional iterator for the position after the last element (since C++11)
c.rbegin() Returns a reverse iterator for the first element of a reverse iteration
c.rend() Returns a reverse iterator for the position after the last element of a reverse iteration
c.crbegin() Returns a constant reverse iterator for the first element of a reverse iteration (since C++11)
c.crend() Returns a constant reverse iterator for the position after the last element of a reverse iteration (since C++11)

双向迭代器。set的所有元素都是key，都是不可修改的。所以不能用修改性的通用算法在set和multiset上。比如remove。只能使用set或multiset的类成员remove函数。

Inserting and Removing Elements

Operation Effect
c.insert(val) Inserts a copy of val and returns the position of the new element and, for sets, whether it succeeded
c.insert(pos, val) Inserts a copy of val and returns the position of the new element (pos is used as a hint pointing to where the insert should start the search)
c.insert(beg, end) Inserts a copy of all elements of the range [beg,end) (returns nothing)
c.insert(initlist) Inserts a copy of all elements in the initializer list initlist (returns nothing; since C++11)
c.emplace(args…) Inserts a copy of an element initialized with args and returns the position of the new element and, for sets, whether it succeeded (since C++11)
c.emplace_hint(pos, args…) Inserts a copy of an element initialized with args and returns the position of the new element (pos is used as a hint pointing to where the insert should start the search)
c.erase(val) Removes all elements equal to val and returns the number of removed elements
c.erase(pos) Removes the element at iterator position pos and returns the following position (returned nothing before C++11)
c.erase(beg, end) Removes all elements of the range [beg,end) and returns the following position (returned nothing before C++11)
c.clear() Removes all elements (empties the container)

注意Set和Multiset操作insert和emplace的返回值不同：
Set

1
2
3
4
5
6
pair<iterator,bool>		insert (const value_type& val);
iterator			insert (const_iterator posHint, const value_type& val);
template <typename... Args>
pair<iterator, bool>		emplace (Args&&... args);
template <typename... Args>
iterator			emplace_hint (const_iterator posHint, Args&&... args);

MultiSet

1
2
3
4
5
6
iterator		insert (const value_type& val);
iterator		insert (const_iterator posHint, const value_type& val);
template <typename... Args>
iterator		emplace (Args&&... args);
template <typename... Args>
iterator		emplace_hint (const_iterator posHint, Args&&... args);

使用Set和Multiset的示例

Using Set

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
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <set>
#include <algorithm>
#include <iterator>
using namespace std;
int main()
{
	// type of the collection:
	// - no duplicates
	// - elements are integral values
	// - descending order
	set<int, greater<int> > coll1;
	// insert elements in random order using different member functions
	// coll1.insert({4,3,5,1,6,2});
	int temp[6] = {4,3,5,1,6,2};
	coll1.insert(temp, temp+6);
	coll1.insert(5);
	// print all elements
	/*for (int elem : coll1)
	{
		cout <<elem<<' ';
	}*/
	for (set<int, greater<int> >::iterator it = coll1.begin(); it != coll1.end(); ++it)
	{
		cout << *it << ' ';
	}
	cout << endl;
	// insert 4 again and process return value
	auto status = coll1.insert(4);
	if (status.second)
	{
		cout << "4 inserted as element "
			<< distance(coll1.begin(), status.first) + 1 << endl;
	}else
	{
		cout << "4 already existes" << endl;
	}
	// assign elements to another set with ascending order
	set<int> coll2(coll1.cbegin(), coll1.cend());
	// print all elements of the copy using stream iterators
	copy(coll2.cbegin(), coll2.cend(), ostream_iterator<int>(cout, " "));
	cout << endl;
	// remove all elements up to element with value 3
	coll2.erase(coll2.begin(), coll2.find(3));
	// remove all elements with value 5
	int num(coll2.erase(5));
	cout << num << " element(s) removed" << endl;
	// print all elements
	copy(coll2.cbegin(), coll2.cend(), ostream_iterator<int>(cout, " "));
	cout << endl;
	system("Pause");
}

Specifying the Sorting Criterior at Runtime

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <iterator>
#include <algorithm>
#include <set>
using namespace std;
// type for runtime sorting criterion
class RuntimeCmp
{
public:
	enum cmp_mode {normal, reverse};
private:
	cmp_mode mode;
public:
	// constructor for sorting criterion
	// - default criterion uses value normal
	RuntimeCmp (cmp_mode m = normal) : mode(m){}
	// comparison of elements
	// - member function for any element type
	template <typename T>
	bool operator() (const T& t1, const T& t2) const
	{
		return mode == normal ? t1 < t2 : t2 < t1;
	}
	// comparison of sorting criteria
	bool operator== (const RuntimeCmp& rc) const
	{
		return mode == rc.mode;
	}
};
// type of a set that uses this sorting criterion
typedef set<int, RuntimeCmp> IntSet;
int main()
{
	// create, fill, and print set with normal element order
	// - uses default sorting criterion
	int temp[7] = {4,7,5,1,6,2,5};
	IntSet coll1(temp, temp+7);
	cout << "coll1:	";
	copy(coll1.cbegin(), coll1.cend(), ostream_iterator<int>(cout, " "));
	cout << endl;
	// create sorting criterion with reverse element order
	RuntimeCmp reverse_order(RuntimeCmp::reverse);
	// create, fill, and print set with reverse element order
	IntSet coll2(reverse_order);
	coll2.insert(temp, temp+7);
	cout << "coll2:	";
	copy(coll2.cbegin(), coll2.cend(), ostream_iterator<int>(cout, " "));
	cout << endl;
	// assign elements AND sorting criterion
	coll1 = coll2;
	coll1.insert(3);
	cout << "coll1:	";
	copy(coll1.cbegin(), coll1.cend(), ostream_iterator<int>(cout, " "));
	cout << endl;
	// just to make sure...
	if (coll1.value_comp() == coll2.value_comp())
	{
		cout << "coll1 and coll2 have the same sorting criterion" << endl;
	}else
	{
		cout << "coll1 and coll2 have a different sorting criterion" << endl;
	}
	system("Pause");
}

[1] The C++ Standard Library 2nd Edition