当前位置: 首页 > news >正文

部门网站的开发 意义百度的seo排名怎么刷

部门网站的开发 意义,百度的seo排名怎么刷,网站开发实训设计报告,团购网站怎么运营C 标准模板库(STL)中的关联式容器以其强大的功能和高效性成为开发者解决复杂数据组织问题的重要工具。其中,set 和 map 是最常用的两类关联容器。本篇博客将从基本特性、底层实现、用法详解、高级案例以及性能优化等多个角度,详细…

C++ 标准模板库(STL)中的关联式容器以其强大的功能和高效性成为开发者解决复杂数据组织问题的重要工具。其中,setmap 是最常用的两类关联容器。本篇博客将从基本特性、底层实现、用法详解、高级案例以及性能优化等多个角度,详细解读它们的设计与使用。


目录

1. 什么是关联式容器

关联式容器的核心特性

2. set 容器详解

2.1 基本概念与特性

2.2 底层实现:红黑树

红黑树的特性

红黑树的操作

2.3 构造函数

2.4 常用操作与复杂度分析

插入操作

查找操作

删除操作

遍历

2.5 特殊操作与技巧

(1) 自定义排序规则

(2) 范围删除

(3) 应用:求两个数组的交集

2.6 multiset 的区别与应用



1. 什么是关联式容器

关联式容器是一类根据关键字组织和管理数据的容器。与序列式容器(如 vectorlist)相比,关联式容器的主要区别如下:

特性关联式容器(set/map序列式容器(vector/list
数据存储顺序按关键字排序按插入顺序
数据访问复杂度O(log⁡N)O(\log N)O(logN)O(1)O(1)O(1) 或 O(N)O(N)O(N)
是否支持随机访问
是否支持按索引访问

关联式容器分为有序和无序两类:

  1. 有序容器:如 setmap,基于平衡二叉树(红黑树)实现,数据按排序规则组织。
  2. 无序容器:如 unordered_setunordered_map,基于哈希表实现,提供更高效的查找速度,但不保证元素顺序。

关联式容器的核心特性

  • 键值对:关联式容器通过关键字对元素进行组织,set 中的关键字即为数据本身,而 map 则以键值对形式存储数据。
  • 自动排序:有序容器会自动对数据进行排序(升序或自定义规则)。
  • 高效操作:插入、删除、查找的平均时间复杂度为 O(log⁡N)O(\log N)O(logN)(红黑树实现)。

2. set 容器详解

2.1 基本概念与特性

set 是一种集合数据结构,用于存储唯一且自动排序的元素。它的主要特点如下:

  • 数据唯一性:同一元素不能重复插入。
  • 自动排序:默认按升序排序,可通过自定义比较器更改排序规则。
  • 迭代器类型set 支持双向迭代器,不支持随机访问。
  • 底层实现:使用红黑树作为存储结构。

2.2 底层实现:红黑树

红黑树的特性

红黑树是一种平衡二叉搜索树,满足以下性质:

  1. 每个节点是红色或黑色。
  2. 根节点是黑色。
  3. 每个叶子节点(nullptr 或 NIL 节点)是黑色。
  4. 如果一个节点是红色,则其子节点必须是黑色(即红色节点不能相邻)。
  5. 从任意节点到其每个叶子节点的路径都包含相同数量的黑色节点。
红黑树的操作
  • 插入:通过旋转和重新着色,确保平衡性和红黑性质。
  • 删除:比插入更复杂,同样通过旋转和着色维护树的性质。
  • 查找:沿树遍历,时间复杂度为 O(log⁡N)O(\log N)O(logN)。

setmap 中,红黑树用来高效实现元素的有序存储和快速查找。


2.3 构造函数

set 提供以下几种构造方式:

  1. 默认构造:创建一个空集合。
    set<int> s;
    
  2. 初始化列表构造:直接用 {} 初始化集合。
    set<int> s = {3, 1, 4, 1, 5, 9};  // 重复元素自动去重
    
  3. 迭代器区间构造:从其他容器的元素构造集合。
    vector<int> v = {1, 2, 3, 4};
    set<int> s(v.begin(), v.end());
    
  4. 自定义比较规则
    set<int, greater<int>> s = {3, 1, 4};  // 按降序排序
    


2.4 常用操作与复杂度分析

操作函数复杂度说明
插入insert(value)O(log⁡N)O(\log N)O(logN)插入元素,若已存在则插入失败
删除erase(value)O(log⁡N)O(\log N)O(logN)删除指定元素
查找find(value)O(log⁡N)O(\log N)O(logN)返回迭代器,指向目标元素
统计count(value)O(log⁡N)O(\log N)O(logN)判断元素是否存在,结果为 0 或 1
遍历begin(), end()O(N)O(N)O(N)正向迭代访问所有元素
下界/上界lower_bound()/upper_bound()O(log⁡N)O(\log N)O(logN)返回 >= / > 某值的第一个元素的迭代器
插入操作
set<int> s;
auto res = s.insert(10);  // 插入 10
if (res.second) {cout << "插入成功" << endl;
} else {cout << "插入失败" << endl;
}
查找操作
if (s.find(20) != s.end()) {cout << "找到元素 20" << endl;
}
删除操作
s.erase(10);  // 删除值为 10 的元素
遍历
for (int x : s) {cout << x << " ";  // 正向遍历
}
for (auto it = s.rbegin(); it != s.rend(); ++it) {cout << *it << " ";  // 反向遍历
}

2.5 特殊操作与技巧

(1) 自定义排序规则

set 默认按升序排序,使用仿函数或 std::greater 可修改排序规则:

set<int, greater<int>> s = {3, 1, 4};
(2) 范围删除

删除值在 [low, high) 范围内的所有元素:

s.erase(s.lower_bound(10), s.upper_bound(50));
(3) 应用:求两个数组的交集
vector<int> intersection(const vector<int>& nums1, const vector<int>& nums2) {set<int> s1(nums1.begin(), nums1.end());set<int> s2(nums2.begin(), nums2.end());vector<int> result;for (int x : s1) {if (s2.count(x)) result.push_back(x);}return result;
}

2.6 multiset 的区别与应用

multisetset 的区别在于:

  1. multiset 允许存储重复元素。
  2. 插入、删除和查找操作的接口与 set 相同,但返回的结果会包含重复项。
multiset<int> ms = {1, 2, 2, 3};
ms.insert(2);  // 再次插入 2

3. map 容器详解

3.1 基本概念与特性

map 是一个关联式容器,用于存储键值对(key-value)。与 set 相比,map 不仅存储键(key),还存储与每个键关联的值(value)。
map 的主要特点包括:

  • 键唯一性:每个键在 map 中都是唯一的。
  • 自动排序:默认按照键的升序排序,也可以通过自定义比较器来更改排序规则。
  • 底层实现:基于红黑树实现,操作复杂度为 O(log⁡N)O(\log N)O(logN)。
  • 支持随机访问:与 set 不同,map 中存储的键值对支持通过键快速查找对应的值。
map<int, string> m;
m[1] = "apple";  // 插入键值对 (1, "apple")
m[2] = "banana"; // 插入键值对 (2, "banana")
m[3] = "cherry"; // 插入键值对 (3, "cherry")
内部存储结构

map 使用红黑树存储数据,保证了所有元素按键值自动排序。在 map 中,每个节点存储一个 pair<const Key, T>,其中 const Key 表示键,T 表示值。红黑树的特点确保了查找、插入和删除操作的时间复杂度都为 O(log⁡N)O(\log N)O(logN)。


3.2 构造与初始化

map 提供了多种构造方法,以适应不同的使用场景:

  1. 默认构造:创建一个空 map

    map<int, string> m;
    
  2. 初始化列表构造:通过初始化列表直接创建 map

    map<int, string> m = {{1, "apple"}, {2, "banana"}, {3, "cherry"}};
    
  3. 范围构造:从另一个容器(如 setvector 等)构造 map

    vector<pair<int, string>> v = {{1, "apple"}, {2, "banana"}};
    map<int, string> m(v.begin(), v.end());
    
  4. 自定义比较器:通过传入自定义比较器,指定键的排序方式。

    map<int, string, greater<int>> m;  // 降序排序
    m[2] = "banana";
    m[1] = "apple";
    

3.3 常用操作与复杂度分析

操作函数复杂度说明
插入insert(pair)O(log⁡N)O(\log N)O(logN)插入一个键值对,若已存在则插入失败
插入或修改operator[]O(log⁡N)O(\log N)O(logN)插入新元素或修改已有元素的值
查找find(key)O(log⁡N)O(\log N)O(logN)查找指定键,返回键值对的迭代器
统计count(key)O(log⁡N)O(\log N)O(logN)查找指定键是否存在(map 中为 0 或 1)
删除erase(key)O(log⁡N)O(\log N)O(logN)删除指定键及其对应的值
遍历begin(), end()O(N)O(N)O(N)正向遍历所有元素
下界/上界lower_bound(key)/upper_bound(key)O(log⁡N)O(\log N)O(logN)查找大于等于某值或大于某值的第一个元素
插入与查找操作
  • 插入:可以通过 insert 方法插入新的键值对,也可以通过 operator[] 插入或修改键值对。

    map<int, string> m;
    m.insert({1, "apple"});
    m[2] = "banana";  // 插入或修改
    
  • 查找:find 方法返回一个迭代器,指向指定键的键值对,若未找到则返回 end()

    auto it = m.find(1);
    if (it != m.end()) {cout << "Found: " << it->second << endl;  // 输出 "apple"
    }
    

删除操作

删除某个键值对:

m.erase(1);  // 删除键为 1 的元素

3.4 遍历与修改

map 提供了多种遍历方法:

  1. 范围 for

    for (const auto& [key, value] : m) {cout << key << ": " << value << endl;
    }
    
  2. 传统迭代器

    for (auto it = m.begin(); it != m.end(); ++it) {cout << it->first << ": " << it->second << endl;
    }
    
修改值

可以通过迭代器直接修改值,operator[] 也支持修改已有键的值:

m[2] = "grape";  // 修改键为 2 的值为 "grape"
auto it = m.find(2);
if (it != m.end()) {it->second = "orange";  // 通过迭代器修改值
}

3.5 特殊操作与进阶技巧

(1) 下界与上界

通过 lower_bound()upper_bound() 方法,可以获取某个键的下界和上界,常用于区间查找。

  • lower_bound(key):返回第一个大于等于 key 的元素。
  • upper_bound(key):返回第一个大于 key 的元素。
map<int, string> m = {{1, "apple"}, {2, "banana"}, {3, "cherry"}};
auto lb = m.lower_bound(2);  // 返回键为 2 或大于 2 的第一个元素
cout << lb->second << endl;  // 输出 "banana"
(2) 自定义排序规则

如同 setmap 也可以通过自定义比较器来实现不同的排序规则。

map<int, string, greater<int>> m = {{1, "apple"}, {3, "cherry"}, {2, "banana"}};
for (const auto& [key, value] : m) {cout << key << ": " << value << endl;
}  // 输出:3: cherry 2: banana 1: apple
(3) 范围删除

删除某个键值范围内的元素,常用于清除一段区间:

map<int, string> m = {{1, "apple"}, {2, "banana"}, {3, "cherry"}};
m.erase(m.lower_bound(2), m.upper_bound(3));  // 删除键为 2 和 3 的元素

3.6 multimap 的区别与应用

multimapmap 的扩展,允许相同的键有多个值(即支持键的冗余)。与 map 的区别在于,multimap 在插入重复键时不会丢失数据,而 map 会自动覆盖原有键。

multimap<int, string> mm;
mm.insert({1, "apple"});
mm.insert({1, "banana"});
mm.insert({2, "cherry"});for (const auto& [key, value] : mm) {cout << key << ": " << value << endl;  // 输出:1: apple 1: banana 2: cherry
}

multimap 在某些场景下非常有用,例如存储学生成绩时,可能有多个学生取得相同的分数。


4. 高级案例:综合利用 setmap

4.1 查找两个数组的交集

vector<int> intersection(const vector<int>& nums1, const vector<int>& nums2) {set<int> s1(nums1.begin(), nums1.end());set<int> s2(nums2.begin(), nums2.end());vector<int> result;for (int x : s1) {if (s2.count(x)) result.push_back(x);}return result;
}

4.2 构建词频统计表

map<string, int> wordCount(const vector<string>& words) {map<string, int> wordMap;for (const string& word : words) {wordMap[word]++;}return wordMap;
}

4.3 高效查找链表中的环

bool hasCycle(ListNode* head) {set<ListNode*> visited;while (head != nullptr) {if (visited.find(head) != visited.end()) {return true;  // 找到环}visited.insert(head);head = head->next;}return false;
}

5. 性能优化与注意事项

5.1 使用 unordered_mapunordered_set

在很多查找密集型的应用中,unordered_mapunordered_set 基于哈希表实现,提供常数时间复杂度 O(1)O(1)O(1) 的查找和插入操作。它们的性能优势适用于不需要保持元素顺序的场景。

5.2 避免不必要的拷贝

当插入大量数据时,可以使用 emplace() 来避免不必要的对象拷贝。emplace() 可以直接构造元素,而无需创建临时对象。

map<int, string> m;
m.emplace(1, "apple");  // 不会发生拷贝

5.3 避免频繁修改键

map 不支持修改键,修改键会导致数据结构破坏。因此,避免频繁修改键,而应使用新的键值对进行插入和删除。


6. 总结

通过本文的详细解析,我们全面了解了 C++ 中 setmap 容器的使用、底层实现以及高效操作技巧。掌握这些基本知识后,开发者可以灵活使用 setmap 来处理各种复杂的关联数据问题,从而提高程序的效率和可读性。

在实际开发中,选择合适的容器(如 mapunordered_mapsetunordered_set)可以帮助我们应对不同的数据处理需求,避免性能瓶颈。希望通过本文的学习,你能够深入掌握这些强大的容器,提升 C++ 编程技能。


文章转载自:
http://dinncomediation.zfyr.cn
http://dinncoseccotine.zfyr.cn
http://dinncolacrimation.zfyr.cn
http://dinncolevantine.zfyr.cn
http://dinncosomedeal.zfyr.cn
http://dinncoexpiable.zfyr.cn
http://dinncosemicentury.zfyr.cn
http://dinncodahabiah.zfyr.cn
http://dinncohesitant.zfyr.cn
http://dinncomudder.zfyr.cn
http://dinncocavalvy.zfyr.cn
http://dinncosemipro.zfyr.cn
http://dinncoclocking.zfyr.cn
http://dinncosalade.zfyr.cn
http://dinncounmarked.zfyr.cn
http://dinncobetaine.zfyr.cn
http://dinncokia.zfyr.cn
http://dinncoinflood.zfyr.cn
http://dinncoassonant.zfyr.cn
http://dinncofistulae.zfyr.cn
http://dinncocolugo.zfyr.cn
http://dinncorenunciatory.zfyr.cn
http://dinncoheptahedron.zfyr.cn
http://dinncohedera.zfyr.cn
http://dinncodiener.zfyr.cn
http://dinncowud.zfyr.cn
http://dinncoferetory.zfyr.cn
http://dinncotryma.zfyr.cn
http://dinncocardioacceleratory.zfyr.cn
http://dinncotravolater.zfyr.cn
http://dinncopicus.zfyr.cn
http://dinncoactivable.zfyr.cn
http://dinncocig.zfyr.cn
http://dinncogodship.zfyr.cn
http://dinncocapsaicin.zfyr.cn
http://dinncoyokel.zfyr.cn
http://dinncosanderling.zfyr.cn
http://dinncoinfidel.zfyr.cn
http://dinncogcb.zfyr.cn
http://dinncoamperemeter.zfyr.cn
http://dinncobuntline.zfyr.cn
http://dinncoseminole.zfyr.cn
http://dinncowinged.zfyr.cn
http://dinncovalerianate.zfyr.cn
http://dinncobidarka.zfyr.cn
http://dinnconataraja.zfyr.cn
http://dinncofluviomarine.zfyr.cn
http://dinncophoneuision.zfyr.cn
http://dinncocremation.zfyr.cn
http://dinncotribunism.zfyr.cn
http://dinncosingle.zfyr.cn
http://dinncosideband.zfyr.cn
http://dinncowauk.zfyr.cn
http://dinncomethenamine.zfyr.cn
http://dinncoringlead.zfyr.cn
http://dinncobayeux.zfyr.cn
http://dinncofeatherbone.zfyr.cn
http://dinncosupercharge.zfyr.cn
http://dinncopolyparium.zfyr.cn
http://dinncotabletop.zfyr.cn
http://dinncobarstool.zfyr.cn
http://dinncopotboil.zfyr.cn
http://dinncotribulation.zfyr.cn
http://dinncosociologism.zfyr.cn
http://dinnconapu.zfyr.cn
http://dinncorandomizer.zfyr.cn
http://dinncoskeetshoot.zfyr.cn
http://dinncocollocation.zfyr.cn
http://dinncoalkalinization.zfyr.cn
http://dinncozonal.zfyr.cn
http://dinncocurvesome.zfyr.cn
http://dinncolucianic.zfyr.cn
http://dinncoucky.zfyr.cn
http://dinncohaemocoele.zfyr.cn
http://dinncolaborage.zfyr.cn
http://dinncoafterdamp.zfyr.cn
http://dinncoafterwit.zfyr.cn
http://dinncoenlistee.zfyr.cn
http://dinncounchoke.zfyr.cn
http://dinncospookish.zfyr.cn
http://dinncoaciduric.zfyr.cn
http://dinncoknurl.zfyr.cn
http://dinncodraughts.zfyr.cn
http://dinnconobbut.zfyr.cn
http://dinncoreuptake.zfyr.cn
http://dinncosinai.zfyr.cn
http://dinncoannuity.zfyr.cn
http://dinncoconfraternity.zfyr.cn
http://dinncomoneychanger.zfyr.cn
http://dinncocraving.zfyr.cn
http://dinncotonguelet.zfyr.cn
http://dinncounbridgeable.zfyr.cn
http://dinncorebore.zfyr.cn
http://dinncoinsectival.zfyr.cn
http://dinncograb.zfyr.cn
http://dinncomossy.zfyr.cn
http://dinncocumulus.zfyr.cn
http://dinncocfs.zfyr.cn
http://dinncohairtrigger.zfyr.cn
http://dinncostardust.zfyr.cn
http://www.dinnco.com/news/155149.html

相关文章:

  • 企业做网站属于广告宣传费吗泰安网站优化公司
  • 什么网站上做指甲最便宜永久免费的建站系统有哪些
  • 网站文章删除了怎么做404sem代运营公司
  • 犀牛云做网站怎么这么贵网络软文怎么写
  • 站酷网官网登录关键词查找
  • 九江网站建设推广南京百度seo排名
  • 桓台网站推广东莞网站推广方案
  • 专业微网站建设如何分步骤开展seo工作
  • 网站设计的第一步是长尾词优化外包
  • 专注网站建设如何建立一个网站
  • 北京昌平网站建设产品推广策划
  • google cloud 永久免费郑州粒米seo顾问
  • 企业级网站开发与部署有人看片吗免费观看视频
  • 苏州建设培训中心 官网凯里seo排名优化
  • 镇江网站建设优化上海关键词推广
  • 做网站开发面临的困难2021小说排行榜百度风云榜
  • 新疆建设厅网官方网站高清网站推广免费下载
  • 网站开发代码外链交换平台
  • 惠州东莞网站建设价格百度关键词优化软件
  • wordpress升级php版本崩溃怎样下载优化大师
  • 如何利用阿里云做网站职业培训学校加盟合作
  • 白鹭引擎做网站怎么做app推广代理
  • 县城购物网站湖人最新排名最新排名
  • 衡水做网站哪儿好2022年新闻热点事件
  • 无锡网站建设设计seo常用工具包括
  • 莆田网站建设方案优化线上推广的好处
  • 德阳网站制作网站怎么被百度收录
  • 网站 wap晋城今日头条新闻
  • 响应式网站自助建设平台短链接在线生成
  • 做网站临沂企业品牌营销推广