企业官网建设流程全解析

1. 序列式容器与关联式容器

C++ STL 中的容器可以分为序列式容器和关联式容器。

常见的序列式容器包括：

string、vector、list、deque、array、forward_list

这些容器按照元素在容器中的位置保存和访问数据，数据之间通常是线性关系。

关联式容器则按照关键字保存和访问数据，常见的关联式容器包括：

set、multiset、map、multimap

set和map的底层通常使用红黑树实现。红黑树是一棵近似平衡的二叉搜索树，因此它们的插入、删除和查找操作的时间复杂度通常为：

O(log N)

二者的主要使用场景如下：

• set：保存关键字，适合搜索、排序和去重。

• map：保存键值对，适合建立关键字和数据之间的映射关系。

2. set 系列容器

2.1 set 的特点

set的基本声明如下：

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

其中：

• T是容器中元素的类型。

• Compare是比较规则，默认使用less<T>。

• Alloc是空间配置器，一般不需要手动设置。

set具有以下特点：

1. 元素不能重复。

2. 元素会自动排序。

3. 默认按照升序排列。

4. 插入、删除和查找的时间复杂度通常为O(log N)。

5. 不能通过迭代器修改元素。

2.2 set 的构造

无参构造

set<int> values;

初始化列表构造

set<int> values = {5, 2, 8, 2, 1};

容器中的最终结果为：

1 2 5 8

set会自动排序并删除重复元素。

迭代器区间构造

vector<int> numbers = {5, 2, 8, 2, 1}; set<int> values( numbers.begin(), numbers.end() );

拷贝构造

set<int> first = {1, 2, 3}; set<int> second(first);

2.3 set 的迭代器

set支持正向迭代器和反向迭代器：

values.begin(); values.end(); values.rbegin(); values.rend();

正向遍历：

for (auto iterator = values.begin(); iterator != values.end(); ++iterator) { cout << *iterator << " "; }

范围for遍历：

for (const auto& value : values) { cout << value << " "; }

反向遍历：

for (auto iterator = values.rbegin(); iterator != values.rend(); ++iterator) { cout << *iterator << " "; }

由于set中的元素同时也是搜索关键字，修改元素可能会破坏底层搜索树的结构，因此不能通过迭代器修改元素。

set<int> values = {1, 2, 3}; auto iterator = values.begin(); // 不允许这样修改 // *iterator = 10;

如果需要修改，应先删除原来的元素，再插入新元素：

values.erase(1); values.insert(10);

2.4 insert：插入元素

插入单个元素

set<int> values; values.insert(5); values.insert(2); values.insert(7); values.insert(5);

第二次插入5会失败，因为set不允许元素重复。

判断是否插入成功

auto result = values.insert(5); if (result.second) { cout << "插入成功" << endl; } else { cout << "元素已经存在" << endl; }

insert()返回一个pair<iterator, bool>：

• first：指向对应元素的迭代器。

• second：表示是否插入成功。

插入初始化列表

values.insert({2, 8, 3, 9});

已经存在的元素不会被重复插入。

插入一段迭代器区间

vector<int> numbers = {10, 20, 30}; values.insert( numbers.begin(), numbers.end() );

2.5 find：查找元素

set<int> values = {2, 4, 5, 7, 8, 9}; int target = 7; auto position = values.find(target); if (position != values.end()) { cout << "找到元素：" << *position << endl; } else { cout << "元素不存在" << endl; }

如果找到元素，find()返回对应位置的迭代器；如果没有找到，则返回end()。

需要注意，算法库中的find()和set自身的find()效率不同：

// 时间复杂度为 O(N) auto first = find( values.begin(), values.end(), target ); // 时间复杂度通常为 O(log N) auto second = values.find(target);

使用set时，应优先调用容器自身的find()。

2.6 count：统计元素数量

if (values.count(7)) { cout << "7存在" << endl; } else { cout << "7不存在" << endl; }

由于普通set不允许元素重复，因此count()的返回值只可能是：

• 0：元素不存在。

• 1：元素存在。

2.7 erase：删除元素

根据元素值删除

size_t count = values.erase(7); if (count == 0) { cout << "元素不存在" << endl; }

根据迭代器删除

auto position = values.find(8); if (position != values.end()) { values.erase(position); }

删除最小元素

由于set默认按照升序排列，因此begin()指向最小元素：

if (!values.empty()) { values.erase(values.begin()); }

删除迭代器区间

set<int> values = { 10, 20, 30, 40, 50, 60, 70, 80, 90 }; // 第一个大于或等于30的元素 auto first = values.lower_bound(30); // 第一个严格大于60的元素 auto last = values.upper_bound(60); // 删除[30, 60] values.erase(first, last);

删除后剩余：

10 20 70 80 90

2.8 lower_bound 和 upper_bound

lower_bound

lower_bound(value)返回第一个大于或等于value的元素。

set<int> values = { 10, 20, 30, 40, 50 }; auto position = values.lower_bound(25); if (position != values.end()) { cout << *position << endl; }

输出：

30

upper_bound

upper_bound(value)返回第一个严格大于value的元素。

auto position = values.upper_bound(30); if (position != values.end()) { cout << *position << endl; }

输出：

40

2.9 set 设置降序排列

set默认使用less<T>，按照升序排列。

使用greater<T>可以设置为降序：

set<int, greater<int>> values = { 5, 2, 8, 1 }; for (int value : values) { cout << value << " "; }

输出：

8 5 2 1

2.10 multiset 和 set 的区别

multiset和set的使用方式基本相同，主要区别是multiset允许保存重复元素。

multiset<int> values = { 4, 2, 7, 2, 4, 8, 4, 5, 4, 9 };

遍历结果：

2 2 4 4 4 4 5 7 8 9

统计某个元素出现的次数：

cout << values.count(4) << endl;

输出：

4

删除指定值时，会删除所有相等的元素：

values.erase(4);

查找某个值对应的完整范围，可以使用：

auto range = values.equal_range(2); for (auto iterator = range.first; iterator != range.second; ++iterator) { cout << *iterator << " "; }

set与multiset的区别可以总结为：

3. map 系列容器

3.1 map 的特点

map用来保存键值对，其基本声明如下：

template< class Key, class T, class Compare = less<Key>, class Alloc = allocator<pair<const Key, T>> > class map;

其中：

• Key是键的类型。

• T是键所映射的数据类型。

• Compare是键的比较规则。

• Alloc是空间配置器。

map具有以下特点：

1. 每个键都是唯一的。

2. 数据按照键自动排序。

3. 键不能直接修改。

4. 键对应的值可以修改。

5. 插入、删除和查找的时间复杂度通常为O(log N)。

3.2 pair 键值对

map使用pair保存键值对。

pair<string, string> data( "sort", "排序" );

pair中包含两个成员：

data.first; // 第一个数据 data.second; // 第二个数据

对于map而言：

• first表示键。

• second表示键对应的值。

也可以使用make_pair()创建键值对：

auto data = make_pair( "insert", "插入" );

map中实际保存的元素类型可以表示为：

pair<const Key, T>

键使用const修饰，因此不能直接修改键。

3.3 map 的构造

无参构造

map<string, string> dictionary;

初始化列表构造

map<string, string> dictionary = { {"left", "左边"}, {"right", "右边"}, {"insert", "插入"}, {"string", "字符串"} };

迭代器区间构造

map<string, int> first = { {"apple", 3}, {"banana", 2} }; map<string, int> second( first.begin(), first.end() );

拷贝构造

map<string, int> third(first);

3.4 map 的遍历

使用普通迭代器遍历：

for (auto iterator = dictionary.begin(); iterator != dictionary.end(); ++iterator) { cout << iterator->first << ":" << iterator->second << endl; }

使用范围for遍历：

for (const auto& data : dictionary) { cout << data.first << ":" << data.second << endl; }

map默认按照键的升序遍历，而不是按照值排序。

map同样支持反向迭代器：

dictionary.rbegin(); dictionary.rend();

3.5 insert：插入键值对

方式一：先创建 pair 对象

pair<string, string> data( "first", "第一个" ); dictionary.insert(data);

方式二：构造临时 pair

dictionary.insert( pair<string, string>( "second", "第二个" ) );

方式三：使用 make_pair

dictionary.insert( make_pair("sort", "排序") );

方式四：使用初始化列表

dictionary.insert({ "auto", "自动的" });

初始化列表的写法通常更加简洁。

判断插入是否成功

auto result = dictionary.insert({ "left", "左边" }); if (result.second) { cout << "插入成功" << endl; } else { cout << "键已经存在" << endl; }

map判断数据是否重复时，只比较键。

即使键对应的值不同，只要键已经存在，插入仍然会失败。

dictionary.insert({ "left", "左边" }); dictionary.insert({ "left", "剩余" });

第二次插入不会覆盖第一次保存的值。

3.6 find：根据键查找数据

string word; cin >> word; auto position = dictionary.find(word); if (position != dictionary.end()) { cout << position->second << endl; } else { cout << "没有找到对应单词" << endl; }

如果查找成功，迭代器可以同时访问键和值：

position->first; position->second;

3.7 使用迭代器修改值

map不允许修改键，但是允许修改键所映射的值：

auto position = dictionary.find("left"); if (position != dictionary.end()) { position->second = "左边、剩余"; }

下面的写法不允许：

// position->first = "right";

因为修改键会破坏底层搜索树的结构。

3.8 count：判断键是否存在

if (dictionary.count("left")) { cout << "left存在" << endl; } else { cout << "left不存在" << endl; }

普通map中的键不能重复，所以count()的返回值只可能是0或1。

3.9 erase：删除键值对

根据键删除

size_t count = dictionary.erase("left"); if (count == 0) { cout << "键不存在" << endl; }

根据迭代器删除

auto position = dictionary.find("right"); if (position != dictionary.end()) { dictionary.erase(position); }

删除一段范围

map<int, string> values = { {10, "A"}, {20, "B"}, {30, "C"}, {40, "D"}, {50, "E"} }; auto first = values.lower_bound(20); auto last = values.upper_bound(40); values.erase(first, last);

这段代码会删除键位于[20, 40]范围内的键值对。

3.10 map 的 lower_bound 和 upper_bound

map的范围查找比较的是键。

map<int, string> values = { {10, "A"}, {20, "B"}, {30, "C"}, {40, "D"} };

查找第一个大于或等于25的键：

auto position = values.lower_bound(25); if (position != values.end()) { cout << position->first << endl; }

输出：

30

查找第一个严格大于30的键：

auto position = values.upper_bound(30); if (position != values.end()) { cout << position->first << endl; }

输出：

40

3.11 operator[] 接口

operator[]是map中非常重要的接口，它同时具有插入、查找和修改功能。

基本形式：

mapped_type& operator[]( const key_type& key );

键不存在时

如果键不存在，operator[]会插入一个新的键值对，并对值进行默认初始化。

map<string, string> dictionary; dictionary["insert"];

插入的键值对相当于：

{"insert", string()}

插入并修改

dictionary["left"] = "左边";

当"left"不存在时，会先插入，再修改对应的值。

修改已有数据

dictionary["left"] = "左边、剩余";

当"left"已经存在时，会直接修改对应的值。

查找并访问

cout << dictionary["left"] << endl;

当键存在时，operator[]会返回该键所对应值的引用。

因此，operator[]可以总结为：

如果只想判断某个键是否存在，应使用find()或count()，防止插入不需要的数据。

3.12 使用 map 统计次数

使用 find 和迭代器统计

#include <iostream> #include <map> #include <string> using namespace std; int main() { string fruits[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" }; map<string, int> counts; for (const auto& fruit : fruits) { auto position = counts.find(fruit); if (position == counts.end()) { counts.insert({fruit, 1}); } else { ++position->second; } } for (const auto& data : counts) { cout << data.first << ":" << data.second << endl; } return 0; }

使用 operator[] 统计

利用operator[]可以简化代码：

map<string, int> counts; for (const auto& fruit : fruits) { ++counts[fruit]; }

当水果第一次出现时，会先插入：

{fruit, 0}

然后执行自增，数量变成1。再次出现时，直接将原来的数量加一。

3.13 multimap 和 map 的区别

multimap和map的使用方式基本相同，主要区别是multimap允许键重复。

multimap<string, int> scores; scores.insert({"Tom", 90}); scores.insert({"Tom", 95}); scores.insert({"Jack", 80});

统计某个键的数量：

cout << scores.count("Tom") << endl;

输出：

2

获取一个键对应的所有数据：

auto range = scores.equal_range("Tom"); for (auto iterator = range.first; iterator != range.second; ++iterator) { cout << iterator->first << ":" << iterator->second << endl; }

删除指定键时，会删除该键对应的所有键值对：

scores.erase("Tom");

multimap不支持operator[]。因为一个键可能对应多个值，无法通过一个键确定应该访问或修改哪一个值。

4. set 和 map 的典型应用

4.1 set 的常见应用

set适合解决：

• 数据去重。

• 数据自动排序。

• 快速判断元素是否出现。

• 求两个数组的交集。

• 记录链表节点，判断链表是否存在环。

• 查找某个范围内的数据。

例如，将数组放入set，可以同时完成去重和排序：

vector<int> numbers = { 4, 2, 7, 2, 4, 8 }; set<int> values( numbers.begin(), numbers.end() );

4.2 map 的常见应用

map适合解决：

• 统计元素出现次数。

• 建立字典映射关系。

• 建立原对象和新对象之间的映射。

• 根据关键字快速查找数据。

• 统计高频单词。

• 保存编号和对象之间的对应关系。

例如：

map<string, int> counts; counts["apple"]++; counts["banana"]++; counts["apple"]++;

最终结果为：

apple: 2 banana: 1

5. 常用接口总结

set 常用接口

map 常用接口

6. 总结

set和map都是基于关键字组织数据的关联式容器，底层通常使用红黑树实现。

set的核心特点是：

• 元素不能重复。

• 自动排序。

• 适合搜索和去重。

• 不能直接修改元素。

map的核心特点是：

• 保存键值对。

• 键不能重复。

• 按照键自动排序。

• 键不能修改，但对应的值可以修改。

• operator[]同时具有插入、访问和修改功能。

set和map的插入、删除和查找效率通常为O(log N)。如果需要保存重复元素，可以分别使用multiset和multimap。