C++大学教程数组与C++标准库类模板

C++大学教程数组与C++标准库类模板Contents课程目录从数组基础到标准库容器，系统掌握C++数据存储与操作的核心知识体系。01数组基础：声明、初始化与访问02数组操作与应用：传参、排序与多维数组03指针与数组：内存视角的深度解析04C++标准库类模板：string与array05vector类模板：动态数组的核心容器CHAPTER01数组基础声明、初始化与访问：掌握C++数组的核心语法DataStructure·C++数组的基本概念与声明数组是C++中最基础的数据结构，它将同类型元素存储在连续的内存区域中，通过下标实现高效随机访问。理解数组的声明语法和内存布局是掌握C++数据处理的基石。C++编程学习·连续内存与下标访问01数组定义—一组相同类型数据的有序集合，在内存中占据连续的存储空间，每个元素通过下标（从0开始）进行访问。02声明语法—类型名数组名[常量表达式]，例如intscores[30]声明了包含30个整数的数组，大小必须在编译时确定。03内存特性—元素在内存中连续排列，相邻元素地址相差一个元素大小的字节数，这一特性使得指针遍历数组非常高效。C++FUNDAMENTALS数组的初始化方式C++提供了多种数组初始化方式，从传统的赋值初始化到C++11的聚合初始化，每种方式都有特定的使用场景。掌握初始化规则能避免未初始化变量导致的难以调试的错误。完全初始化语法形式：intarr[3]={1,2,3}，花括号内元素数量必须与数组大小一致或更少适用场景：已知所有元素初始值时使用，如配置参数表、查找表等固定数据集{1,2,3}部分初始化语法形式：intarr[5]={1,2}，未指定的元素自动初始化为0（整型）或0.0（浮点型）清零技巧：intarr[100]={}可将整个数组初始化为零，比memset更安全且类型安全={}C++11聚合初始化语法形式：intarr[3]{1,2,3}，省略等号的统一初始化语法，与类和结构体初始化风格一致自动推导：intarr[]={1,2,3,4,5}，编译器自动推导数组大小为5，减少手动计数错误autoARRAYACCESS数组元素的访问与遍历数组通过下标运算符实现O(1)时间复杂度的随机访问，配合范围for循环可简洁遍历。但C++不提供内置的边界检查，越界访问会导致未定义行为，程序员必须自行保证下标合法性。下标访问使用arr[i]语法访问第i个元素，时间复杂度O(1)，下标从0开始，合法范围为0到n-1O(1)范围for循环for(intx:arr)自动遍历所有元素，需要修改元素时用for(int&x:arr)传引用引用传递传统for循环for(inti=0;i<n;++i)适用于需要下标索引的场景，如逆序遍历或跳跃访问索引控制越界风险C++不对数组下标做运行时检查，arr[100]越界访问不会报错，可能导致程序崩溃或数据损坏未定义行为MemoryLayout数组的内存布局数组在内存中按元素类型大小连续排列，相邻元素地址间隔等于sizeof(元素类型)。理解内存布局是掌握指针与数组关系、避免内存错误的前提。不同类型数组的内存占用对比（假设数组大小为5）数据类型单元素大小(字节)总占用(字节)相邻元素地址间隔声明示例char151字节charname[5]short2102字节shortvals[5]int4204字节intscores[5]float4204字节floattemps[5]double8408字节doubledata[5]数组总内存=元素个数×sizeof(元素类型)，相邻元素地址差等于元素类型大小MODERNC++·RANGE-BASEDFOR现代C++的数组遍历技巧C++11的auto关键字与范围for循环大幅简化了数组操作代码，但引用传递与值传递的区别直接影响程序正确性和性能。理解auto推导规则是写出高效现代C++代码的基础。auto类型推导autox=arr[0]自动推导为元素类型，auto*p=arr推导为元素指针类型，减少冗余类型声明。auto值拷贝陷阱for(autox:arr)中x是元素的副本，修改x不影响原数组，初学者常在此处犯错。copy引用修改for(auto&x:arr)通过引用直接操作原数组元素，适合需要就地修改的场景。auto&const引用优化for(constauto&x:arr)避免拷贝开销同时防止意外修改，是只读遍历的最佳实践。constauto&CHAPTER02数组操作与应用函数传参、排序算法与多维数组的实战应用C++CoreConcepts数组作为函数参数C++中数组作为函数参数时会退化为指针，丢失大小信息，这是许多数组相关bug的根源。现代C++推荐使用std::array或std::vector替代原生数组，以获得更安全的传参行为。LEGACY传统数组传参⚠️voidfunc(intarr[],intsize)看似传递数组，实际传递的是指向首元素的指针int*，类型信息已丢失。📏函数内sizeof(arr)返回指针大小（通常8字节）而非数组总大小，必须额外传递size参数，易引发越界访问。🔓数组在函数内可被修改，因为传递的是地址而非副本；需要只读保护时应使用constintarr[]修饰参数。MODERNC++现代C++替代方案🔗引用传递固定数组：int(&arr)[10]保留完整类型信息，编译期检查数组大小，但大小必须编译时确定，灵活性受限。📦std::array传参支持size()、拷贝和值语义，类型安全且零开销，是固定大小数组的最佳选择。✅std::vector传参支持动态大小，自动管理内存，边界检查完善，是现代C++实际开发的首选方案。SORTINGALGORITHM冒泡排序算法冒泡排序通过反复比较和交换相邻元素实现数组排序，每轮将最大元素移至末尾。虽然时间复杂度为O(n²)，但其直观的逻辑是理解排序算法和数组操作的经典入门案例。01核心原理反复遍历数组，比较相邻元素并交换逆序对，每轮遍历将当前最大值"冒泡"到未排序区末尾BUBBLEUP02双重循环实现外层循环控制轮数（n-1轮），内层循环做相邻比较，第i轮只需比较前n-1-i个元素N-1ROUNDS03提前终止优化设置boolswapped标志位，若某轮无交换发生说明已有序，可提前退出，最优情况O(n)O(n)BEST04复杂度分析最坏和平均时间复杂度O(n²)，空间复杂度O(1)原地排序，是稳定排序算法O(1)SPACEAlgorithmComparison选择排序与插入排序选择排序通过每轮选取最小值减少交换次数，插入排序通过逐步插入维护有序子数组。两者时间复杂度均为O(n²)，但在不同数据分布下各有优势，是理解高级排序算法的基础。选择排序核心思路每轮从未排序区找最小元素，与未排序区首元素交换，逐步构建有序前缀。性能特点交换次数最多n-1次，但比较次数固定O(n²)，不受数据初始分布影响。稳定性不稳定排序：相同元素的相对顺序可能被交换打乱，不适合需要保持原始顺序的场景。插入排序核心思路将每个元素插入到已排序子数组的正确位置，类似整理手中的扑克牌。近有序优势对近乎有序的数组效率接近O(n)，是Timsort等高级算法的小数组策略。稳定性稳定排序：相同元素不会交换位置，保持原始相对顺序，适合多关键字排序场景。ALGORITHMCOMPARISON数组搜索算法线性搜索适用于无序数组，时间复杂度O(n)；二分搜索要求数组有序，但将时间复杂度降至O(logn)。选择正确的搜索算法能将百万级数据的查找从秒级优化到微秒级。线性搜索LinearSearch·O(n)实现方式—从首元素开始逐个比较，匹配则返回下标，遍历完毕未找到则返回-1适用条件—不要求数组有序，适合一次性查找或小规模数据集，代码简洁不易出错性能局限—大规模数据集下效率低下，100万元素最多需100万次比较O(n)100万次比较二分搜索BinarySearch·O(logn)前提条件—数组必须已排序，通过low、high、mid三个指针不断缩小搜索范围算法效率—每轮排除一半数据，100万元素仅需约20次比较标准库支持—std::binary_search判断是否存在，std::lower_bound返回首个不小于目标的位置O(logn)仅需~20次比较C++Fundamentals多维数组多维数组将一维数组扩展为矩阵和张量结构，C++采用行优先的连续内存布局。虽然原生多维数组语法受限较多，但其内存模型是理解矩阵运算和图像处理的基础。大学课堂中的矩阵数学教学场景01声明语法：intmatrix[rows][cols]声明二维数组，初始化用嵌套花括号{{1,2},{3,4}}02行优先存储：内存中先存第一行所有元素，再存第二行，matrix[i][j]的地址为base+(i*cols+j)*sizeof03函数传参限制：voidfunc(intarr[][4],introws)除第一维外，其余维度大小必须编译时确定04现代替代方案：vector<vector<int>>支持动态行列数、自动内存管理和边界检查，实际开发首选StandardLibraryC++标准库算法与数组C++标准库的algorithm和numeric头文件提供了sort、accumulate、find等高效算法，替代手写循环实现。善用标准库能将开发效率提升数倍，同时获得经过充分测试的可靠实现。std::sort内省排序算法，平均O(nlogn)，对原生数组排序，支持自定义比较函数O(nlogn)std::find与count在范围内查找元素或统计出现次数，返回迭代器或计数值，避免手写遍历iterator/countaccumulate数值累加和前缀和计算，定义在numeric头文件中，支持自定义运算符<numeric>max/min_element返回范围内最大或最小元素的迭代器，一次遍历即可获取极值位置一次遍历CHAPTER03指针与数组从内存地址视角深度理解指针运算与数组的底层联系ARRAYS&POINTERS数组名与指针的等价关系C++中数组名在大多数表达式中退化为指向首元素的指针，arr[i]本质上是*(arr+i)的语法糖。但数组与指针并非完全等价，sizeof和地址可变性是两个关键区别点。退化规则数组名在表达式中自动转换为指向首元素的指针，arr等价于&arr[0]，类型为int*arr≡&arr[0]下标本质arr[i]编译器解释为*(arr+i)，下标运算符就是指针解引用加偏移量的语法糖arr[i]≡*(arr+i)sizeof区别sizeof(arr)返回整个数组字节数（如20字节），sizeof(ptr)仅返回指针大小（通常8字节）20Bvs8B地址可变性数组名是常量地址不可修改（arr++非法），指针变量可自由移动（ptr++合法）CONSTvsVARPOINTERARITHMETIC指针算术运算指针加减运算以元素大小为单位而非字节，编译器根据指针类型自动计算偏移量。指针算术是实现高效数组遍历、内存操作和底层数据结构的基础工具。类型感知偏移ptr+1移动sizeof(*ptr)个字节，int*移动4字节，double*移动8字节sizeof(*ptr)指针相减两个指向同一数组的指针相减得到元素个数差，常用于计算区间长度ptrdiff_t指针遍历通过指针递增遍历数组，是系统级编程的常见模式p<arr+n比较运算同一数组内的指针可用<>==比较，判断元素前后关系或是否指向同一位置<>==CONSTQUALIFIERconst与指针和数组const关键字在指针声明中的位置决定了保护对象：左侧保护数据、右侧保护指针本身。01const修饰数据constint*p—可改变指向但不可修改所指数据，适合只读遍历数组。函数参数constintarr[]：承诺不修改传入数组，调用者安全传递敏感数据。只读访问02const修饰指针int*constp—不可改变指向但可修改所指数据，常用于固定缓冲区句柄。constint*constp：最强保护，用于硬件寄存器映射。双重保护03记忆口诀与实践从右向左读声明：逐层解析避免混淆，清晰理解每层const的保护范围。默认使用const：函数参数和范围for循环中优先用const引用，需要修改时再去除。右到左读MemoryManagement动态数组与内存管理动态数组通过new在堆上分配运行时确定大小的内存，弥补了原生数组大小必须编译时常量的限制。但手动内存管理容易引发泄漏和悬空指针，现代C++推荐用vector替代。动态分配int*arr=newint[n]在堆上分配n个int的连续空间，n可为运行时变量，突破了编译时常量限制。动态数组的大小在程序执行期间确定，提供了灵活的内存使用方式。newint[n]释放规则delete[]arr释放动态数组内存，方括号不可省略，否则只释放首元素导致内存泄漏。正确的释放语法确保整个数组空间被完整回收，避免系统资源浪费。delete[]常见陷阱忘记释放（内存泄漏）、重复释放（程序崩溃）、释放后继续使用（悬空指针/未定义行为）。这些错误难以调试，是C++程序中最常见的内存安全问题来源。3类风险RAII原则用vector或unique_ptr<int[]>封装动态数组，构造时分配、析构时自动释放，杜绝泄漏。RAII将资源生命周期与对象生命周期绑定，是现代C++的核心编程范式。vectorCHAPTER04C++标准库类模板string与array类模板：现代C++对原生数组的安全封装C++TEMPLATES模板的基本概念模板是C++泛型编程的核心机制，通过参数化类型实现一份代码适配多种数据类型。标准库容器和算法大量使用类模板和函数模板，在编译时生成类型安全的特化代码，兼顾灵活性与运行效率。函数模板template<typenameT>声明类型参数T，编译器根据实参类型自动推导并生成特化版本template<typenameT>类模板template<typenameT>classBox将类型作为参数，Box<int>和Box<string>共享同一份定义Box<int>·Box<string>编译时特化模板在编译阶段实例化为具体类型代码，运行时无额外开销，不同于Java的泛型擦除零运行时开销标准库基石vector<T>、array<T,N>、sort()等标准库组件均基于模板实现，一套代码服务所有类型vector·array·sortC++STANDARDLIBRARYC++string类string类是C++标准库对C风格字符数组的安全封装，提供自动内存管理、丰富的成员函数和运算符重载。使用string替代char数组能消除缓冲区溢出风险，大幅提升字符串处理的安全性和开发效率。创建与初始化01直接赋值：strings="hello"自动管理内存，无需指定缓冲区大小，不会发生溢出02构造方式：strings(5,'a')创建重复字符，strings(other)拷贝构造，strings(other,2,3)截取子串常用操作01拼接与比较：s1+s2直接拼接，s1==s2按字典序比较，无需strcmp/strcpy等C函数02长度与访问：s.size()返回字符数，s[i]下标访问，s.at(i)带边界检查的访问（越界抛异常）03查找与截取：s.find("sub")返回子串位置，s.substr(pos,len)提取子串，string::npos表示未找到Iterator&Interopstring迭代器与C字符串互操作string支持迭代器接口，可与标准库算法无缝配合；c_str()提供与C风格字符串的桥接能力。迭代器遍历s.begin()/s.end()返回双向迭代器，支持for循环和sort、reverse等标准库算法算法配合sort(s.begin(),s.end())排序字符，count统计特定字符出现次数c_str()桥接返回constchar*指向内部C风格字符串，可传给printf、fopen等C函数生命周期注意c_str()指针在string修改或销毁后失效，不可长期缓存或跨线程传递C++StandardLibraryarray类模板C++11的array<T,N>类模板是原生数组的零开销抽象，提供size()、at()、迭代器等现代接口的同时保持与原生数组相同的内存布局和性能。在新代码中应优先使用array替代原生数组。01声明语法array<int,5>arr={1,2,3,4,5}array<int,5>arr={1,2,3,4,5}，类型和大小均为模板参数，大小必须编译时常量02安全访问arr.at(i)out_of_rangearr[i]arr.at(i)带边界检查，越界抛出out_of_range异常；arr[i]不检查边界，与原生数组行为一致03值语义支持arr1=arr2arr1==arr2arr1=arr2完整拷贝，arr1==arr2逐元素比较，原生数组不支持这两种操作04零开销抽象编译器优化后与原生数组完全相同的内存布局和访问速度，无任何运行时额外开销C++ContainerComparison原生数组vsarrayvsvector原生数组、std::array和std::vector各有适用场景：array适合编译时固定大小的高性能场景，vector适合运行时动态变化的通用场景，原生数组仅在与C代码互操作时才考虑。三种数组方案的核心特性对比特性原生数组int[]array<T,N>vector<T>大小确定时机编译时编译时运行时可变size()方法不支持支持支持边界检查(at)不支持支持支持赋值/比较不支持支持支持传参退化退化为指针不退化不退化动态扩容不支持不支持支持性能开销零开销零开销微小开销新代码优先使用array（固定大小）或vector（动态大小），原生数组仅用于C接口兼容CHAPTER05vector类模板动态数组的核心容器：从基础操作到性能优化的全面掌握C++StandardLibrary·Containersvector的创建与基本操作vector提供灵活的构造方式和丰富的元素操作接口，支持动态增删和随机访问。作为C++标准库最常用的容器，vector的API设计兼顾了易用性和功能性。SECTION创建方式默认构造：vector<int>v创建空vector，vector<int>v(10)创建10个默认值（int为0）填充构造：vector<int>v(10,42)创建10个42，vector<int>v{1,2,3}初始化列表构造拷贝与范围：vector<int>v(other)拷贝构造，vector<int>v(first,last)从迭代器范围构造SECTION元素操作动态增删：push_back()末尾添加O(1)均摊，pop_back()末尾删除，insert/erase中间操作O(n)访问方式：v[i]下标访问无检查，v.at(i)带边界检查抛异常，v.front()/v.back()访问首尾容量查询：v.size()当前元素数，v.empty()判空，v.clear()清空，v.resize(n)调整大小MEMORYMANAGEMENTvector的容量管理与扩容机制vector通过size和capacity分离实现动态扩容，倍增策略保证push_back的均摊O(1)复杂度。使用reserve预分配内存可避免多次扩容的数据拷贝开销，是处理大规模数据的关键优化手段。SIZE/CAPACITYsize与capacity：size是当前元素个数，capacity是已分配空间可容纳的元素数，≥sizeAUTORESIZE自动扩容策略：size超过capacity时分配更大内存并迁移数据，通常倍增（capacity*=2），单次O(n)×2AMORTIZED均摊复杂度：虽然扩容是O(n)，但N次push_back总开销为O(N)，均摊每次O(1)，数学上可严格证明O(1)PRE-ALLOCATEreserve预分配：v.reserve(10000)一次性分配足够内存，避免反复扩容拷贝，大数据量场景性能提升显著10K服务器内存硬件·动态扩容的物理基础Iterators&Algorithmsvector迭代器与算法配合vector提供完整的迭代器接口，与标准库算法形成"容器-算法-迭代器"三位一体的STL设计模式。正向迭代器v.begin()/v.end()支持随机访问，可进行it+n、it1-it2等指针式运算begin()·end()const与反向v.cbegin()/v.cend()返回只读迭代器，v.rbegin()/v.rend()支持逆序遍历cbegin()·rbegin()算法配合sort()排序，find()查找，transform()变换，accumulate()求和sort·find·transformLambda表达式配合[](intx){returnx>0;}可内联定义谓词，实现灵活的自定义筛选和变换[](){...}C++Vectorvector的传参与二维应用vector按const引用传递避免拷贝开销，C++11移动语义使返回vector高效无冗余拷贝。函数传参最佳实践CONSTREFconst引用传递：voidfunc(constvector<int>&v