关联式容器
#STL 2024-11-24

关于底层红黑树的原理还是另开一篇文章吧，这里重点讲 set 和 map，至于像其它类型的 set 和 map 就罗列一张表看看区别，因为接口的使用并没有太大的区别。

set

不支持下标（没有重载[]）、不支持迭代器修改元素（每次修改必然得调整，这不合情理）。

查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
iterator find( const Key& key );

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator 
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::find(const Key& k) {
  link_type y = header;        // Last node which is not less than k. 
  link_type x = root();        // Current node. 

  while (x != 0) 
    if (!key_compare(key(x), k))
      y = x, x = left(x);
    else
      x = right(x);

  iterator j = iterator(y);   
  return (j == end() || key_compare(k, key(j.node))) ? end() : j;
}


返回值是一个迭代器，也就是找到的元素的迭代器。

我们核心源码 find 中的最后一行，如果说找到就会返回该迭代器，否则就返回 end 迭代器。

至此，我们也就轻松写出如下代码：

1
2
3
4
5
6
7
8
set<int>	data = { 1, 4, 9, 89 };
auto		item = data.find( 4 );
if ( item != data.end() )
{
	cout << "find success" << endl;
}else{
	cout << "find failed" << endl;
}

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 1. 插入单个元素，返回一个 pair，其中第二个元素表示插入是否成功
std::pair<iterator, bool> insert(const value_type& val);
std::pair<iterator, bool> insert(value_type&& val);

// 2. 带提示位置插入单个元素（几乎不用，因为插入之后也会被自动排序）
iterator insert(const_iterator hint, const value_type& val);
iterator insert(const_iterator hint, value_type&& val);

// 3. 插入一个范围内的元素
template <class InputIterator>
void insert(InputIterator first, InputIterator last);

// 4. 插入初始化列表中的元素
void insert(std::initializer_list<value_type> il);

set 中支持好几种插入行为，我们要关注一下这些第一个接口执行之后的返回值。

直接插入单个元素：返回值类型为 std::pair<iterator, bool>，第一个参数是插入值的迭代器，第二个参数用以判断插入是否成功。

1
2
3
4
5
6
7
8
set<int>	data = { 1, 4, 9, 89 };
auto		item = data.insert( 10 );
if ( item.second )
{
	cout << *item.first << " insert success" << endl;
}else{
	cout << "insert failed" << endl;
}

删除

1
2
3
4
5
6
7
8
// 1. 按照迭代器位置删除单个元素，返回指向被删除元素的下一个元素的迭代器
iterator erase(const_iterator pos);

// 2. 按照键值删除元素，返回被删除的元素个数（0 或 1，因为 set 中元素唯一）
size_type erase(const key_type& key);

// 3. 按照迭代器范围删除元素，删除 [first, last) 范围内的元素，返回 last
iterator erase(const_iterator first, const_iterator last);

关联式容器底层是红黑树，那这些节点必然不可能保证是连续的内存，因此如果我们连续删除元素的话，是需要记得更新迭代器的。刚好 erase 之后返回的迭代器就是被删除元素的下一个元素的迭代器，很方便我们更新。

1
2
3
4
5
6
7
8
9
10
set<int> data = { 1, 4, 9, 9, 9, 89 };
for ( auto it = data.begin(); it != data.end(); )
{
	if ( *it == 9 )	// 删除连续奇数 9
	{
		it = data.erase( it );
	}else{
		++it;
	}
}

修改元素

std::set 不允许直接修改已有元素的值，因为 set 是基于有序的红黑树实现的，修改元素值可能会破坏其有序性和唯一性。这意味着无法通过迭代器或引用来直接更改 set 中的元素。要修改 set 中的元素，通常有以下两种方法：

（一）先删除再插入

此番操作行为等价于 修改元素 2 为 20

1
2
3
4
5
std::set<int> s = {1, 2, 3};


s.erase(2);     // 删除旧值
s.insert(20);   // 插入新值

（二）C++17 的 extra 方法

1
2
3
4
5
std::set<int> s = {1, 2, 3};

auto node = s.extract(2);  // 摘取元素 2
node.value() = 20;         // 修改摘取的值
s.insert(std::move(node)); // 插入修改后的值

C++17 引入了 extract 方法，可以将元素“摘取”出来进行修改，然后重新插入回 set。这可以避免删除和插入带来的额外开销。

针对于自定义类型

1
2
3
4
5
template< class InputIt >
set( InputIt first, InputIt last,
     const Compare& comp = Compare(),
     const Allocator& alloc = Allocator() 
   );

我们可以看到这里面的 comp 参数，接受一个函数对象，默认的函数对象是 Compare()。

1
2
3
4
5
6
template <class Key, class Compare = less<Key>, class Alloc = alloc>

template <class T>
struct less : public binary_function<T, T, bool> {	// 从小到大排序
    bool operator()(const T& x, const T& y) const { return x < y; }
};

自此，我们就知道 set 自动排序为递增的缘由，那我们可以也可以改为自动排序为递减：set<int,greater<int>> data;

1
2
3
4
template <class T>
struct greater : public binary_function<T, T, bool> {
    bool operator()(const T& x, const T& y) const { return x > y; }
};

当然，这些都是 STL 本身提供的接口，如果我们管理的对象是自定义类型，就务必要自己提供一个作为Compare，否则整个 set 就无法正常使用。

模板的特化

可以看到默认为调用 std::less ，这是一个模板类。

1
2
3
4
5
6
7
8
9
template<typename _Tp>
struct less : public binary_function<_Tp, _Tp, bool>
{
	bool
	operator()( const _Tp & __x, const _Tp & __y ) const
	{
		return(__x < __y);
	}
};

那我们就为自己的类进行特化，默认就会去调用了。

1
2
3
4
5
6
7
8
namespace std {
template<>
struct less<MyClass> {
  bool operator()(const MyClass &lhs, const MyClass &rhs) const {
    return lhs.value > rhs.value;
  }
};
}

运算符重载

1
2
3
4
5
6
7
8
9
10
11
class MyClass {
public:
    int value;

    MyClass(int v) : value(v) {}

    // 重载 `<` 运算符
    bool operator<(const MyClass& other) const {
        return value < other.value;
    }
};

函数对象

1
2
3
4
5
6
7
8
9
10
11
12
13
class MyClass {
public:
    int value;

    MyClass(int v) : value(v) {}
};

// 自定义比较函数对象
struct MyCompare {
    bool operator()(const MyClass& a, const MyClass& b) const {
        return a.value < b.value;
    }
};

map

查找

1
2
3
4
5
6
7
8
map<int, string>::iterator it = number.find( 2 );
if ( it != number.end() )
{
	cout	<< "该元素存在map中 " << it->first
		<< "   " << it->second << endl;
}else  {
	cout << "查找失败，该元素不存在map中" << endl;
}

插入

1
2
3
4
5
6
7
8
9
pair<map<int, string>::iterator, bool> ret =
	number.insert( { 7, "shenzhen" } );
if ( ret.second )
{
	cout	<< "插入成功 " << ret.first->first
		<< "   " << ret.first->second << endl;
}else  {
	cout << "插入失败，该元素存在map中" << endl;
}

支持下标

map 支持像数组那样通过下标进行操作，通过下标可以添加元素、查找元素、修改元素。

读取时应该用 at() 更安全，写入时才需要用带有自动创建功能的 []。

map 与 RAII

梦幻联动：map 容器与 RAII 的双向奔赴

如果 map 中元素的值类型是 RAII 类型，其析构函数会在元素被删除时自动调用。

map 被移动时，不会调用元素的移动函数，因为 map 里只存着指向红黑树根节点的指针，只需指针移动即可。

map 被拷贝时，会调用元素的拷贝函数，如果元素不支持拷贝，则 map 的拷贝也会被禁用（delete）掉。

map 被析构时，其所有元素都会被析构。

容器总结与选择

容器 数据结构 特点 是否有序
map 红黑树 键值对，唯一键 有序
set 红黑树 唯一元素 有序
multimap 红黑树 键值对，键允许重复 有序
multiset 红黑树 元素允许重复 有序
unordered_map 哈希表 键值对，唯一键 无序
unordered_set 哈希表 唯一元素 无序
unorderes_multimap 哈希表 元素允许重复 无序
unorderes_multiset 哈希表 键值对，唯一键 无序

红黑树 结构的容器是按键值排序的，因此是有序的。

哈希表 结构的容器则不保证顺序，所以是无序的。