map是一种关联式容器，存储的都是 pair 对象，也就是用 pair 类模板创建的键值对。 包括 C++ 基本数据类型（int、double 等）和使用结构体或类自定义的类型。
map是STL里的一个模板类，用来存放键值对的数据结构，它的定义如下：
template < class Key, //map::key_type
class T, //map::mapped_type
class Compare = less<Key>, //map::key_compare
class Alloc = allocator<pair<const Key, T>> //map::allocator_type
> class map;- 第1个参数存储了key。
- 第2个参数存储了mapped value。
- 第3个参数是比较函数的函数对象。map用它来判断两个key的大小，并返回bool类型的结果。利用这个函数，map可以确定元素在容器中遵循的顺序以及两个元素键是否相等
(!comp(a, b) && !comp(b, a))，确保map中没有两个元素可以具有等效键。这里，它的默认值是less<key>，定义如下：
template <class T>
struct less {
bool operator() (const T& x, const T& y) const {return x < y;}
typedef T first_argument_type;
typedef T second_argument_type;
typedef bool result_type;
};- 第4个参数是用来定义存储分配模型的。
map容器存储的各个键值对，键的值既不能重复也不能被修改。换句话说，map容器中存储的各个键值对不仅键的值独一无二，键的类型也会用 const 修饰，这意味着只要键值对被存储到map容器中，其键的值将不能再做任何修改。- 在使用 map 容器存储多个键值对时，该容器会自动根据各键值对的键的大小，按照既定的规则进行排序。默认情况下，
map容器选用std::less<T>排序规则（其中T表示键的数据类型），其会根据键的大小对所有键值对做升序排序。当然，根据实际情况的需要，我们可以手动指定map容器的排序规则，既可以选用STL标准库中提供的其它排序规则（比如std::greater<T>），也可以自定义排序规则。
| 成员方法 | 功能 |
|---|---|
begin() |
返回指向容器中第一个（注意，是已排好序的第一个）键值对的双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。 |
end() |
返回指向容器最后一个元素（注意，是已排好序的最后一个）所在位置后一个位置的双向迭代器，通常和 begin() 结合使用。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。 |
rbegin() |
返回指向最后一个（注意，是已排好序的最后一个）元素的反向双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。 |
rend() |
返回指向第一个（注意，是已排好序的第一个）元素所在位置前一个位置的反向双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。 |
cbegin() |
和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。 |
cend() |
和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。 |
crbegin() |
和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。 |
crend() |
和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。 |
find(key) |
在 map 容器中查找键为 key 的键值对，如果成功找到，则返回指向该键值对的双向迭代器；反之，则返回和 end() 方法一样的迭代器。另外，如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。 |
lower_bound(key) |
返回一个指向当前 map 容器中第一个大于或等于 key 的键值对的双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。 |
upper_bound(key) |
返回一个指向当前 map 容器中第一个大于 key 的键值对的迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。 |
equal_range(key) |
该方法返回一个 pair 对象（包含 2 个双向迭代器），其中 pair.first 和 lower_bound() 方法的返回值等价，pair.second 和 upper_bound() 方法的返回值等价。也就是说，该方法将返回一个范围，该范围中包含的键为 key 的键值对（map 容器键值对唯一，因此该范围最多包含一个键值对）。 |
empty() |
若容器为空，则返回 true；否则 false。 |
size() |
返回当前 map 容器中存有键值对的个数。 |
max_size() |
返回 map 容器所能容纳键值对的最大个数，不同的操作系统，其返回值亦不相同。 |
operator[] |
map容器重载了 [] 运算符，只要知道 map 容器中某个键值对的键的值，就可以向获取数组中元素那样，通过键直接获取对应的值。 |
at(key) |
找到 map 容器中 key 键对应的值，如果找不到，该函数会引发 out_of_range 异常。 |
insert() |
向 map 容器中插入键值对。 |
erase() |
删除 map 容器指定位置、指定键（key）值或者指定区域内的键值对。 |
swap() |
交换 2 个 map 容器中存储的键值对，这意味着，操作的 2 个键值对的类型必须相同。 |
clear() |
清空 map 容器中所有的键值对，即使 map 容器的 size()为 0。 |
emplace() |
在当前 map 容器中的指定位置处构造新键值对。其效果和插入键值对一样，但效率更高。 |
emplace_hint() |
在本质上和 emplace() 在 map 容器中构造新键值对的方式是一样的，不同之处在于，使用者必须为该方法提供一个指示键值对生成位置的迭代器，并作为该方法的第一个参数。 |
count(key) |
在当前 map 容器中，查找键为 key 的键值对的个数并返回。注意，由于 map容器中各键值对的键的值是唯一的，因此该函数的返回值最大为 1。 |
C++ STL 标准库为 map 容器配备的是双向迭代器（bidirectional iterator）。这意味着，map 容器迭代器只能进行 ++p、p++、--p、p--、*p 操作，并且迭代器之间只能使用 == 或者 != 运算符进行比较。map 类模板中还提供了 find() 成员方法，它能帮我们查找指定 key 值的键值对，如果成功找到，则返回一个指向该键值对的双向迭代器；反之，其功能和 end() 方法相同。
同时，map 类模板中还提供有 lower_bound(key) 和 upper_bound(key) 成员方法，它们的功能是类似的，唯一的区别在于：
lower_bound(key)返回的是指向第一个键不小于key的键值对的迭代器；upper_bound(key)返回的是指向第一个键大于key的键值对的迭代器；
lower_bound(key) 和 upper_bound(key) 更多用于 multimap 容器，在 map 容器中很少用到。
equal_range(key) 成员方法可以看做是 lower_bound(key) 和 upper_bound(key) 的结合体，该方法会返回一个 pair 对象，其中的 2 个元素都是迭代器类型，其中 pair.first 实际上就是 lower_bound(key) 的返回值，而 pair.second 则等同于 upper_bound(key) 的返回值。显然，equal_range(key) 成员方法表示的一个范围，位于此范围中的键值对，其键的值都为 key。和 lower_bound(key)一样，该方法也更常用于 multimap 容器，因为 map 容器中各键值对的键的值都是唯一的，因此通过 map 容器调用此方法，其返回的范围内最多也只有 1 个键值对。
set也是一种关联式容器，set容器中只能存储键，是单纯的键的集合，其中键是不能重复的。
- 所有的元素都会被自动排序。
- 不能通过迭代器来改变set的值，因为set的值就是键。从语法上讲 set 容器并没有强制对存储元素的类型做 const 修饰，即 set 容器中存储的元素的值是可以修改的。但是，C++ 标准为了防止用户修改容器中元素的值，对所有可能会实现此操作的行为做了限制，使得在正常情况下，用户是无法做到修改 set 容器中元素的值的。
如果
set中允许修改键值的话，那么首先需要删除该键，然后调节平衡，在插入修改后的键值，再调节平衡，如此一来，严重破坏了set的结构，导致iterator失效，不知道应该指向之前的位置，还是指向改变后的位置。所以STL中将set的迭代器设置成const，不允许修改迭代器的值。
| 成员方法 | 功能 |
|---|---|
begin() |
返回指向容器中第一个（注意，是已排好序的第一个）元素的双向迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。 |
end() |
返回指向容器最后一个元素（注意，是已排好序的最后一个）所在位置后一个位置的双向迭代器，通常和 begin() 结合使用。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。 |
rbegin() |
返回指向最后一个（注意，是已排好序的最后一个）元素的反向双向迭代器。如果 set容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。 |
rend() |
返回指向第一个（注意，是已排好序的第一个）元素所在位置前一个位置的反向双向迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。 |
cbegin() |
和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值。 |
cend() |
和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值。 |
crbegin() |
和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值。 |
crend() |
和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值。 |
find(val) |
在 set 容器中查找值为 val 的元素，如果成功找到，则返回指向该元素的双向迭代器；反之，则返回和 end() 方法一样的迭代器。另外，如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。 |
lower_bound(val) |
返回一个指向当前 set 容器中第一个大于或等于 val 的元素的双向迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。 |
upper_bound(val) |
返回一个指向当前 set 容器中第一个大于 val 的元素的迭代器。如果 set 容器用 const 限定，则该方法返回的是 const类型的双向迭代器。 |
equal_range(val) |
该方法返回一个 pair 对象（包含 2 个双向迭代器），其中 pair.first 和 lower_bound() 方法的返回值等价，pair.second 和 upper_bound() 方法的返回值等价。也就是说，该方法将返回一个范围，该范围中包含的值为 val 的元素（set 容器中各个元素是唯一的，因此该范围最多包含一个元素）。 |
empty() |
若容器为空，则返回 true；否则 false。 |
size() |
返回当前 set 容器中存有元素的个数。 |
max_size() |
返回 set 容器所能容纳元素的最大个数，不同的操作系统，其返回值亦不相同。 |
insert() |
向 set 容器中插入元素。 |
erase() |
删除 set 容器中存储的元素。 |
swap() |
交换 2 个 set 容器中存储的所有元素。这意味着，操作的 2 个 set 容器的类型必须相同。 |
clear() |
清空 set 容器中所有的元素，即令 set 容器的 size() 为 0。 |
emplace() |
在当前 set 容器中的指定位置直接构造新元素。其效果和 insert() 一样，但效率更高。 |
emplace_hint() |
在本质上和 emplace() 在 set 容器中构造新元素的方式是一样的，不同之处在于，使用者必须为该方法提供一个指示新元素生成位置的迭代器，并作为该方法的第一个参数。 |
count(val) |
在当前 set 容器中，查找值为 val 的元素的个数，并返回。注意，由于 set 容器中各元素的值是唯一的，因此该函数的返回值最大为 1。 |
set 容器类模板中未提供 at() 成员函数，也未对 [] 运算符进行重载。因此，要想访问 set 容器中存储的元素，只能借助 set 容器的迭代器。
C++ STL 标准库为 set 容器配置的迭代器类型为也是双向迭代器。因为 iter 迭代器指向的是 set 容器存储的某个元素，而不是键值对，因此通过 *iter 可以直接获取该迭代器指向的元素的值。除此之外，如果只想遍历 set 容器中指定区域内的部分数据，则可以借助 find()、lower_bound() 以及 upper_bound() 实现。通过调用它们，可以获取一个指向指定元素的迭代器。需要特别指出的是，equal_range(val) 函数的返回值是一个 pair 类型数据，其包含 2 个迭代器，表示 set 容器中和指定参数 val 相等的元素所在的区域，但由于 set 容器中存储的元素各不相等，因此该函数返回的这 2 个迭代器所表示的范围中，最多只会包含 1 个元素。
虽然 C++ STL 标准中，set 类模板中包含 lower_bound()、upper_bound()、equal_range() 这 3 个成员函数，但它们更适用于 multiset 容器，几乎不会用于操作 set 容器。
其实在 STL 标准库中，本就包含几个可供关联式容器使用的排序规则，如表表示：
| 排序规则 | 功能 |
|---|---|
| std::less<T> | 底层采用 < 运算符实现升序排序，各关联式容器默认采用的排序规则。 |
| std::greater<T> | 底层采用 > 运算符实现降序排序，同样适用于各个关联式容器。 |
| std::less_equal<T> | 底层采用 <= 运算符实现升序排序，多用于 multimap 和 multiset 容器。 |
| std::greater_equal<T> | 底层采用 >= 运算符实现降序排序，多用于 multimap 和 multiset 容器。 |
使用函数对象自定义排序规则
class cmp {
public:
//重载 () 运算符
bool operator ()(const string &a,const string &b) {
//按照字符串的长度，做升序排序(即存储的字符串从短到长)
return (a.length() < b.length());
}
};
int main() {
//创建 set 容器，并使用自定义的 cmp 排序规则
std::set<string, cmp>myset{"http://c.biancheng.net/stl/",
"http://c.biancheng.net/python/",
"http://c.biancheng.net/java/"};
//输出容器中存储的元素
for (auto iter = myset.begin(); iter != myset.end(); ++iter) {
cout << *iter << endl;
}
return 0;
}在我们插入时，map会先通过比较函数地函数对象来比对key的大小，然后根据比对结果进行有序存储。c++标准库中，map比较函数的函数对象不可避免地会用到‘<’运算，因此一种方法就是直接在自定义类里重载operator<()操作符：
class Person{
public:
string name;
int age;
Person(string n, int a){
name = n;
age = a;
}
bool operator < (const Person &p) const //注意这里的两个const
{
return (age < p.age) || (age == p.age && name.length() < p.name.length()) ;
}
};需要注意的是，在重载operator<(){}时，无论是参数还是整个函数的const都不能少。参照less的定义，less的参数和函数整体都是const，那么被调用的operator<()必然也是同等要求。
还可以以全局函数定义：
bool operator < (const Person &p1, const Person &p2) const //注意这里的两个const
{
return (p1.age < p2.age) ||
(p1.age == p2.age && p1.name.length() < p2.name.length()) ;
}当以成员函数的方式重载 < 运算符时，该成员函数必须声明为 const 类型，且参数也必须为 const 类型，至于参数的传值方式是采用按引用传递还是按值传递，都可以（建议采用按引用传递，效率更高）。
还可以使用友元函数的形式实现：
//类中友元函数的定义
friend bool operator < (const Person &p1, const Person &p2);
//类外部友元函数的具体实现
bool operator < (const Person &p1, const Person &p2) {
return (p1.age < p2.age) ||
(p1.age == p2.age && p1.name.length() < p2.name.length()) ;
}除了直接重载operator<()，我们可以直接自定义比较函数的函数对象。首先简要介绍一下函数对象的概念：在《C++ Primer Plus》里面，函数对象是可以以函数方式与()结合使用的任意对象。这包括函数名、指向函数的指针和重载了“operator()”操作符的类对象。基于此，我们提出3种定义方法。
它是一种通用、多态、类型安全的函数封装，其实例可以对任何可调用目标实体（包括普通函数、Lambda表达式、函数指针、以及其它函数对象等）进行存储、复制和调用操作，方法如下：
#include <iostream>
#include <map>
#include <string>
#include <functional>
using namespace std;
class Person{
public:
string name;
int age;
Person(string n, int a){
name = n;
age = a;
}
};
bool MyCompare(const Person &p1, const Person &p2) {//普通的函数
return (p1.age < p2.age) || (p1.age == p2.age && p1.name.length() < p2.name.length());
}
int main(int argc, char* argv[]){
map<Person, int, function<bool(const Person &, const Person &)>> group(MyCompare); //需要在构造函数中指明
group[Person("Mark", 17)] = 40561;
group[Person("Andrew",18)] = 40562;
for ( auto ii = group.begin() ; ii != group.end() ; ii++ )
cout << ii->first.name
<< " " << ii->first.age
<< " : " << ii->second
<< endl;
return 0;
}我们利用std::function为MyCompare()构建函数实例。初始化时，这个函数实例就会被分配那个指向MyCompare()的指针。因此，在对group进行申明时，需要构造函数指明函数实例。
另外，c++11增加了一个新的关键词decltype，它可以直接获取自定义哈希函数的类型，并把它作为参数传送。因此，group的声明可以如下修改：
map<Person, int, decltype(&MyCompare)> group(MyCompare);利用重载operator()的类，将比较函数打包成可以直接调用的类：
#include <iostream>
#include <map>
#include <string>
using namespace std;
class Person{
public:
string name;
int age;
Person(string n, int a){
name = n;
age = a;
}
};
struct MyCompare{ //Function Object
bool operator()(const Person &p1, const Person &p2) const{
return (p1.age < p2.age) || (p1.age == p2.age && p1.name.length() < p2.name.length());
}
};
int main(int argc, char* argv[]){
map<Person, int, MyCompare> group;
group[Person("Mark", 17)] = 40561;
group[Person("Andrew",18)] = 40562;
for ( auto ii = group.begin() ; ii != group.end() ; ii++ )
cout << ii->first.name
<< " " << ii->first.age
<< " : " << ii->second
<< endl;
return 0;
}
值得注意的是，这时group的声明不再需要将函数对象的引用传入构造器里。因为map会追踪类定义，当需要比较时，它可以动态地构造对象并传递数据。
通过map的定义可知，第三个参数的默认值是less。显而易见，less属于模板类。那么，我们可以对它进行模板定制，如下所示：
#include <iostream>
#include <map>
#include <string>
using namespace std;
class Person{
public:
string name;
int age;
Person(string n, int a){
name = n;
age = a;
}
};
template <> //function-template-specialization
struct less<Person>{
public :
bool operator()(const Person &p1, const Person &p2) const {
return (p1.age < p2.age) || (p1.age == p2.age && p1.name.length() < p2.name.length());
}
};
int main(int argc, char* argv[]){
map<Person, int> group; //无需指定第三个参数啦
group[Person("Mark", 17)] = 40561;
group[Person("Andrew",18)] = 40562;
for ( auto ii = group.begin() ; ii != group.end() ; ii++ )
cout << ii->first.name
<< " " << ii->first.age
<< " : " << ii->second
<< endl;
return 0;
}