佛山网站制作建设,吉林省建设厅官方网站办事指南,同一服务器建两个wordpress,怎么做页眉摘要#xff1a;本文深入探讨 C 提高编程中的模板编程与标准模板库#xff08;STL#xff09;相关内容。详细阐述模板编程中函数模板和类模板的概念、语法、特性及应用案例#xff1b;对 STL 的诞生背景、基本概念、六大组件进行剖析#xff0c;并对常用容器、函数对象、常…摘要本文深入探讨 C 提高编程中的模板编程与标准模板库STL相关内容。详细阐述模板编程中函数模板和类模板的概念、语法、特性及应用案例对 STL 的诞生背景、基本概念、六大组件进行剖析并对常用容器、函数对象、常用算法展开全面讲解旨在为 C 开发者提供系统且深入的技术参考助力其提升 C 编程能力与代码质量。 一、引言 C 作为一种强大且应用广泛的编程语言其提高编程部分涵盖的模板编程和 STL为开发者提供了高度的代码复用性和强大的数据处理能力。模板编程实现了泛型编程使代码能够独立于具体数据类型STL 则是一套精心设计的模板库包含容器、算法和迭代器等组件极大地简化了复杂数据结构和算法的实现。深入理解和掌握这些内容对提升 C 编程水平至关重要。
二、模板编程
一模板概念 模板是 C 泛型编程的基础它允许将类型作为参数传递给函数或类从而实现代码的复用。通过模板算法可以独立于具体的数据类型提高了代码的通用性和可维护性。其核心基于类型参数化使得同一套代码能够处理不同类型的数据减少了重复代码的编写。
二函数模板
语法 函数模板以template typename T或template class T的形式声明模板参数其中typename和class含义相同用于指定类型参数。在函数定义中使用该模板参数来表示函数的参数类型或返回值类型。例如
template typename T
T add(T a, T b) {return a b;
}注意事项 类型推导存在一定规则编译器优先匹配精确类型当无法自动推导模板参数类型时需要开发者显式指定。同时在模板参数匹配时普通函数的优先级高于函数模板。案例 实现一个通用的数组元素交换函数
template typename T
void swapArray(T arr[], int i, int j) {T temp arr[i];arr[i] arr[j];arr[j] temp;
}此函数可用于交换不同类型数组中的元素展示了函数模板的便捷性。再如编写通用的最大值获取函数
template typename T
T getMax(T a, T b) {return (a b)? a : b;
}体现了函数模板对不同数据类型的适用性。 4. 与普通函数区别 函数模板具有类型通用性能够处理多种数据类型而普通函数针对特定类型编写。在编译时函数模板会根据实际传入的参数类型进行实例化生成对应类型的函数代码普通函数则直接进行编译。 5. 调用规则 自动类型推导编译器根据传入函数的参数自动确定模板参数的类型如int result add(3, 5);。显式指定类型开发者明确指定模板参数类型例如addint(3, 5)。 6. 局限性 对于一些特定类型的操作如位运算等函数模板可能需要特殊处理。此外大量实例化可能导致代码体积膨胀占用更多的存储空间。
三类模板
语法 类模板的声明形式为template typename T class ClassName {...} 在类内部可以使用模板参数T定义成员变量和成员函数。成员函数既可以在类内直接定义也可以在类外实现。类外实现成员函数时语法如下
template typename T
return_type ClassNameT::function_name(parameters) {...}与函数模板区别 类模板作用于整个类及其对象实例而函数模板仅作用于函数。类模板可包含多种成员如数据成员、成员函数等结构更为复杂涉及到类的封装、继承和多态等特性与模板的结合。成员函数创建时机 类模板的成员函数在调用时才会进行实例化生成对应类型的函数代码。提前声明成员函数并不立即实例化这种延迟实例化机制可以节省编译时间只有在实际使用时才进行实例化操作。对象做函数参数 按值传递将对象复制一份传递给函数这种方式开销较大适用于小对象或无需保留原对象状态的情况。例如
template typename T
void printObjectByValue(T obj) {std::cout obj std::endl;
}引用传递传递对象的引用给函数高效且能修改对象内容同时避免了拷贝构造的开销。如
template typename T
void modifyObjectByReference(T obj) {// 修改obj操作
}指针传递通过指针传递对象具有较高的灵活性可实现多态等特性但需要注意指针的有效性。示例如下
template typename T
void operateOnObjectByPointer(T* ptr) {// 通过指针操作对象
}与继承 类模板继承普通类子类模板可以继承普通类的属性和方法并在此基础上添加模板特性。例如普通类实现了一些通用的功能类模板继承后可以针对不同类型进行定制化扩展。 类模板之间继承子类模板可以继承父类模板的参数及功能并且可以进一步扩展新的模板参数或成员。在继承过程中需要注意模板参数的传递和处理确保继承关系的正确性和代码的可读性。成员函数类外实现 类模板成员函数类外实现时需遵循特定语法明确指定模板参数。同时要注意作用域的限定确保编译器能够正确识别和编译。例如
template typename T
class MyClass {
public:void function();
};template typename T
void MyClassT::function() {// 函数实现代码
}分文件编写 头文件主要用于声明类模板及其成员函数为其他文件提供接口。在头文件中应包含必要的模板声明和类的前置声明确保其他源文件能够正确引用。 源文件实现类模板的成员函数。在编译时需要正确处理模板实例化问题常见的解决方法包括显式实例化或在源文件中包含头文件等方式以避免编译链接错误。与友元 普通函数友元授予普通函数访问类模板私有成员的权限通过在类模板中声明友元函数来实现。例如
template typename T
class MyClass {friend void friendFunction(MyClassT obj);
private:T data;
};template typename T
void friendFunction(MyClassT obj) {// 访问obj的私有成员data
}函数模板友元函数模板可以作为类模板的友元实现特定功能的交互。在声明和实现时需要注意模板参数的匹配和作用域的处理。 类模板友元一个类模板可以作为另一个类模板的友元从而实现两个类模板之间的数据共享或功能协作。在这种情况下需要仔细设计友元关系确保代码的安全性和可维护性。 9. 案例 实现通用的链表类模板
template typename T
class LinkedList {
private:struct Node {T data;Node* next;Node(const T value) : data(value), next(nullptr) {}};Node* head;
public:LinkedList() : head(nullptr) {}// 链表操作函数如插入、删除、遍历等
};该类模板可用于管理不同类型数据的链表节点实现链表的基本操作。再如构建通用的矩阵类模板
template typename T
class Matrix {
private:int rows;int cols;T** elements;
public:Matrix(int r, int c) : rows(r), cols(c) {elements new T*[rows];for (int i 0; i rows; i) {elements[i] new T[cols];}}// 矩阵运算函数如加法、乘法等
};实现矩阵的存储和运算功能展示类模板在复杂数据结构中的应用。
三、STL 初识
一STL 诞生 STL 起源于惠普实验室由 Alexander Stepanov 等人开发。其设计目标是提供一套通用、高效、可复用的模板库旨在简化 C 编程中数据结构和算法的实现减少开发者的重复劳动提高软件开发的效率和质量。
二基本概念
容器用于存储数据是 STL 的重要组成部分。类似于不同的数据结构如数组、链表、集合等提供了不同的存储和访问方式满足各种应用场景对数据存储的需求。算法对容器中的数据进行操作涵盖排序、查找、遍历等多种操作。STL 算法具有高度的通用性能够处理不同类型的容器数据通过迭代器与容器进行交互。迭代器类似于指针用于访问容器中的元素为容器提供了统一的访问接口。迭代器的存在使得算法可以不依赖于具体容器的实现细节实现了容器和算法的分离与通用化。
三六大组件
容器 顺序容器如vector、list、deque等它们按照元素的插入顺序存储元素。vector是动态数组具有连续的内存存储支持随机访问适合频繁访问元素的场景list是双向链表不支持随机访问但在频繁插入和删除元素时效率较高deque是双端队列允许在两端进行高效的插入和删除操作兼具vector和list的部分特性。 关联容器包括set、map等这些容器根据特定的键值关系存储元素。set中的元素唯一且自动排序常用于快速查找和去重map以键值对的形式存储数据键唯一且自动排序可用于高效的键值查找。算法 分为多种类型如遍历算法用于逐个访问容器中的元素查找算法用于在容器中寻找特定元素或满足条件的元素排序算法用于对容器中的元素进行排序等。不同的算法针对不同的应用需求提供了丰富的数据处理功能。迭代器 输入迭代器只读支持单遍扫描容器用于从容器中读取数据。 输出迭代器只写用于向容器中写入数据。 前向迭代器支持读写操作只能单遍扫描容器按顺序向前访问元素。 双向迭代器支持读写操作可在容器中前后移动适用于需要双向遍历的场景。 随机访问迭代器支持读写操作并且可以随机访问容器中的元素具有类似指针算术运算的能力如vector的迭代器。仿函数 即函数对象通过类重载()运算符实现。仿函数可以作为算法的参数用于定制算法的操作逻辑。例如在排序算法中可以使用自定义的仿函数作为比较函数实现特定的排序规则。适配器 容器适配器如stack、queue等它们改变了其他容器的接口使其符合特定的数据结构特性。stack遵循后进先出原则queue遵循先进先出原则它们底层通常基于其他容器如deque、vector等实现。 迭代器适配器如reverse_iterator它改变了迭代器的遍历方向使算法可以反向遍历容器。分配器 负责容器的内存分配与释放默认情况下使用系统的内存分配机制。开发者也可以自定义分配器以满足特定的内存管理需求如提高内存分配效率、实现内存池等功能。
四容器、算法、迭代器 迭代器在容器和算法之间起到桥梁作用。算法通过迭代器来访问和操作容器中的元素使得算法能够独立于具体容器的实现。容器提供了数据的存储结构而算法基于迭代器对容器中的数据进行处理这种设计模式实现了容器和算法的分离与高度复用提高了代码的可维护性和扩展性。
五容器算法迭代器初识
vector 存放内置数据类型 语法定义vectorint v;创建一个存储int类型数据的vector容器。插入元素使用v.push_back(5);访问元素可以通过v[0]或v.at(0)at函数带有边界检查。 动态内存管理vector会根据元素的插入自动扩展内存采用连续内存存储方式这使得元素访问效率较高同时也支持随机访问。vector 存放自定义数据类型 适配自定义数据类型需要实现合适的构造函数、拷贝构造函数、赋值运算符等以满足vector对元素的存储和操作要求。例如如果自定义类没有正确实现拷贝构造函数在vector进行元素拷贝如插入、删除等操作可能涉及拷贝时可能会出现错误。 操作可以对存放自定义数据类型的vector进行排序、查找等操作但通常需要定制比较函数等以确保操作符合自定义类型的逻辑。vector 容器嵌套容器 应用场景常用于表示二维数据结构如二维数组表示矩阵、表格等。例如vectorvectorint matrix;可以表示一个整数矩阵。 内存布局与访问外层vector管理内层vector的指针内存并非完全连续。访问元素时需要通过两层索引如matrix[i][j]来访问第i行第j列的元素。
四、STL - 常用容器
一string 容器
基本概念 string容器用于动态存储字符串它自动管理内存相比 C 风格字符串更加安全和易用。其内部采用类似vector的结构来存储字符数据提供了丰富的操作接口来处理字符串。构造函数 默认构造string s;创建一个空字符串。 拷贝构造string s1(s);将已有字符串s复制给s1。 初始化列表构造string s2(hello);使用字符串字面量初始化s2。赋值操作 重载运算符s world;直接将字符串字面量赋值给s。 assign 函数提供多种赋值方式如s.assign(new string, 3);表示取new string的前 3 个字符赋值给s。字符串拼接 重载运算符s s !;将!拼接到字符串s后面。 append 函数s.append( append);可指定位置和长度进行字符串拼接如s.append( append, 3);表示拼接 app。查找和替换 find 函数size_t pos s.find(ll);用于查找子串ll在字符串s中的位置。 replace 函数s.replace(pos, 2, XX);将从位置pos开始长度为 2 的子串替换为XX。字符串比较 重载比较运算符如if (s1 s2)通过重载的运算符按字典序比较两个字符串。 比较规则从左到右逐个字符比较 ASCII 码值若所有字符都相同则字符串相等否则根据第一个不同字符的 ASCII 码大小确定字符串的大小关系。字符存取 重载[]运算符char c s[0];直接访问字符串s的第一个字符。 at 函数char c1 s.at(0);与[]类似但at函数带有越界检查当访问越界时会抛出异常。插入和删除 insert 函数s.insert(1, x);在字符串s的索引位置 1 处插入字符x。 erase 函数s.erase(1, 2);删除字符串s从索引位置 1 开始长度为 2 的字符。子串 substr 函数string sub s.substr(1, 3);获取字符串s从索引位置 1 开始长度为 3 的子串。 应用场景常用于文本解析、字符串截取等操作例如从一个完整的文件名中截取文件扩展名。
二vector 容器 resize 和 reserve 函数resize函数用于改变vector中元素的个数可指定初始值例如v.resize(10, 0)将vector的大小调整为 10新添加的元素初始值为 0reserve函数用于调整vector的容量不改变元素个数它可以提前分配内存减少内存重新分配的开销如v.reserve(20)表示为v预留能容纳 20 个元素的内存空间。 5. 插入和删除 push_back 函数在vector的尾部插入元素v.push_back(6);将元素 6 添加到vector的末尾。 insert 函数可以在指定位置插入元素v.insert(v.begin() 1, 7);表示在vector的第二个位置索引为 1插入元素 7。 pop_back 函数删除vector尾部的元素v.pop_back();移除vector的最后一个元素。 erase 函数删除指定位置或范围的元素v.erase(v.begin() 2);删除vector中索引为 2 的元素v.erase(v.begin() 1, v.begin() 3);则删除从索引 1 到索引 2不包括索引 3的元素。 6. 数据存取 重载[]运算符通过v[0]可以直接访问vector中索引为 0 的元素。 at 函数v.at(0)与[]运算符功能类似但at函数会进行越界检查若索引越界会抛出异常而[]运算符在越界时行为未定义。 7. 互换容器 swap 函数swap(v, v1);用于交换两个vector容器的内容。这在某些场景下可以用于内存优化例如当需要快速交换两个vector的元素时使用swap函数比逐个元素交换效率更高。 8. 预留空间 reserve 函数如前面所述reserve函数可以提前为vector分配内存避免在插入元素时频繁进行内存重新分配。例如当已知需要向vector中插入大量元素时提前调用reserve函数可以显著提高程序性能。
三deque 容器
基本概念 deque双端队列允许在队列的两端进行插入和删除操作与vector相比它在头部和尾部的操作更加高效。其内存结构是分段连续的通过映射表来管理各个内存块这使得它在需要频繁在两端操作元素的场景中表现出色。构造函数 默认构造dequeint d;创建一个空的deque容器。 带参数构造dequeint d1(5, 8);创建一个包含 5 个元素每个元素值为 8 的deque。赋值操作 重载运算符d d1;将d1的内容复制给d。 assign 函数d.assign(4, 9);用 4 个值为 9 的元素替换d原来的内容。大小操作 size 函数用于获取deque中元素的个数int s d.size();。 empty 函数判断deque是否为空bool isEmpty d.empty();。插入和删除 push_front 函数在deque的头部插入元素d.push_front(1);将元素 1 添加到deque的开头。 push_back 函数在deque的尾部插入元素d.push_back(2);将元素 2 添加到deque的末尾。 pop_front 函数删除deque头部的元素d.pop_front();移除deque的第一个元素。 pop_back 函数删除deque尾部的元素d.pop_back();移除deque的最后一个元素。 insert 函数可以在指定位置插入元素d.insert(d.begin() 1, 3);在deque的第二个位置索引为 1插入元素 3。 erase 函数删除指定位置或范围的元素d.erase(d.begin() 2);删除deque中索引为 2 的元素d.erase(d.begin() 1, d.begin() 3);删除从索引 1 到索引 2不包括索引 3的元素。数据存取 重载[]运算符通过d[0]可以直接访问deque中索引为 0 的元素。 at 函数d.at(0)与[]运算符功能类似但at函数会进行越界检查若索引越界会抛出异常而[]运算符在越界时行为未定义。排序 deque可以使用sort算法进行排序例如sort(d.begin(), d.end());。如果需要按照特定的规则进行排序可以自定义比较函数将其作为sort算法的参数实现对deque中元素的定制化排序。
四案例 - 评委打分
案例描述 该案例模拟比赛评分的场景在比赛中多位评委为选手打分为了保证评分的公正性需要去除一个最高分和一个最低分然后计算剩余分数的平均值以此作为选手的最终得分。此案例涉及到数据的存储、处理和结果的输出等环节通过使用 STL 容器和算法可以高效地实现。实现步骤 数据录入使用合适的容器如vector来存储评委的分数。例如vectordouble scores;然后通过循环等方式将评委的分数依次录入到容器中如scores.push_back(score);其中score为从输入获取的评委分数。 数据处理首先查找容器中的最高分和最低分可以使用max_element和min_element算法如auto maxIt max_element(scores.begin(), scores.end());和auto minIt min_element(scores.begin(), scores.end());。然后从容器中删除最高分和最低分scores.erase(maxIt);和scores.erase(minIt);。最后计算剩余分数的平均值通过累加剩余分数并除以剩余分数的个数来实现如double sum accumulate(scores.begin(), scores.end(), 0.0); double average sum / scores.size();。 结果输出将计算得到的选手最终得分输出显示如cout 选手的最终得分是: average endl;。
五stack 容器
基本概念 stack是一种遵循后进先出LIFO原则的数据结构。在实际应用中常用于函数调用栈的模拟、表达式求值如后缀表达式计算等场景。它底层通常基于其他容器如deque、vector实现通过对这些容器的接口进行封装使其符合栈的特性。常用接口 push 函数用于将元素压入栈顶s.push(5);将元素 5 添加到栈s的顶部。 pop 函数用于移除栈顶的元素s.pop();删除栈s的栈顶元素。 top 函数用于获取栈顶的元素但不删除该元素int topVal s.top();获取栈s的栈顶元素值。 size 函数用于获取栈中元素的个数int stackSize s.size();。 empty 函数用于判断栈是否为空bool isStackEmpty s.empty();。
六queue 容器
基本概念 queue是一种遵循先进先出FIFO原则的数据结构。在实际应用中常用于消息队列、任务队列等场景例如在多线程编程中任务可以按照先进先出的顺序放入任务队列然后由线程依次取出执行。它底层也通常基于其他容器如deque、list实现通过封装容器接口来满足队列的特性。常用接口 push 函数用于将元素插入队尾q.push(3);将元素 3 添加到队列q的末尾。 pop 函数用于移除队头的元素q.pop();删除队列q的队头元素。 front 函数用于获取队头的元素但不删除该元素int frontVal q.front();获取队列q的队头元素值。 back 函数用于获取队尾的元素但不删除该元素int backVal q.back();获取队列q的队尾元素值。 size 函数用于获取队列中元素的个数int queueSize q.size();。 empty 函数用于判断队列是否为空bool isQueueEmpty q.empty();。
七list 容器
基本概念 list是一个双向链表它的每个节点都包含一个指向前驱节点和一个指向后继节点的指针。由于其内存不是连续的因此不支持随机访问但是在频繁进行插入和删除操作时具有较高的效率。适用于需要频繁插入和删除元素而对随机访问需求较少的场景如实现一个动态的任务列表任务可以随时添加或删除。构造函数 默认构造listint l;创建一个空的list容器。 带参数构造listint l1(4, 7);创建一个包含 4 个元素每个元素值为 7 的list。赋值操作 重载运算符l l1;将l1的内容复制给l。 assign 函数l.assign(3, 8);用 3 个值为 8 的元素替换l原来的内容。插入和删除 push_front 函数在list的头部插入元素l.push_front(1);将元素 1 添加到list的开头。 push_back 函数在list的尾部插入元素l.push_back(2);将元素 2 添加到list的末尾。 pop_front 函数删除list头部的元素l.pop_front();移除list的第一个元素。 pop_back 函数删除list尾部的元素l.pop_back();移除list的最后一个元素。 insert 函数可以在指定位置插入元素l.insert(l.begin(), 3);在list的开头插入元素 3。 erase 函数删除指定位置或范围的元素l.erase(l.begin() 1);删除list中索引为 1 的元素l.erase(l.begin() 1, l.begin() 3);删除从索引 1 到索引 2不包括索引 3的元素。数据存取 由于list不支持随机访问因此不能像vector那样通过下标直接访问元素。需要通过迭代器来遍历list例如
for (auto it l.begin(); it ! l.end(); it) {int val *it;// 对val进行操作
}排序 list可以使用sort函数进行排序l.sort();。同样如果需要按照特定的规则进行排序可以自定义比较函数将其作为sort函数的参数实现对list中元素的定制化排序。
八set/multiset 容器
基本概念 set是一个集合容器其中的元素唯一且自动排序底层通常使用红黑树实现。这种数据结构使得在set中查找元素的效率较高适用于需要快速查找和去重的场景例如统计一篇文章中不重复的单词。 multiset与set类似也是基于红黑树实现但其允许元素重复适用于需要统计元素出现次数等场景比如统计一个班级学生成绩中各个分数的出现次数。构造和赋值 默认构造setint s;和multisetint ms;分别创建一个空的set和multiset容器。 拷贝构造setint s1(s);和multisetint ms1(ms);分别将已有的set和multiset容器进行复制。 赋值运算符重载s s1;和ms ms1;分别实现set和multiset容器之间的赋值操作。大小和交换 size 函数用于获取set或multiset中元素的个数int setSize s.size();和int multisetSize ms.size();。 empty 函数用于判断set或multiset是否为空bool isSetEmpty s.empty();和bool isMultisetEmpty ms.empty();。 swap 函数swap(s, s1);和swap(ms, ms1);分别用于交换两个set或两个multiset容器的内容。插入和删除 insert 函数用于向set或multiset中插入元素s.insert(5);和ms.insert(5);分别向set和multiset中插入元素 5。在set中如果插入的元素已经存在则插入操作不会生效而在multiset中相同元素可以多次插入。 erase 函数用于删除指定的元素或范围s.erase(s.find(5));和ms.erase(ms.find(5));分别删除set和multiset中值为 5 的元素在multiset中会删除所有值为 5 的元素s.erase(s.begin(), s.end());和ms.erase(ms.begin(), ms.end());分别删除set和multiset中的所有元素。查找和统计 find 函数用于查找元素setint::iterator it s.find(5);和multisetint::iterator mit ms.find(5);分别在set和multiset中查找值为 5 的元素并返回指向该元素的迭代器如果元素不存在则返回end()迭代器。 count 函数在multiset中用于统计元素出现的次数int countVal ms.count(5);统计multiset中值为 5 的元素的个数在set中count函数的返回值只能是 0 或 1因为set中元素唯一。set 和 multiset 区别 元素唯一性set中的元素是唯一的不允许重复而multiset允许元素重复出现。 应用场景set主要用于去重和快速查找唯一元素multiset则更适合用于统计元素的出现次数等场景。pair 对组创建 语法可以使用make_pair函数或直接初始化的方式创建pair对组。例如pairint, string p make_pair(1, one);或pairint, string p1(2, two);。pair对组常用于在set和multimap等关联容器中存储键值对。set 容器排序 set容器默认按照元素的升序进行排序这是由其底层的红黑树结构和比较函数决定的。如果需要改变排序规则可以自定义比较函数。例如
struct Compare {bool operator()(int a, int b) {return a b; // 降序排序}
};
setint, Compare s2;通过这种方式创建的set容器s2将按照降序对元素进行排序。
九map/multimap 容器
基本概念 map是一个以键值对key - value形式存储数据的关联容器其中键是唯一的并且会自动按照键的顺序进行排序底层通常使用红黑树实现。这种结构使得通过键查找值的效率很高适用于需要快速查找和存储键值对数据的场景比如学生成绩管理系统中以学生学号为键成绩为值进行存储和查询。 multimap与map类似也是存储键值对但它允许键重复适用于一个键可以对应多个值的场景例如一个单词在文章中可能出现多次需要记录每次出现的位置就可以使用multimap以单词为键位置为值进行存储。构造和赋值 默认构造mapint, string m;和multimapint, string mm;分别创建一个空的map和multimap容器。 拷贝构造mapint, string m1(m);和multimapint, string mm1(mm);分别将已有的map和multimap容器进行复制。 赋值运算符重载m m1;和mm mm1;分别实现map和multimap容器之间的赋值操作。大小和交换 size 函数用于获取map或multimap中键值对的个数int mapSize m.size();和int multimapSize mm.size();。 empty 函数用于判断map或multimap是否为空bool isMapEmpty m.empty();和bool isMultimapEmpty mm.empty();。 swap 函数swap(m, m1);和swap(mm, mm1);分别用于交换两个map或两个multimap容器的内容。
插入和删除 insert 函数有多种插入方式。例如使用m.insert(make_pair(1, one));或m.insert(std::pairint, std::string(1, one)); 向map容器m中插入键值对。在multimap中插入方式类似如mm.insert(make_pair(1, value1));由于multimap允许键重复相同键的键值对会依次插入。 erase 函数在map中m.erase(1);删除键为 1 的键值对m.erase(m.find(1));通过找到键 1 对应的迭代器来删除键值对。在multimap中mm.erase(1);会删除所有键为 1 的键值对mm.erase(mm.find(1));则只删除找到的第一个键为 1 的键值对。查找和统计 find 函数mapint, string::iterator it m.find(1);在map m中查找键为 1 的键值对如果找到it指向该键值对否则it等于m.end()。在multimap中类似multimapint, string::iterator mit mm.find(1);用于查找键为 1 的键值对。 count 函数在map中m.count(1)返回值只能是 0 或 1因为键唯一。在multimap中mm.count(1)用于统计键为 1 的键值对出现的次数若存在多个键为 1 的键值对会返回相应的数量。map 容器排序 map默认根据键的升序进行排序这基于其底层红黑树结构和默认比较函数。若要改变排序规则可自定义比较函数。如
struct KeyCompare {bool operator()(const int a, const int b) {return a b; // 实现键的降序排序}
};
mapint, string, KeyCompare m2;如此创建的map m2会按照键的降序对键值对进行排序。 7. 案例 - 员工分组 案例描述假设有一个公司需要将员工按照部门进行分组管理。每个员工有唯一的工号和所属部门信息要求能够高效地存储员工信息并能根据部门快速查询该部门的所有员工。此案例体现了map或multimap在实际场景中的应用。 实现步骤 定义员工数据结构
struct Employee {int id;std::string name;std::string department;Employee(int i, const std::string n, const std::string d) : id(i), name(n), department(d) {}
};数据录入使用multimap来存储员工信息因为一个部门可能有多个员工。例如
multimapstd::string, Employee employeeMap;
Employee emp1(1, Alice, HR);
Employee emp2(2, Bob, Engineering);
employeeMap.insert(make_pair(HR, emp1));
employeeMap.insert(make_pair(Engineering, emp2));分组操作根据部门对员工进行分组。例如要获取 “HR” 部门的所有员工可以通过查找键 “HR” 来遍历该部门的所有员工
auto range employeeMap.equal_range(HR);
for (auto it range.first; it ! range.second; it) {std::cout Employee ID: it-second.id , Name: it-second.name std::endl;
}结果输出将分组后的员工信息按照一定格式输出如上述代码中将 “HR” 部门的员工工号和姓名输出显示方便查看和管理。
五、STL - 函数对象
一函数对象
概念 函数对象是一种可调用对象通过在类中重载()运算符来实现。它与普通函数的区别在于函数对象可以携带状态即它可以包含成员变量来存储额外的信息而普通函数通常不具备这种能力。函数对象可以像普通函数一样被调用同时又具有类的特性能够进行数据封装和继承等操作。使用 在 STL 算法中函数对象常作为参数传递用于定制算法的操作逻辑。例如在sort算法中可以使用自定义的函数对象作为比较函数实现特定的排序规则。假设有一个自定义的类MyComparator
class MyComparator {
public:bool operator()(const int a, const int b) {return a b; // 实现降序比较}
};在使用sort函数时可以这样调用
vectorint numbers {1, 3, 2, 4, 5};
sort(numbers.begin(), numbers.end(), MyComparator());这里MyComparator()作为比较函数传递给sort算法使得numbers向量按照降序排列。
二谓词
概念 谓词是一种特殊的函数对象其返回值为bool类型主要用于条件判断等场景。在 STL 算法中谓词常用于筛选符合特定条件的元素或进行元素之间的比较。一元谓词 一元谓词是接受一个参数并返回bool值的函数对象。例如定义一个一元谓词IsEven来判断一个数是否为偶数
class IsEven {
public:bool operator()(const int num) {return num % 2 0;}
};在使用find_if算法查找向量中第一个偶数时可以这样应用
vectorint nums {1, 3, 4, 5, 6};
auto it find_if(nums.begin(), nums.end(), IsEven());
if (it ! nums.end()) {std::cout First even number: *it std::endl;
}二元谓词 二元谓词是接受两个参数并返回bool值的函数对象。在排序算法中常用二元谓词来定义元素之间的比较规则。如前面提到的MyComparator类就是一个二元谓词它接受两个int类型参数并返回比较结果用于定义排序顺序。
三内建函数对象
意义 内建函数对象是 STL 提供的一些预定义的函数对象它们涵盖了常见的算术、关系和逻辑操作。这些内建函数对象的存在提高了代码编写的效率开发者无需手动编写这些基本操作的函数对象直接使用即可。算术仿函数 加法仿函数plusplusint()(3, 5)返回3 5的结果即 8。在accumulate算法中结合plus仿函数可用于对容器元素求和例如
vectorint values {1, 2, 3, 4, 5};
int sum accumulate(values.begin(), values.end(), 0, plusint());减法仿函数minusminusint()(5, 3)返回5 - 3的结果即 2。可用于实现两个数的减法操作在一些自定义算法中可能会用到。 乘法仿函数multipliesmultipliesint()(3, 4)返回3 * 4的结果即 12。在数值计算相关的算法中可能会使用到。 除法仿函数dividesdividesint()(6, 3)返回6 / 3的结果即 2。用于实现除法运算。 取模仿函数modulusmodulusint()(7, 3)返回7 % 3的结果即 1。在需要进行取模运算的场景中使用。 3. 关系仿函数 大于仿函数greatergreaterint()(5, 3)返回true因为5 3。在sort算法中如果要对向量进行降序排序可以使用sort(numbers.begin(), numbers.end(), greaterint()); 小于仿函数lesslessint()(3, 5)返回true因为3 5。这是sort算法默认的比较方式用于升序排序。 大于等于仿函数greater_equalgreater_equalint()(5, 5)返回true因为5 5。在一些需要判断大于等于关系的算法中使用。 小于等于仿函数less_equalless_equalint()(3, 3)返回true因为3 3。常用于条件判断场景。 等于仿函数equal_toequal_toint()(3, 3)返回true用于判断两个数是否相等。在查找算法中可能会用到如find_if结合equal_to来查找特定值。 不等于仿函数not_equal_tonot_equal_toint()(3, 5)返回true因为3 ! 5。在需要判断不相等关系的场景中使用。 4. 逻辑仿函数 逻辑与仿函数logical_andlogical_andbool()(true, false)返回false因为true false为false。在一些需要进行逻辑与运算的算法中使用如在对容器元素进行条件筛选时。 逻辑或仿函数logical_orlogical_orbool()(true, false)返回true因为true || false为true。用于逻辑或运算场景例如多个条件判断中只要有一个条件满足的情况。 逻辑非仿函数logical_notlogical_notbool()(true)返回false因为!true为false。用于对逻辑值取反的操作。
六、STL - 常用算法
一常用遍历算法
for_each 语法for_each(iterator start, iterator end, function object)。它接受一个迭代器范围起始迭代器start和结束迭代器end以及一个函数对象。 功能对容器中指定范围内的每个元素逐一应用传入的函数对象。例如假设有一个打印整数的函数对象PrintNumber
class PrintNumber {
public:void operator()(const int num) {std::cout num ;}
};
vectorint nums {1, 2, 3, 4, 5};
for_each(nums.begin(), nums.end(), PrintNumber());上述代码会将nums向量中的每个元素依次打印出来。 应用场景常用于对容器元素进行简单的遍历操作如打印元素、对每个元素进行简单的计算等。 2. transform 语法transform(iterator start, iterator end, output_iterator, function object)或transform(iterator1 start, iterator1 end, iterator2 start, output_iterator, function object)。第一种形式将输入范围[start, end)内的元素通过函数对象进行转换并将结果存储到以output_iterator开始的位置第二种形式从两个输入范围分别以iterator1 start和iterator2 start开始中取出元素通过函数对象进行转换并将结果存储到output_iterator开始的位置。 功能对容器元素进行转换并存储到新容器或原容器。例如将一个向量中的每个元素乘以 2 并存储到另一个向量中
class MultiplyByTwo {
public:int operator()(const int num) {return num * 2;}
};
vectorint source {1, 2, 3, 4, 5};
vectorint result(source.size());
transform(source.begin(), source.end(), result.begin(), MultiplyByTwo());这里MultiplyByTwo函数对象将source向量中的每个元素乘以 2并将结果存储到result向量中。 应用场景在数据转换、类型转换等场景中广泛应用如将字符串向量中的所有字符串转换为大写形式或者将一个数值向量中的每个元素进行特定的数学运算后存储到新向量。
二常用查找算法
find 语法find(iterator start, iterator end, value)。它在指定的迭代器范围[start, end)内查找值为value的元素。 功能在容器中查找指定值。例如在一个向量中查找值为 3 的元素
vectorint numbers {1, 2, 3, 4, 5};
auto it find(numbers.begin(), numbers.end(), 3);
if (it ! numbers.end()) {std::cout Element 3 found at position: std::distance(numbers.begin(), it) std::endl;
}如果找到元素find函数返回指向该元素的迭代器否则返回end迭代器。 应用场景常用于判断容器中是否存在特定元素或者获取特定元素在容器中的位置。 2. find_if 语法find_if(iterator start, iterator end, predicate)。它在指定的迭代器范围[start, end)内查找满足谓词predicate的第一个元素。 功能在容器中查找满足条件的元素。例如查找向量中第一个大于 3 的元素
class GreaterThanThree {
public:bool operator()(const int num) {return num 3;}
};
vectorint nums {1, 2, 4, 5, 3};
auto it1 find_if(nums.begin(), nums.end(), GreaterThanThree());
if (it1 ! nums.end()) {std::cout First element greater than 3: *it1 std::endl;
}应用场景在需要按特定条件筛选元素时使用如在一个学生成绩向量中查找第一个不及格的成绩。 3. adjacent_find 语法adjacent_find(iterator start, iterator end)或adjacent_find(iterator start, iterator end, binary_predicate)。第一种形式查找相邻且相等的元素第二种形式使用自定义的二元谓词查找满足特定条件的相邻元素。 功能查找相邻且相等的元素。例如在一个向量中查找相邻重复的元素
vectorint values {1, 2, 2, 3, 4};
auto it2 adjacent_find(values.begin(), values.end());
if (it2 ! values.end()) {std::cout Adjacent duplicate element found: *it2 std::endl;
}如果找到相邻重复元素返回指向第一个重复元素的迭代器否则返回end迭代器。 应用场景用于检测序列中是否存在相邻重复的元素在数据去重、数据校验等场景中可能会用到。 4. binary_search 语法binary_search(iterator start, iterator end, value)或binary_search(iterator start, iterator end, value, compare)。第一种形式在有序的迭代器范围[start, end)内使用默认比较函数二分查找值为value的元素第二种形式使用自定义的比较函数compare进行二分查找。 功能在有序容器中二分查找指定值。例如在一个有序向量中查找值为 4 的元素
vectorint sortedNums {1, 2, 3, 4, 5};
bool found binary_search(sortedNums.begin(), sortedNums.end(), 4);
if (found) {std::cout Element 4 found in the sorted vector. std::endl;
}如果找到元素返回true否则返回false。 应用场景在需要高效查找有序序列中的元素时使用相比顺序查找二分查找的时间复杂度更低适用于大规模数据的查找。 5. count 语法count(iterator start, iterator end, value)。它在指定的迭代器范围[start, end)内统计值为value的元素个数。 功能统计容器中指定值出现的次数。例如在一个向量中统计值为 2 的元素个数
vectorint numbers {1, 2, 2, 3, 2, 4};
int countVal count(numbers.begin(), numbers.end(), 2);
std::cout The number 2 appears countVal times. std::endl;应用场景常用于统计元素频率如统计一篇文章中某个单词出现的次数。 6. count_if 语法count_if(iterator start, iterator end, predicate)。它在指定的迭代器范围[start, end)内统计满足谓词predicate的元素个数。 功能统计容器中满足条件的元素个数。例如统计向量中大于 3 的元素个数 class GreaterThanThree {
public:bool operator()(const int num) {return num 3;}
};
vectorint nums {1, 2, 4, 5, 3, 6};
int countGreater count_if(nums.begin(), nums.end(), GreaterThanThree());
std::cout The number of elements greater than 3 is: countGreater std::endl;应用场景在需要按条件统计元素数量时使用如统计一个
班级成绩中及格人数、统计一组数据中奇数的数量等场景。
三常用排序算法
sort 语法sort(iterator start, iterator end) 或 sort(iterator start, iterator end, comparator)。第一种形式使用默认的小于比较函数less对迭代器范围 [start, end) 内的元素进行升序排序第二种形式则使用自定义的比较函数 comparator 来决定排序规则。 功能对容器元素进行排序。例如对一个存储整数的向量进行升序排序
std::vectorint numbers {5, 3, 7, 1, 9};
std::sort(numbers.begin(), numbers.end());若要进行降序排序可自定义比较函数
struct Greater {bool operator()(const int a, const int b) {return a b;}
};
std::vectorint numbers {5, 3, 7, 1, 9};
std::sort(numbers.begin(), numbers.end(), Greater());应用场景广泛应用于各种需要对数据进行排序的场景如对学生成绩进行排名、对商品价格进行排序展示等。 2. random_shuffle 语法random_shuffle(iterator start, iterator end)。它对指定迭代器范围 [start, end) 内的元素进行随机重排。 功能随机打乱容器元素顺序。例如将一副扑克牌用向量表示的顺序打乱 std::vectorint deck(52);
for (int i 0; i 52; i) {deck[i] i;
}
std::random_shuffle(deck.begin(), deck.end());应用场景在需要随机化数据顺序的场景中使用如游戏中的随机发牌、随机分组等。 3. merge 语法merge(iterator1 start, iterator1 end, iterator2 start, iterator2 end, output_iterator) 或 merge(iterator1 start, iterator1 end, iterator2 start, iterator2 end, output_iterator, comparator)。第一种形式将两个有序的输入范围分别由 iterator1 start 到 iterator1 end 和 iterator2 start 到 iterator2 end 定义合并到以 output_iterator 开始的输出范围使用默认的小于比较函数第二种形式则使用自定义的比较函数 comparator 进行合并。 功能合并两个有序容器。例如将两个有序的整数向量合并成一个新的有序向量 std::vectorint v1 {1, 3, 5};
std::vectorint v2 {2, 4, 6};
std::vectorint result(v1.size() v2.size());
std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());应用场景在数据处理中当需要将多个有序数据集合并成一个更大的有序数据集时使用如合并多个有序的日志文件。 4. reverse 语法reverse(iterator start, iterator end)。它将指定迭代器范围 [start, end) 内的元素顺序反转。 功能反转容器元素顺序。例如将一个字符串用 string 容器表示反转 std::string str hello;
std::reverse(str.begin(), str.end());应用场景在需要改变序列顺序的场景中使用如将链表反转、将数字的各位顺序反转等。
四常用拷贝和替换算法
copy 语法copy(iterator start, iterator end, output_iterator)。它将迭代器范围 [start, end) 内的元素拷贝到以 output_iterator 开始的位置。 功能将容器元素拷贝到另一个位置。例如将一个向量的元素拷贝到另一个向量 std::vectorint source {1, 2, 3, 4, 5};
std::vectorint destination(source.size());
std::copy(source.begin(), source.end(), destination.begin());应用场景常用于数据备份、容器间元素复制等场景如将一个临时计算结果向量复制到最终存储向量。 2. replace 语法replace(iterator start, iterator end, old_value, new_value)。它将迭代器范围 [start, end) 内所有值为 old_value 的元素替换为 new_value。 功能将容器中指定值替换为新值。例如将一个向量中所有的 3 替换为 30 std::vectorint numbers {1, 3, 2, 3, 4};
std::replace(numbers.begin(), numbers.end(), 3, 30);应用场景在数据修正场景中使用如将文本中错误的单词统一替换为正确的单词。 3. replace_if 语法replace_if(iterator start, iterator end, predicate, new_value)。它将迭代器范围 [start, end) 内所有满足谓词 predicate 的元素替换为 new_value。 功能将容器中满足条件的值替换为新值。例如将一个向量中所有大于 5 的元素替换为 0 class GreaterThanFive {
public:bool operator()(const int num) {return num 5;}
};
std::vectorint numbers {1, 3, 7, 4, 8};
std::replace_if(numbers.begin(), numbers.end(), GreaterThanFive(), 0);应用场景在按条件修改数据时使用如将一组成绩中不及格的分数替换为补考标记。 4. swap 语法swap(value1, value2)。它交换两个值 value1 和 value2 的内容。 功能交换两个值。例如交换两个整数变量的值 int a 5;
int b 3;
std::swap(a, b);在容器场景中也可用于交换两个容器的内容如 std::swap(v1, v2); 交换两个向量 v1 和 v2 的内容。 应用场景元素交换、容器内容交换等场景如在排序算法中用于交换元素位置在需要快速切换两个数据集时交换容器内容。
五常用算术生成算法
accumulate 语法accumulate(iterator start, iterator end, initial_value) 或 accumulate(iterator start, iterator end, initial_value, binary_function)。第一种形式将迭代器范围 [start, end) 内的元素累加并加上初始值 initial_value使用默认的加法操作第二种形式则使用自定义的二元函数 binary_function 进行累加操作。 功能对容器元素进行累加求和。例如计算一个向量中所有元素的和 std::vectorint numbers {1, 2, 3, 4, 5};
int sum std::accumulate(numbers.begin(), numbers.end(), 0);若要进行乘法累加即计算所有元素的乘积可自定义二元函数 struct Multiply {int operator()(const int a, const int b) {return a * b;}
};
std::vectorint numbers {1, 2, 3, 4, 5};
int product std::accumulate(numbers.begin(), numbers.end(), 1, Multiply());应用场景数值计算场景如计算一组数据的总和、平均值等在金融计算、统计分析等领域有广泛应用。 2. fill 语法fill(iterator start, iterator end, value)。它将迭代器范围 [start, end) 内的所有元素填充为指定值 value。 功能将容器指定范围填充为指定值。例如将一个向量的所有元素初始化为 0 std::vectorint numbers(5);
std::fill(numbers.begin(), numbers.end(), 0);应用场景在初始化容器元素、重置容器内容等场景中使用如在进行多次数据处理前将结果容器清空并填充为初始值。
六常用集合算法
set_intersection 语法set_intersection(iterator1 start, iterator1 end, iterator2 start, iterator2 end, output_iterator) 或 set_intersection(iterator1 start, iterator1 end, iterator2 start, iterator2 end, output_iterator, comparator)。第一种形式求两个有序范围分别由 iterator1 start 到 iterator1 end 和 iterator2 start 到 iterator2 end 定义的交集并将结果存储到以 output_iterator 开始的位置使用默认的小于比较函数第二种形式使用自定义的比较函数 comparator。 功能求两个有序集合的交集。例如求两个有序向量的交集 std::vectorint v1 {1, 3, 5, 7};
std::vectorint v2 {3, 5, 7, 9};
std::vectorint intersection;
std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(intersection));应用场景在需要找出两个数据集的共同部分时使用如找出两个学生名单中的共同学生、两个商品清单中的重复商品等。 2. set_union 语法set_union(iterator1 start, iterator1 end, iterator2 start, iterator2 end, output_iterator) 或 set_union(iterator1 start, iterator1 end, iterator2 start, iterator2 end, output_iterator, comparator)。第一种形式求两个有序范围的并集并将结果存储到以 output_iterator 开始的位置使用默认的小于比较函数第二种形式使用自定义的比较函数 comparator。 功能求两个有序集合的并集。例如求两个有序向量的并集 std::vectorint v1 {1, 3, 5};
std::vectorint v2 {3, 5, 7};
std::vectorint unionSet;
std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(unionSet));应用场景在合并两个数据集且去除重复元素时使用如合并两个课程列表并去除重复课程。 3. set_difference 语法set_difference(iterator1 start, iterator1 end, iterator2 start, iterator2 end, output_iterator) 或 set_difference(iterator1 start, iterator1 end, iterator2 start, iterator2 end, output_iterator, comparator)。第一种形式求第一个有序范围相对于第二个有序范围的差集即存在于第一个范围但不存在于第二个范围的元素并将结果存储到以 output_iterator 开始的位置使用默认的小于比较函数第二种形式使用自定义的比较函数 comparator。 功能求两个有序集合的差集。例如求向量 v1 相对于向量 v2 的差集 std::vectorint v1 {1, 3, 5, 7};
std::vectorint v2 {3, 5};
std::vectorint difference;
std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(difference));应用场景在需要找出两个数据集的差异部分时使用如找出两个版本软件功能列表的新增功能相对于旧版本。 七、总结 C 提高编程中的模板编程和 STL 为开发者提供了强大的工具集。模板编程通过类型参数化实现了代码的高度复用无论是函数模板还是类模板都极大地减少了重复代码的编写提高了代码的通用性和可维护性。STL 作为一套成熟的模板库其六大组件相互协作容器提供了多样化的数据存储结构算法实现了丰富的数据处理操作迭代器则作为桥梁连接了容器和算法使得代码能够高效、灵活地处理各种数据场景。通过对常用容器、函数对象和常用算法的深入理解和应用开发者能够显著提升 C 编程的效率和质量编写出更健壮、更高效的代码。在实际项目开发中合理运用这些技术能够降低开发成本提高软件的性能和可扩展性满足日益复杂的软件需求。因此深入学习和掌握模板编程与 STL 是 C 开发者提升自身能力的关键路径。
copy 语法copy(iterator start, iterator end, output_iterator)。它将迭代器范围 [start, end) 内的元素拷贝到以 output_iterator 开始的位置。 功能将容器元素拷贝到另一个位置。例如将一个向量的元素拷贝到另一个向量accumulate 语法accumulate(iterator start, iterator end, initial_value) 或 accumulate(iterator start, iterator end, initial_value, binary_function)。第一种形式将迭代器范围 [start, end) 内的元素累加并加上初始值 initial_value使用默认的加法操作第二种形式则使用自定义的二元函数 binary_function 进行累加操作。 功能对容器元素进行累加求和。例如计算一个向量中所有元素的和set_intersection 语法set_intersection(iterator1 start, iterator1 end, iterator2 start, iterator2 end, output_iterator) 或 set_intersection(iterator1 start, iterator1 end, iterator2 start, iterator2 end, output_iterator, comparator)。第一种形式求两个有序范围分别由 iterator1 start 到 iterator1 end 和 iterator2 start 到 iterator2 end 定义的交集并将结果存储到以 output_iterator 开始的位置使用默认的小于比较函数第二种形式使用自定义的比较函数 comparator。 功能求两个有序集合的交集。例如求两个有序向量的交集
