关联式容器

关联式容器包括：set、multiset、map、multimap四种。它们的底层使用的数据结构都是红黑树。要学习它们的使用，也可以从：初始化、遍历、查找、插入、删除、针对自定义类型等方面进行学习。

红黑树的五大特征

节点不是红色就是黑色
根节点是黑色
每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
如果一个节点是红色的，则它的子节点必须是黑色的
从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点

类模板声明

cpp

#include <set>
template <
    class Key,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<Key>>
class set;

#include <set>
template <
    class Key,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<Key>>
class multiset;

#include <map>
template <
    class Key,
    class T,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, T>>>
class map;

#include <map>
template <
    class Key,
    class T,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, T>>>
class multimap;

关联式容器的性质

set特征

存放的是key类型，key值是唯一的，不能重复
默认按照key值进行升序排列
底层实现是红黑树

multiset特征

存放的是key类型，key值是不唯一的，可以重复
默认按照key值进行升序排列
底层实现是红黑树

map特征

存放的是key-value类型，key值是唯一的，不能重复，value没有要求是否唯一
默认按照key值进行升序排列
底层实现是红黑树

multimap特征

存放的是key-value类型，key值是不唯一的，可以重复，value没有要求是否唯一
默认按照key值进行升序排列
底层实现是红黑树

容器对象的初始化

关联式容器的初始化方式与序列式容器初始化方式基本完全一致，包括：初始化空对象、使用迭代器范围、使用大括号、拷贝或者移动构造的方式，具体代码形式可以回看序列式容器。

cpp

template <typename Container>
void display(const Container &con) {
    for (auto &elem : con) {
        cout << elem << " ";
    }
    cout << endl;
}
set<int> number = {1, 4, 7, 6, 4, 3, 2, 6, 8, 4, 2};
display(number);
// 注意：上述的set可以直接换成multiset

cpp

template <typename Container>
void display(const Container &con) {
    for (auto &elem : con) {
        cout << elem.first << " " << elem.second << endl;
    }
}
map<int, string> number =
    {
        {1, "北京"}, // 大括号方式进行初始化
        {2, "上海"},
        std::pair<int, string>(3, "广州"), // map中存的是pair类型，就直接使用pair初始化
        std::pair<int, string>(4, "深圳"),
        std::make_pair(5, "武汉"), // std::make_pair()函数返回类型就是pair类型
        std::make_pair(6, "南京"),
        std::make_pair(2, "上海")};
display(number);
// 注意：初始化时，map可以直接换成multimap

遍历容器

关联式容器的遍历方式与序列式容器遍历方式基本完全一致，包括：使用迭代器遍历、使用范围for遍历、使用for_each算法遍历致(可以参考序列式容器)。

cpp

template <typename Container>
void display(const Container &c) {
    for (auto &elem : c) {
        cout << elem << " ";
    }
    cout << endl;
}

容器对象的查找

count()与find()

四种关联式容器都有这两个函数

cpp

// 查找满足条件的key的个数
size_type count( const Key& key ) const;

// 查找满足条件的key的迭代器
iterator find( const Key& key );
const_iterator find( const Key& key ) const;

演示实例

cpp

// number对象可以是四种关联式容器中的任何一种
size_t cnt = number.count(1); // cnt = 1 表示key存在，否则key不存在
set<int>::iterator it = number.find(10);
if (it == number.end()) {
    cout << "该元素不存在number中" << endl;
} else {
    cout << "该元素存在number中： " << *it << endl;
}

另外三个查找函数

四种关联式容器都有这三个函数

cpp

// 返回第一个不小于给定key值的迭代器
iterator lower_bound(const Key &key);
const_iterator lower_bound(const Key &key) const;

// 返回第一个大于给定key值的迭代器
iterator upper_bound(const Key &key);
const_iterator upper_bound(const Key &key) const;

// 返回满足给定key值范围的元素
std::pair<iterator, iterator> equal_range(const Key &key);
std::pair<const_iterator, const_iterator> equal_range(const Key &key) const;

还有三个用于查找的函数，这个函数对于multiset与multimap效果要好一点。

cpp

auto it = number.lower_bound(2);  // 不大于key的第一个位置
auto it2 = number.upper_bound(2); // 大于key的第一个位置
pair<multiset<int>::iterator, multiset<int>::iterator> ret =
    number.equal_range(2);
while (ret2.first != ret2.second) {
    cout << *ret2.first << " ";
    ++ret2.first;
}

容器对象的插入

cpp

// value_type，若是set/multiset代表的是key，若是map/multimap代表的是pair<const key, value>
// 1、插入一个元素到容器中
std::pair<iterator, bool> insert(const value_type &value);
std::pair<iterator, bool> insert(value_type &&value);

// 2、插入一个元素到容器的hint位置的前面
iterator insert(iterator hint, const value_type &value);
iterator insert(const_iterator hint, const value_type &value);
iterator insert(const_iterator hint, value_type &&value);

// 3、插入一个迭代器范围的元素到容器中
template <class InputIt>
void insert(InputIt first, InputIt last);

// 4、插入一个大括号范围的元素到容器中
void insert(std::initializer_list<value_type> ilist);

具体代码示例如下：

cpp

// 如果是set插入，需要判断返回值，multiset就不需要
set<int> number = {1, 4, 8, 7, 6, 4, 3, 2};
auto ret = number.insert(10);
if (ret.second) {
    cout << "添加成功" << *ret.first << endl;
} else {
    cout << "添加失败，这个元素已经存在set之中: " << endl;
}

// 添加一对迭代器范围元素
vector<int> vec{10, 9, 8, 5, 30, 20, 11, 39};
number.insert(vec.begin(), vec.end());
number.insert({100, 21, 500});
display(number);

// 如果是map插入，需要判断返回值，multimap就不需要
map<string, Point> number;
auto ret3 = number.insert(std::make_pair("999", Point(10, 40)));
if (ret3.second) {
    cout << "添加元素成功 : " << ret3.first->first
         << ret3.first->second << endl;
} else {
    cout << "添加失败，该元素存在于map之中 : "
         << ret3.first->first
         << ret3.first->second << endl;
}

容器对象的删除

cpp

// 1、删除迭代器指向的一个元素
void erase(iterator pos); // 删除某个位置元素
iterator erase(const_iterator pos);
iterator erase(iterator pos);

// 2、删除迭代器范围的元素
void erase(iterator first, iterator last); // 删除某个返回的元素
iterator erase(const_iterator first, const_iterator last);

cpp

auto it = number.begin();
++it;
++it;
number.erase(it);

下标访问

只有map支持下标访问，且兼具插入与修改的功能，所以使用起来比较方便

cpp

T& operator[]( const Key& key );
T& operator[]( Key&& key );

演示实例

cpp

map<string, Point> number = {
                                {"1", Point(1, 2)},
                                {"4", Point(3, 4)},
                                {"3", Point(4, 4)},
} 

cout << "points[\"1\"] = " << points["1"] << endl; // 查找
cout << "points[\"0\"] = " << points["0"] << endl; // 插入

points["4"] = Point(10, 20);                       // 修改

针对自定义类型的操作

对于四种关联式容器而言，它们的模板参数中都有一个Compare，默认采用的是std::less，所以如果Key是自定义类型，需要自己传递Compare类型的参数才能满足条件，否则无法通过编译。下面以自定义类型Point为例，以点到原点的距离为标准进行比较

cpp

class Point {
public:
    double getDistance() const {
        return hypot(_ix, _iy);
    }
    friend bool operator<(const Point &lhs, const Point &rhs); // std::less
    friend class ComparePoint;                                 // 函数对象
private:
    int _ix;
    int _iy;
};

// 第一种方式：模板的特化。使用Compare的默认值std::less,只是Key类型是Point，所以需要特化
namespace std {
    template <>
    struct less<Point> {
        bool operator()(const Point &lhs, const Point &rhs) {
            if (lhs.getDistance < rhs.getDistance) {
                return true;
            } else if (lhs.getDistance == rhs.getDistance) {
                if (lhs.getX() < rhs.getX()) {
                    return true;
                } else if (lhs.getX() == rhs.getX()) {
                    if (lhs.getY() < rhs.getY()) {
                        return true;
                    } else {
                        return false;
                    }
                } else {
                    return false;
                }
            } else {
                return false;
            }
        }
    };
} // end of namespace std

// 第二种形式：运算符重载。因为std::less的本质就在比较lhs < rhs
bool operator<(const Point &lhs, const Point &rhs) {
    //......
}

// 第三种形式：函数对象。重新给Compare传递一个参数，不使用默认值std::less
struct ComparePoint {
    bool operator()(const Point &lhs, const Point &rhs) const {
        //.......
    }
};

cpp

void test() {
    set<Point, PointComparator> points =
        {
            Point(1, 2),
            Point(3, 4),
            Point(-1, 2),
            Point(3, 4),
            Point(0, 6),
        };
    display(points);
}
// 这样上述代码就可以正常编译通过，还可以运行

参考资料

cppreference-容器库

log4cpp

C++11智能指针

C++11线程库

C++11其他新特性

C++20协程

workflow

关联式容器

红黑树的五大特征

类模板声明

关联式容器的性质

容器对象的初始化

遍历容器

容器对象的查找

count()与find()

另外三个查找函数

容器对象的插入

容器对象的删除

下标访问

针对自定义类型的操作

参考资料

关联式容器 ​

红黑树的五大特征 ​

类模板声明 ​

关联式容器的性质 ​

容器对象的初始化 ​

遍历容器 ​

容器对象的查找 ​

count()与find() ​

另外三个查找函数 ​

容器对象的插入 ​

容器对象的删除 ​

下标访问 ​

针对自定义类型的操作 ​

参考资料 ​

关联式容器

红黑树的五大特征

类模板声明

关联式容器的性质

容器对象的初始化

遍历容器

容器对象的查找

count()与find()

另外三个查找函数

容器对象的插入

容器对象的删除

下标访问

针对自定义类型的操作

参考资料