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(n2)，但其直觀的邏輯是理解排序算法和數組操作的經典入門案例。01核心原理反復遍歷數組，比較相鄰元素并交換逆序對，每輪遍歷將當前最大值"冒泡"到未排序區末尾BUBBLEUP02雙重循環實現外層循環控制輪數（n-1輪），內層循環做相鄰比較，第i輪只需比較前n-1-i個元素N-1ROUNDS03提前終止優化設置boolswapped標志位，若某輪無交換發生說明已有序，可提前退出，最優情況O(n)O(n)BEST04復雜度分析最壞和平均時間復雜度O(n2)，空間復雜度O(1)原地排序，是穩定排序算法O(1)SPACEAlgorithmComparison選擇排序與插入排序選擇排序通過每輪選取最小值減少交換次數，插入排序通過逐步插入維護有序子數組。兩者時間復雜度均為O(n2)，但在不同數據分布下各有優勢，是理解高級排序算法的基礎。選擇排序核心思路每輪從未排序區找最小元素，與未排序區首元素交換，逐步構建有序前綴。性能特點交換次數最多n-1次，但比較次數固定O(n2)，不受數據初始分布影響。穩定性不穩定排序：相同元素的相對順序可能被交換打亂，不適合需要保持原始順序的場景。插入排序核心思路將每個元素插入到已排序子數組的正確位置，類似整理手中的撲克牌。近有序優勢對近乎有序的數組效率接近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