date: 2020/01/15

set, multiset, map, multimap是关联容器;

pair是类模板,关联容器经常以pair为参数或返回值


pair

http://www.cplusplus.com/reference/utility/pair/

http://c.biancheng.net/view/358.html

pair是类模板,只是一种简单的数据组合

#include <utility>

构造

pair();    // 默认
template<class U, class V> pair(const pair<U,V>& pr);   // 用另一个pair初始化
pair(const first_type& a, const second_type& b);   // 直接用两个数值初始化

访问

两个public的member

// 获取两个值的类型
T1 first_type;
T2 second_type;

// 获取两个值
first_type first;
second_type second;

赋值

通过运算=赋值,STL提供make_pair()函数便捷生成一个pair

std::pair<char, int> pr;
pr = std::make_pair('0', 0);


set&multiset

都是关联容器,内部是有序的,因此不允许直接修改其中的元素;

区别在于set不允许重复元素,multiset允许重复元素

c++11还有内部无序的unordered_set,要注意set内置了pair的哈希函数而unordered_set没有,需要自定义一个哈希函数,如贪心算法 - 874模拟行走机器人 

#include <set> 


示例:


构造

// template<class T, class Compare=less<T>, class Alloc=allocator<T>> class set;

// 默认
explicit set(const key_compare& comp = key_compare(),
             const allocator_type& alloc = allocator_type());
// 用迭代器初始化
set(iterator first, iterator last,
    const key_compare& comp = key_compare(),
    const allocator_type& alloc = allocator_type());
// 用另一个set初始化
set(const set& x);

访问

通过迭代器访问,类似vector

增删查

不允许直接修改其中的元素,只能先删除后插入

// 单次插入,注意multiset是直接返回一个迭代器,而set返回一个pair(来指明是否已有重复元素)
iterator insert (const value_type& val);  // multise
pair<iterator,bool> insert (const value_type& val);   // set
// 批量插入(用迭代器)
void insert (iterator first, iterator last);

// 删除操作与vector类似,但不返回迭代器,而且多一种删除指定数值的形式
void erase (iterator position);
size_type erase (const value_type& val);    // 返回删除掉的元素数量(set必定为0或1)
void erase (iterator first, iterator last);
void clear();

// 查找
iterator find (const value_type& val); // 第一匹配项,如无匹配返回set::end()
iterator lower_bound (const value_type& val);    // 所有匹配项的下边界l
iterator upper_bound (const value_type& val);    // 所有匹配项的上边界u(对set必定为l或l+1)
pair<iterator,iterator> equal_range (const value_type& val);   // 所有匹配项的上下边界


map&multimap

都是关联容器,包含键和值两部分,内部有序(按键排序);

map的键必须唯一,multimap的键可以重复;

c++11还有内部无序的unordered_map

#include <map> 

构造

构造形式与set完全相同

explicit map(const key_compare& comp = key_compare(),
              const allocator_type& alloc = allocator_type());
map(iterator first, iterator last,
    const key_compare& comp = key_compare(),
    const allocator_type& alloc = allocator_type());
map(const map& x);

访问

通过运算符[]或迭代器访问,注意迭代器都是键值对pair;

注意multimap只能通过迭代器访问

// mapped_type& operator[] (const key_type& k);

map<int, char> mp;

mp[0] = '0';
cout << mp[0] << endl;

for(map<int, char>::iterator it = mp.begin(); it != mp.end(); it++){
    cout << mp->first << ", " << mp->second << endl;
}

另外也可以获取键、值的type


[], count和find 

增删查

与set相同