关联容器

本文最后更新于：2022年3月19日 凌晨

此文整理与👉容器库 - cppreference.com

关联容器实现能快速查找（ O(log n) 复杂度）的数据结构。

std::set#

定义于头文件 <set>

std::set 是关联容器，含有 Key 类型对象的已排序集并去重。用比较函数 比较 (Compare) 进行排序。搜索、移除和插入拥有对数复杂度。 set 通常以红黑树实现。

  • 返回指向 set 首元素的迭代器。

  • 若 set 为空，则返回的迭代器将等于 end() 。

  • 返回值

指向首元素的迭代器。

  • 复杂度

常数。

std::set<>::begin,std::set<>::cbegin#

#include <algorithm>
#include <iostream>
#include <set>

int main() {
    std::set<int> set = { 3, 1, 4, 1, 5, 9, 2, 6, 5 };
    std::for_each(set.cbegin(), set.cend(), [](int x) {
        std::cout << x << ' ';
    });
    std::cout << '\n';
}

std::set<Key,Compare,Allocator>::empty#

检查容器是否无元素

std::set<Key,Compare,Allocator>::size#

返回容器中的元素数

std::set<Key,Compare,Allocator>::clear#

从容器擦除所有元素。此调用后 size() 返回零

std::set<Key,Compare,Allocator>::insert#

插入元素到容器，若容器未含拥有等价关键的元素。

std::set<Key,Compare,Allocator>::emplace#

若容器中无拥有该关键的元素，则插入以给定的 args 原位构造的新元素到容器。

细心地使用 emplace 允许在构造新元素的同时避免不必要的复制或移动操作

std::set<Key,Compare,Allocator>::erase#

擦除元素

std::set<Key,Compare,Allocator>::find#

寻找键等于 key 的的元素。

#include <set>
#include <iostream>
 
int main()
{
    std::set<int> numbers;
    std::cout << "Initially, numbers.empty(): " << numbers.empty() << '\n';
 
    numbers.insert(13317); 
    numbers.insert(3);
    numbers.insert(2);
    std::cout << "After adding elements, numbers.empty(): " << numbers.empty() << '\n';
    
    std::for_each(numbers.cbegin(), numbers.cend(), [](int x) {
    std::cout << x << ' ';
  	});
    
    numbers.emplace(1);
    
    numbers.erase(1);
    
    uint32_t size = numbers.size();
    std::cout << "nums contains " << size << " elements.\n";
    
    auto search = numbers.find(2);
    if (search != numbers.end()) {
        std::cout << "Found " << (*search) << '\n';
    } else {
        std::cout << "Not found\n";
    }
    
    numbers.clear();
	return 0;
}

std::map#

键值对的集合，按照键排序，键是唯一的

  • std::map 是有序键值对容器，它的元素的键是唯一的。

  • 用比较函数 Compare 排序键。搜索、移除和插入操作拥有对数复杂度。

  • map 通常实现为红黑树。

元素访问

std::map<Key,T,Compare,Allocator>::at#

返回到拥有等于 key 的关键的元素被映射值的引用。

std::map<Key,T,Compare,Allocator>::empty#

检查容器是否为空

std::map<Key,T,Compare,Allocator>::size#

返回容纳的元素数

std::map<Key,T,Compare,Allocator>::clear#

清除内容

std::map<Key,T,Compare,Allocator>::insert#

插入元素或结点 (C++17 起)

std::map<Key,T,Compare,Allocator>::insert_or_assign#

插入元素，或若键已存在则赋值给当前元素

std::map<Key,T,Compare,Allocator>::emplace#

原位构造元素

std::map<Key,T,Compare,Allocator>::emplace_hint#

使用提示原位构造元素

std::map<Key,T,Compare,Allocator>::try_emplace#

若键不存在则原位插入，若键存在则不做任何事

std::map<Key,T,Compare,Allocator>::erase#

擦除元素

std::map<Key,T,Compare,Allocator>::find#

寻找带有特定键的元素

std::erase_if (std::map)#

擦除所有满足特定判别标准的元素

#include <map>
#include <iostream>
#include <utility>
 
int main(void)
{
    std::map<int,int> numbers;
    
    numbers.emplace(42, 13);
    numbers.emplace_hint(41, 12);
    numbers.insert(std::make_pair(13317, 123)); 
    std::cout << "After adding elements, numbers.empty(): " << numbers.empty() << '\n';
    
    std::cout << "After elements, numbers.size(): " << numbers.size() << '\n';
    
    numbers.try_emplace(40, 10);

	numbers.erase(40);
	
    const auto count = std::erase_if(data, [](const auto& item) {
        auto const& [key, value] = item;
        return (key & 1) == 1;
    });
    std::cout << "Erase items with odd keys:\n" << data << '\n'
              << count << " items removed.\n";
    
    myMap.insert_or_assign("a", "apple");
    
	numbers.find(42);
	std::cout << "After elements, numbers.clear(): " << numbers.clear() << '\n';
	return 0;
}

std::multiset#

键的集合，按照键排序

迭代器
begin cbegin(C++11) 返回指向起始的迭代器 (公开成员函数)
end cend(C++11) 返回指向末尾的迭代器 (公开成员函数)
rbegin crbegin(C++11) 返回指向起始的逆向迭代器 (公开成员函数)
rend crend(C++11) 返回指向末尾的逆向迭代器 (公开成员函数)
容量
empty 检查容器是否为空 (公开成员函数)
size 返回容纳的元素数 (公开成员函数)
max_size 返回可容纳的最大元素数 (公开成员函数)
修改器
clear 清除内容 (公开成员函数)
insert 插入元素或结点 (C++17 起) (公开成员函数)
emplace(C++11) 原位构造元素 (公开成员函数)
emplace_hint(C++11) 使用提示原位构造元素 (公开成员函数)
erase 擦除元素 (公开成员函数)
swap 交换内容 (公开成员函数)
extract(C++17) 从另一容器释出结点 (公开成员函数)
merge(C++17) 从另一容器接合结点 (公开成员函数)
查找
count 返回匹配特定键的元素数量 (公开成员函数)
find 寻找带有特定键的元素 (公开成员函数)
contains(C++20) 检查容器是否含有带特定键的元素 (公开成员函数)
equal_range 返回匹配特定键的元素范围 (公开成员函数)
lower_bound 返回指向首个不小于给定键的元素的迭代器 (公开成员函数)
upper_bound 返回指向首个大于给定键的元素的迭代器
erase_if(std::multiset)(C++20) 擦除所有满足特定判别标准的元素

std::multimap#

键值对的集合，按照键排序

迭代器
begincbegin(C++11) 返回指向起始的迭代器 (公开成员函数)
endcend(C++11) 返回指向末尾的迭代器 (公开成员函数)
rbegincrbegin(C++11) 返回指向起始的逆向迭代器 (公开成员函数)
rendcrend(C++11) 返回指向末尾的逆向迭代器 (公开成员函数)
容量
empty 检查容器是否为空 (公开成员函数)
size 返回容纳的元素数 (公开成员函数)
max_size 返回可容纳的最大元素数 (公开成员函数)
修改器
clear 清除内容 (公开成员函数)
insert 插入元素或结点 (C++17 起) (公开成员函数)
emplace(C++11) 原位构造元素 (公开成员函数)
emplace_hint(C++11) 使用提示原位构造元素 (公开成员函数)
erase 擦除元素 (公开成员函数)
swap 交换内容 (公开成员函数)
extract(C++17) 从另一容器释出结点 (公开成员函数)
merge(C++17) 从另一容器接合结点 (公开成员函数)
查找
count 返回匹配特定键的元素数量 (公开成员函数)
find 寻找带有特定键的元素 (公开成员函数)
contains(C++20) 检查容器是否含有带特定键的元素 (公开成员函数)
equal_range 返回匹配特定键的元素范围 (公开成员函数)
lower_bound 返回指向首个不小于给定键的元素的迭代器 (公开成员函数)
upper_bound 返回指向首个大于给定键的元素的迭代器 (公开成员函数)
观察器
key_comp 返回用于比较键的函数 (公开成员函数)
value_comp 返回用于在value_type类型的对象中比较键的函数。
erase_if(std::multimap)(C++20) 擦除所有满足特定判别标准的元素
Associative

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！