C&Cpp学习笔记
C++面向对象编程
C++ STL

C++ 标准模板库 STL 关联容器

# C++ 标准模板库 STL 关联容器

容器	数据结构	时间复杂度	顺序性	重复性
set	红黑树	插入、删除、查找 O(log2n)	有序	不可重复
multiset	红黑树	插入、删除、查找 O(log2n)	有序	可重复
map	红黑树	插入、删除、查找 O(log2n)	有序	不可重复
multimap	红黑树	插入、删除、查找 O(log2n)	有序	可重复
unordered_set	哈希表	插入、删除、查找 O(1) 最差 O(n)	无序	不可重复
unordered_multiset	哈希表	插入、删除、查找 O(1) 最差 O(n)	无序	可重复
unordered_map	哈希表	插入、删除、查找 O(1) 最差 O(n)	无序	不可重复
unordered_multimap	哈希表	插入、删除、查找 O(1) 最差 O(n)	无序	可重复

# 关联容器概述

关联容器和顺序容器 (opens new window)的本质的不同在于：关联容器中的元素是按关键字来保存和访问的；与之相对，顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的。关联容器支持高效的关键字查找与访问，其内部元素有序排列，新元素插入的位置取决于它的值，查找速度快。两个主要的关联容器类型是map与set，除了各容器都有的函数外，还支持以下成员函数：

函数	函数描述
find	在容器中搜索具有等于 key 键的元素，如果找到则返回一个迭代器
count	在容器中搜索具有等于 key 键的键的元素，并返回匹配的数量
lower_bound	返回一个非递减序列 `[first, last)`中的第一个大于等于值 val 的位置的迭代器
upper_bound	返回一个非递减序列 `[first, last)`中第一个大于 val 的位置的迭代器
equal_range	获取相同元素的范围，返回包含容器中所有具有与 key 等价的键的元素的范围边界
insert	用以插入一个元素或一个区间

关联容器的基础是名为 pair 的标准库类型，它定义在头文件utility中。pair是一个用来生成特定类型的模板，一个pair保存两个数据成员。当创建一个pair时，需要提供两个类型名，pair的数据成员将具有对应的类型，一个pair类型的对象，其实存储的是一个键值对（key-value）。pair 模板的源码如下所示：

template<class _T1, class _T2>
struct
pair
{
    typedef _T1 first_type ;
    typedef _T2 second_type ;
    // pair 存储的键值对
    _T1 first ;
    _T2 second ;
    // pair 的三种构造函数
    pair(): first(), second() { }
    pair(const _T1& __a, const _T2& __b): first(__a), second(__b) { }
    template<class _U1, class _U2>
    pair(const pair<_U1, _U2>& __p): first(__p.first ), second(__p.second) { }
};

// 第三个构造函数的使用示例
pair<int,int>
p(pair<double,double>(5.5,4.6));
//p.first = 5, p.second = 4

# 集合 set/multiset

set/multiset #include<set> 集合：set 集合中不允许存在相同的元素，multiset 集合中允许存在相同的元素。

# multiset

multiset 类模板定义中有3个模板参数如下：

template <typename Key, typename Pred = less<Key>, typename A = allocator<Key> >
class multiset { …… };

multiset 类模板中3个模板参数的后两个模板参数是可以缺省的，其中第二个模板参数 Pred 类型的变量决定了multiset 中的元素，大小顺序是怎么定义的。multiset 运行过程中，比较两个元素x,y的大小的做法，就是生成一个 Pred 类型的变量，假定为 op，若表达式op(x,y) 返回值为true,则 x比y小。Pred 的缺省类型是 less<Key>，起模板定义如下：

// 第二个模板参数Pred中的模板函数less是使用<运算符比较大小，其模板定义如下
template<class T>
struct less : public binary_function<T, T, bool>{ 
    bool operator()(const T& x, const T& y) { 
        return x < y ; 
    } 
    const; 
};

一种由第二个模板参数缺省导致错误的 multiset 使用错误：

#include <set>
using namespace std;
class A { };
int main() {
    multiset<A> a;
    a.insert(A()); // Error
}

由于参数缺省，multiset<A> a; 就等价于 multiset<A, less<A>> a;；插入元素时，multiset 会将被插入元素和已有元素进行比较。由于 less 模板是用 < 进行比较的；所以，这都要求 A 的对象能用 < 比较，即需要该对象中对 < 运算符进行了重载。

class A {
private:
	int n;
public:
    A(int n_ ) { n = n_; }
    friend bool operator< ( const A & a1, const A & a2 ) { // 重载 < 运算符
        return a1.n < a2.n; 
    }
};

# multiset 成员函数

函数	函数描述
iterator find(const T & val)	在容器中查找值为val的元素，返回其迭代器; 如果找不到，返回end()
iterator insert(const T & val)	将val插入到容器中并返回其迭代器
void insert( iterator first,iterator last)	将区间[first,last)插入容器
int count(const T & val)	统计有多少个元素的值和val相等
iterator lower_bound(const T & val)	查找一个最大的位置 it,使得[begin(),it) 中所有的元素都比 val 小
iterator upper_bound(const T & val)	查找一个最小的位置 it,使得[it,end()) 中所有的元素都比 val 大
pair<iterator,iterator> equal_range(const T & val)	同时求得lower_bound和upper_bound
iterator erase(iterator it)	删除it指向的元素，返回其后面的元素的迭代器

一个 multiset 常用函数使用实例如下：

#include <iostream>
#include <set> //使用multiset须包含此文件
using namespace std;

// 输出[first,last)内的所有元素
template <class T>
void Print(T first, T last){ 
    for(;first != last ; ++first)
        cout << * first << " ";
	cout << endl;
}

class A {
private:
	int n;
public:
    A(int n_ ) { n = n_; }
    friend bool operator< ( const A & a1, const A & a2 ) { // 重载 < 运算符
        return a1.n < a2.n; 
    }
    friend ostream & operator<< ( ostream & o, const A & a2 ) { 
        o << a2.n; 
        return o; 
    }
    friend class MyLess;
};

struct MyLess { 
	bool operator()( const A & a1, const A & a2){ 
        return ( a1.n % 10 ) < (a2.n % 10); //按个位数比较大小
    }
};

// 定义两个使用不同大小比较方式的 Multiset
typedef multiset<A> MSET1; //MSET1用默认方式的 < 运算符比较大小
typedef multiset<A,MyLess> MSET2; //MSET2用 MyLess::operator()比较大小

int main()
{
    const int SIZE = 6;
    A a[SIZE] = {4,22,19,8,33,40};
    // m1中的元素默认大小比较方式排序
    MSET1 m1; 
    m1.insert(a,a+SIZE);
    m1.insert(22);
    
	// 使用count成员函数获取元素值为22的元素个数
    cout << "1) " << m1.count(22) << endl; 
    //输出m1的所有元素： 4 8 19 22 22 33 40
    cout << "2) "; Print(m1.begin(),m1.end()); 
    
    // 使用find成员函数查找元素值为19的元素
    MSET1::iterator pp = m1.find(19);
    if( pp != m1.end() ) //条件为真说明找到
    	cout << "found" << endl;
   
    // 使用 lower_bound 成员函数返回m1中第一个大于等于22的元素的迭代器
    // upper_bound 成员函数返回m1中最后一个大于等于22的元素的迭代器
    cout << "3) "; cout << *m1.lower_bound(22) << "," << *m1.upper_bound(22)<< endl;
    
    // 使用 erase 成员函数删除区间内的元素
    pp = m1.erase(m1.lower_bound(22),m1.upper_bound(22)); //pp指向被删元素的下一个元素
    cout << "4) "; Print(m1.begin(),m1.end()); // 4 8 19 33 40
    cout << "5) "; cout << * pp << endl; // 33
    
    // m2里的元素按n的个位数从小到大排
    MSET2 m2; 
    m2.insert(a,a+SIZE);
    cout << "6) "; Print(m2.begin(),m2.end()); //输出 6) 40 22 33 4 8 19
    return 0;
}

# set

和 multiset 相似 set 类模板定义中有3个模板参数如下：

template <typename Key, typename Pred = less<Key>, typename A = allocator<Key> >
class set { …… };=

set和multiset的最大区别：set支持去重， multiset不支持，所以他们的成员函数大都相同，但是在使用insert() 成员函数时，如果插入set中的是已存在的元素，则忽略插入。

一个 set 常用函数使用实例如下：

#include <iostream>
#include <set>
using namespace std;
int main() {
    typedef set<int>::iterator IT;
    int a[5] = { 3,4,6,1,2 };
    set<int> st(a,a+5); // st里是 1 2 3 4 6 有序集合
    pair< IT,bool> result;
    result = st.insert(5); // st变成 1 2 3 4 5 6 插入数据时会和已有数据进行比较
    if(result.second) //插入成功则输出被插入元素
    	cout << * result.first << " inserted" << endl; // 输出: 5 inserted
    if( st.insert(5).second ) 
        cout << * result.first << endl;
    else
    	cout << * result.first << " already exists" << endl; //输出 5 already exists
    pair<IT,IT> bounds = st.equal_range(4); // 使用equal_range成员函数同时求得lower_bound和upper_bound
    cout << * bounds.first << "," << * bounds.second ; //输出：4,5
    return 0;
}

# 键值对集合 map/multimap

map/multimap #include <map> 键值对集合：map/multimap里放着的都是pair模版类的对象，且按first从小到大排序。所以，map 和 set 的不同在于前者存放的元素有且仅有两个成员变量 (first,second)，一个名为 first，另一个名为 second ，first 的值用来对整体元素进行从小到大的排序，并可以通过 first 快速检索元素。

# multimap

multimap 类模板定义中有4个模板参数如下：

template <typename Key, typename T, typename Pred = less<Key>, typename A = allocator<Key> >
class multiset { …… };

multimap 类模板中4个模板参数的后两个模板参数是可以缺省的，其中第一个模板参数key代表关键字的类型，第二个模板参数T代表值的类型，第三个模板参数 Pred 类型和set类似，该变量决定了multimap 中的元素大小比较的规则。

multimap 中的元素由<关键字,值>组成，每个元素是一个pair对象，关键字就是 first 成员变量，其类型是Key
multimap 中允许多个元素的关键字相同。元素按照first成员变量从小到大排列，缺省情况下用 less<Key> 定义关键字的小于关系

所有适用于 set 的操作都适用于 map，一个 multimap 使用实例如下：

#include <iostream>
#include <map>
using namespace std;
int main()
{
    typedef multimap<int,double,less<int> > mmid;
    mmid pairs;
    // 使用insert()函数插入键值对
    pairs.insert(pair<int,double>(15,4.2));
    pairs.insert(make_pair(15,3.1));
    pairs.insert(mmid::value_type(15,2.7));
    pairs.insert(mmid::value_type(15,99.3));
    // 使用count()函数求关键字等于某值的元素个数
    cout << pairs.count(15) << endl;
    pairs.insert(mmid::value_type(30,111.11));
    pairs.insert(mmid::value_type(10,22.22));
    pairs.insert(mmid::value_type(25,33.333));
    pairs.insert(mmid::value_type(20,9.3));
    // 使用erase()函数删除关键字为25的元素
    pairs.erase(25)
    for( mmid::const_iterator i = pairs.begin();
        i != pairs.end() ;i ++ )
        cout << "(" << i->first << "," << i->second << ")" << ",";
}

map 插入数据是需要插入一个pair对象，从上例中有三种插入方式：

pair<int,double>()：pair构造函数生成pair对象，需要指定first和second的类型
make_pair()：无需写出类型就可以生成一个pair对象，通过实参自动匹配类型；但是需要注意的是pair<int, float>(1, 1.1);和make_pair(1, 1.1);是不同的，前者指定了second就是float，而后再会将其匹配成double
mmid::value_type()：在定义mmid时会同时定义value_type，typedef pair<const Key, T> value_type;所以也可以使用value_type构造pair对象

# map

和 multimap 一样 map 类模板定义中有4个模板参数如下：

template <typename Key, typename T, typename Pred = less<Key>, typename A = allocator<Key> >
class multiset { 
    …… 
	typedef pair<const Key, T> value_type;
    …… 
};

和 multimap 一样 map 中的元素也是由<关键字,值>组成，每个元素是一个pair对象；但是，和 multimap 的主要区别在于 map 的关键字也就是 first 成员变量各不相同，不存在重复的关键字。同样，在第三个模板参数缺省的情况下，其中的元素使用less<Key> 大小比较方法，按照关键字从小到大排列。

map的[ ]成员函数

因为 map 中的元素关键字都是各不相同的，所以可以使用类似于顺序容器的[]对元素进行检索与修改。若 mymap 为 map 模版类的对象，则可以使用mymap[key]返回对关键字等于key的元素的值（second成员变量）的引用。若没有关键字为key的元素，则会往mymap里插入一个关键字为key的元素，其值用无参构造函数初始化，并返回其值的引用。

一个 map 使用实例如下：

#include <iostream>
#include <map>
using namespace std;

// 重载 << 运算符，用于输出map元素
template <class Key,class Value>
ostream & operator <<( ostream & o, const pair<Key,Value> & p){
    o << "(" << p.first << "," << p.second << ")";
    return o;
}

int main() {
    typedef map<int, double,less<int> > mmid;
    mmid pairs;
    pairs.insert(mmid::value_type(15,2.7));
    cout << pairs.count(15) << endl;
    pairs.insert(mmid::value_type(20,9.3));
    mmid::iterator i; 
    for( i = pairs.begin(); i != pairs.end();i ++ ) 
    	cout << * i << ",";
    cout << endl;
   	// 使用[]成员函数检索map元素，如果没有关键字为40的元素，则插入一个
    int n = pairs[40];
    for( i = pairs.begin(); i != pairs.end();i ++ )
    	cout << * i << ",";
    cout << endl;
    cout << "5) ";
    // 使用[]成员函数修改map元素，把关键字为15的元素值改成6.28
    pairs[15] = 6.28; 
    for( i = pairs.begin(); i != pairs.end();i ++ )
    	cout << * i << ",";
}

上次更新: 2023/11/19, 12:55:48

← C++ 标准模板库 STL 函数对象 C++ 标准模板库 STL 容器适配器→