注:原创不易,转载请务必注明原作者和出处,感谢支持!

注:内容来自某培训课程,不一定完全正确!

一 set和multiset

set和multiset的特性是所有元素会根据元素的值自动进行排序。set和multiset以红黑树(平衡二叉树的一种)为底层机制。其查找效率非常好。set容器中不允许重复的元素,multiset则允许重复元素存在。

构造函数

set<T> st;				// 默认构造函数
multiset<T> mst; // multiset默认构造函数
set(const set &st); // 拷贝构造函数

赋值操作

set &operator=(const set &st);	// 重载等号运算符
swap(st); // 交换两个集合容器中的元素

大小操作

size();		// 返回容器中元素的数目
empty(); // 判断容器是否为空

插入和删除

insert(elem);		// 在容器中插入元素
clear(); // 清空所有元素
erase(pos); // 删除pos迭代器所指的元素,返回下一个元素的迭代器
erase(beg, end); // 删除区间[beg, end)的所有元素
erase(elem); // 删除容器中值为elem的元素

查找操作

find(key);				// 查找键key是否存在,若存在,返回该元素的迭代器;若不存在,则返回map.end()
lower_bound(keyElem); // 返回第一个key>=keyElem元素的迭代器
upper_bound(keyElem); // 返回第一个key>keyElem元素的迭代器
equal_range(keyElem); // 返回容器中key和keyElem相等的上下限的两个迭代器

下面是set和multiset的应用案例。

void printSet(set<int> &v)
{
decltype(v.begin()) it;
for (it = v.begin(); it != v.end(); ++it)
{
cout << *it << " ";
}
cout << endl;
} void printMultiset(multiset<int> &mst)
{
decltype(mst.begin()) it;
for (it = mst.begin(); it != mst.end(); ++it)
{
cout << *it << " ";
}
cout << endl;
} void Test1()
{
// 初始化
set<int> s1;
s1.insert(7);
s1.insert(2);
s1.insert(4);
s1.insert(5);
s1.insert(1);
printSet(s1); // 赋值
set<int> s2 = s1;
printSet(s2); set<int> s3;
s3.swap(s1);
printSet(s1);
printSet(s3); // 删除
s3.erase(s3.begin());
printSet(s3);
s3.erase(7);
printSet(s3); // multiset
multiset<int> mst;
mst.insert(7);
mst.insert(6);
mst.insert(9);
mst.insert(1);
mst.insert(6);
cout << "mst = " << endl;
decltype(mst.begin()) it;
for (it = mst.begin(); it != mst.end(); ++it)
{
cout << *it << " ";
}
cout << endl; // 查找
set<int> st;
for (int i = 1; i <= 10; ++i)
{
st.insert(i * 10);
}
printSet(st); set<int>::iterator itlow, itup;
// 第一个key >= 30的元素的迭代器
itlow = st.lower_bound(30);
// 第一个key > 60的元素的迭代器
itup = st.upper_bound(60);
cout << "*itlow = " << *itlow << endl;
cout << "*itup = " << *itup << endl;
st.erase(itlow, itup);
printSet(st); // equal_range()
multiset<int> s;
s.insert(10);
s.insert(20);
s.insert(20);
s.insert(20);
s.insert(30);
s.insert(40);
printMultiset(s); pair<decltype(s.begin()), decltype(s.begin())> iteq;
iteq = s.equal_range(20);
cout << "*iteq.first = " << *iteq.first << endl;
cout << "*iteq.second = " << *iteq.second << endl;
s.erase(iteq.first, iteq.second);
printMultiset(s);
}

使用仿函数更改set容器的默认排序方式

在上面的案例中,我们知道set容器默认是对int数据从小到大进行排序的。那么怎样才能让set从大到小排序呢?请看下面的例子。

// 仿函数
class MyCompare
{
public:
bool operator() (int v1, int v2)
{
return v1 > v2;
}
}; // 从大到小排序
void Test2()
{
set<int, MyCompare> s1;
s1.insert(7);
s1.insert(2);
s1.insert(4);
s1.insert(5);
s1.insert(1);
decltype(s1.begin()) it;
for (it = s1.begin(); it != s1.end(); ++it)
{
cout << *it << " ";
}
cout << endl;
}

set容器当中如何放置对象

如果你直接这样写的话是不行的!

class Person
{
public:
Person(int id, int age) : id(id), age(age) {}
public:
int id;
int age;
}; void Test3()
{
// 会报错!因为set内部是需要排序的,当你往set里放置对象时,
// set是不知道如何对对象进行排序的。这与基础数据类型不同
set<Person> sp;
Person p1(1000, 20);
Person p2(1001, 21);
Person p3(1002, 22);
sp.insert(p1);
sp.insert(p2);
sp.insert(p3);
}

那这个问题如何解决?使用仿函数!如下所示。

class cmp
{
public:
bool operator() (const Person &p1, const Person &p2)
{
// 根据ID从小到大排序
return p1.id < p2.id;
}
}; void Test3()
{
// 会报错!因为set内部是需要排序的,当你往set里放置对象时,
// set是不知道如何对对象进行排序的。这与基础数据类型不同
// set<Person> sp; // 正确的写法
set<Person, cmp> sp;
Person p1(1000, 23);
Person p2(1001, 26);
Person p3(1002, 22);
sp.insert(p1);
sp.insert(p2);
sp.insert(p3); decltype(sp.begin()) it;
for (it = sp.begin(); it != sp.end(); ++it)
{
cout << "id = " << it->id << " " << "age = " << it->age << endl;
} // 务必注意:因为仿函数cmp里只对Person的ID进行比较
// 所以在下面的案例中,在sp中查找p4,结果理应是p4不在
// sp中的。但是,因为cmp直对Person的ID进行比较,所以
// 下面案例的实际输出是p4在sp中!,因为p4的ID和p3的ID
// 相同。所以,it返回的实际上是p3的迭代器!!!!!!
Person p4(1002, 29);
it = sp.find(p4);
if (it != sp.end())
{
cout << "p4在sp中!" << endl;
cout << "id = " << it->id << " " << "age = " << it->age << endl;
}
else
{
cout << "p4不在sp中!" << endl;
}
}

务必注意上面案例中的查找的注意事项!

二 对组pair

对组(pair)将一对值组合成一个值,这一对值可以具有不同的数据类型,两个值可以分别用pair的两个公有函数first和second访问。

创建对组

// 方法一
pair<string, int> p1(string("name"), 20);
cout << p1.first << endl;
cout << p1.second << endl; // 方法二
pair<string, int> p2 = make_pair("name", 20);
cout << p2.first << endl;
cout << p2.second << endl; // 对组的赋值
pair<string, int> p3 = p2;
cout << p3.first << endl;
cout << p3.second << endl;
05-21 10:02