羅湖網(wǎng)站建設(shè)優(yōu)化即刻搜索
提示：文章寫完后，目錄可以自動生成，如何生成可參考右邊的幫助文檔
目錄
一、 二分查找
1.二分查找的前提
2.binary_?search函數(shù)
3.lower_bound和upper_bound
二、排序
1.sort概念
2.sort的用法
3.自定義比較函數(shù)
三、全排列
1.next permutation函數(shù)
2.prev_permutation()函數(shù)
四、最值查找
1.min和max函數(shù)
2.min element和max element
3.nth_element函數(shù)
五、大小寫轉(zhuǎn)換
1.islower/isupper函數(shù)
2.tolower/toupper函數(shù)
3.ascii碼
六、其他庫函數(shù)
1.memset()
2.swap()
3.reverse()
4.unique()
一、 二分查找
1.二分查找的前提
庫函數(shù)只能對數(shù)組進(jìn)行二分查找，
對一個(gè)數(shù)組進(jìn)行二分查找的前提是這個(gè)數(shù)組中的元素是單調(diào)的，一般為單調(diào)不減，當(dāng)然如果是單調(diào)不增也可以(需要修改比較函數(shù))
例如:
[1,5,5.9,18]是單調(diào)的
[1,9,9,7,15]不是單調(diào)的
[9,8,8.7,7,1]是單調(diào)的
2.binary_?search函數(shù)
binary_?search是C++標(biāo)準(zhǔn)庫中的一個(gè)算法函數(shù)，用于在已排序的序列(例如數(shù)組或容器中查找特定元素。
容器：C++標(biāo)準(zhǔn)模板庫（STL）提供了一系列預(yù)定義的容器類，這些容器類是用來存儲和管理對象的集合。
它通過二分查找算法來確定序列中是否存在目標(biāo)元素。
函數(shù)返回一個(gè)bool值，表示目標(biāo)元素是否存在于席列中。
如果需要獲取找到的元素的位置，可以使用
lower_?bound函數(shù)或upper_ bound函數(shù)
代碼如下（示例）：
vector<int> numbers = {1, 3, 5, 7};
int a = 5;
//使用binary_?search查找目標(biāo)元素
bool found = binary_?search(numbers.begin(),?numbers.end(),a);
if (found)
? ? ? {
? ? ? ? cout << "a element " << a << "found." << endl;
? ? ?}
? ? ? ? else?
? ? ? ? ? {
? ? ? ? ? ? cout <<?"a element "<< a <<?" not found." << endl;
? ? ? ? ?}
3.lower_bound和upper_bound
前提:數(shù)組必須為非降序。
如果要在非升序的數(shù)組中使用，可以通過修改比較函數(shù)實(shí)現(xiàn)(方法與sort自定義比較函數(shù)似)
lower_ bound(st,ed,x)返回地址[st,ed)中第一個(gè)大于等于x的元素的地址。
//st（起始地址）/ed（結(jié)束地址）
upper_ bound(st,ed,x)返回地址[st,ed)中第一個(gè)大于x的元素的地址。
//地址-首地址=下標(biāo)
如果不存在則返回最后一個(gè)元素的下一個(gè)位置，在vector中即end()。
代碼如下（示例）：
//初始化v
vector<int> v = {5, 1, 3, 7, 9};
sort ( v.begin(), v.end () );
for (auto &i : v)
cout << i << ' ' :
cout << '\n' ;
//找到數(shù)組中第一個(gè)大于等于5的元素位置
cout << (lower_bound(v.begin(), v.end(), 5) - v.begin()) << '\n';
二、排序
1.sort概念
sort函數(shù)包含在頭文件<algorithm>中:在使用前需要#include<algorithm>或使用萬能頭文件。sort是C++標(biāo)準(zhǔn)庫中的一個(gè)函數(shù)模板，用于對指定范圍內(nèi)的元素進(jìn)行排序。
sort算法使用的是快速排序(QuickSort)或者類似快速排序的改進(jìn)算法，具有較好的平均時(shí)間復(fù)雜度，一般為O(nlogn)。
2.sort的用法
sort(起始地址， 結(jié)束地址的下一位， *比較函數(shù)）；
代碼如下（示例）：
int a[100];
int n;? ? ? ? ? ? ? ??
? ? //讀取數(shù)組大小
cin >> n;? ? ??
? ? ?//讀取元素
for(int i = 1;i <= n; ++i)
cin >> a[i];
? ? //對數(shù)組進(jìn)行排序
sort(a +?1, a + n + 1);
? ? //輸出
for(int i = 1;i <= n; ++i)? ? ?
? //可以替換成? for(auto i : v)
cout << a[i] << ' ';
3.自定義比較函數(shù)
sort默認(rèn)使用小于號進(jìn)行排序，如果想要自定義比較規(guī)則，
可以傳入第三個(gè)參數(shù)，可以是函數(shù)或lambda表達(dá)式。
代碼如下（示例）：
bool cmp(const int &u, const int &v)
{
? return u > v;
}
int main()
{
? ?ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
? //初始化v
vector<int> v = {5, 1, 3, 9};
? //對數(shù)組進(jìn)行排序，降序排列
sort（v.begin(), v.end(), cmp);
? //輸出
for(int i = 0,i < v.size(); ++ i)
cout << v[i] <<' ';??
輸出:? 9 5 3 1
結(jié)構(gòu)體可以將小于號重載后進(jìn)行排序，當(dāng)然用前面的方法
也是可行的。
代碼如下（示例）：
struct NO
{
? ?int u, v;
? ?bool operator < (const No &m)const
? ?{
? ? ? ?//以u為第一關(guān)鍵字，v為第二關(guān)鍵字排序
? ? ? ? return u == m.u ? v < m.v : u < m.u;
? ? }
三、全排列
1.next permutation函數(shù)
next permutation函數(shù)用于生成當(dāng)前序列的下一個(gè)排列。它按照字典序?qū)π蛄羞M(jìn)行重新排列，如果存在下一個(gè)排列，則將當(dāng)前序列更改為下一個(gè)排列，并返回true;如果當(dāng)前序列已經(jīng)是最后一個(gè)排列，則將序列更改為第一個(gè)排列，并返回false。
代碼如下（示例）：
vector<int> nums = {1, 2, 3};
cout << "initial permutation: ";
for (int num : nums)
? {
? ? ? ?cout << num << " ";
?}
cout << endl;
//生成下一個(gè)排列
while(next_permutation(nums.begin(), nums.end())
{
? ? ? ? cout << "next_permutation: ";
? ? ? ? for (int num :nums)
? ? ? ? ? ? ? cout << num << " ";
? ? ? ? {
? ? ? cout << endl;
}
輸出：
| 1 | 2 | 3 |
| 1 | 3 | 2 |
| 2 | 1 | 3 |
| 2 | 3 | 1 |
| 3 | 1 | 2 |
| 3 | 2 | 1 |
2.prev_permutation()函數(shù)
prev_permutation函數(shù)與next permutation 函數(shù)相反，它用于生成當(dāng)前序列的上一個(gè)排列。它按照字典序?qū)π蛄羞M(jìn)行重新排列，如果存在上一個(gè)排列，則將當(dāng)前序列更改為上一個(gè)排列，并返回true;如果當(dāng)前序列已經(jīng)是第一個(gè)排列，則將序列更改為最后一個(gè)排列，并返回false。
代碼如下（示例）：
vector<int> nums2 = {3, 2, 1};
cout << "initial permutation: ";
for (int num : nums2)
? {
? ? ? ?cout << num << " ";
?}
cout << endl;
//生成上一個(gè)排列
while(prev_permutation(nums2.begin(), nums2.end())
{
? ? ? ? cout << "prev_permutation: ";
? ? ? ? for (int num : nums2)
? ? ? ? ? ? ? cout << num << " ";
? ? ? ? {
? ? ? cout << endl;
}
輸出：
| 3 | 2 | 1 |
| 3 | 1 | 2 |
| 2 | 1 | 3 |
| 2 | 1 | 3 |
| 1 | 3 | 2 |
| 1 | 2 | 3 |
四、最值查找
1.min和max函數(shù)
?
min(a,b)返回a和b中較小的那個(gè)值，只能傳入兩個(gè)值，或傳入一個(gè)列表。例如:
min(3, 5)=3
min({1,2,3,4})=1
max(a,b)返回a和b中較大的那個(gè)值，只能傳入兩個(gè)值，或傳入一個(gè)列表。例如:
max(7,5)=7
min({1,2, 3,4})=4
時(shí)間復(fù)雜度為O(1)，傳入?yún)?shù)為數(shù)組時(shí)時(shí)間復(fù)雜度為0(n)，n為數(shù)組大小。
min,max函數(shù)是在取最值操作時(shí)最常用的操作。
2.min element和max element
min_element(st,ed)返回地址[st,ed)中最小的那個(gè)值的地址(迭代器)，傳入?yún)?shù)為兩個(gè)地址或迭代器。
max_element(st,ed)返回地址[st,ed)中最大的那個(gè)值的地址(迭代器)，傳入?yún)?shù)為兩個(gè)地址或迭代器。
時(shí)間復(fù)雜度均為O(n)，n為數(shù)組大小(由傳入的參數(shù)決定)
代碼如下（示例）：
//初始化v
vector <int> v = (5，1,3，9,11};
//輸出最大的元素，*表示解引用，即通過地址(迭代器)得到值
cout << ( *max_element(v.?begin,? v.end()) << '/n';
輸出：11
3.nth_element函數(shù)
nth element(st, k, ed)
進(jìn)行部分排序，返回值為void()
傳入?yún)?shù)為三個(gè)地址或迭代器。其中第二個(gè)參數(shù)位置的元素將處于正確位置，其他位置元素的順序可能是任意的，但前面的都比它小，后面的都比它大。時(shí)間復(fù)雜度O(n)。
代碼如下（示例）：
//初始化
vector<int>v={5,1,7,3, 10,18, 9};
//輸出最大的元素，*表示解引用，即通過地址(達(dá)代器)得到值
nth_?element(v.begin(),v.begin()+ 3,v.end());
//這里v[3]的位置將會位于排序后的位置，其他的任意
for(auto &i :v)
cout <<? i? <<? " ";、
輸出：3 1 5 7 9 18 10
五、大小寫轉(zhuǎn)換
1.islower/isupper函數(shù)
islower和isupper是C++標(biāo)準(zhǔn)庫中的字符分類函數(shù)，用于檢查一個(gè)字符是否為小寫字母或大寫字母islower和isupper函數(shù)需要包含頭文件<cctype>，也可用方能頭包含。函數(shù)返回值為bool類型。
代碼如下（示例）：
char ch1='A ';
char ch2 ='b';
//使用 islower 函數(shù)判斷字符是否為小寫字母
if(islower(ch1))
{
? ? ? ? ? cout << ch1?<< " is a lowercase letter." << endl;
}
? ? ? ? ? ? ?else
? ? ? ? ? ?{
? ? ? ? ? ? ? ? ? ? ?cout << ch1 << "is not a lowercase letter." << endl;
? ? ? ? ? ?}
//使用 isupper 函數(shù)判斷字符是否為大寫字母
if (isupper(ch2))
{
? ? ? ? ? cout << ch2 << " is an uppercase letter."<< endl;
?}
? ? ? ?else
? ? ? ? {
? ? ? ? cout << ch2 << "is not an uppercase letter." << endl;
? ? ? ? }
2.tolower/toupper函數(shù)
tolower(charch)可以將ch轉(zhuǎn)換為小寫字母，如果ch不是大寫字母則不進(jìn)
行操作。toupper()同理。
代碼如下（示例）：
char ch1 ='A';
char ch2= 'b';
//使用tolower 函數(shù)將字符轉(zhuǎn)換為小寫字母
char lowercaseCh1 = tolower(ch1)；
cout << "Lowercase of " << ch1 << " is " << lowercasech1 << endl;
//使用toupper 所數(shù)將字符轉(zhuǎn)換為大寫字母
char uppercasech2 = toupper(ch2);
cout <<"Uppercase of "<<?ch2 <<"?is "?<< uppercasech2 <<?endl;
3.ascii碼
在了解了ascii碼后，我們可以通過直接對英文字母進(jìn)行加減運(yùn)算計(jì)算出其大小寫的字符。
在ASCI碼表中，大寫字母的編碼范圍是65(A)到90(Z)，而小寫字母的編碼范圍是97(a”)到122(z)。根據(jù)這個(gè)規(guī)則，可以使用ASCII碼表進(jìn)行大小寫轉(zhuǎn)換。
代碼如下（示例）：
char ch='A';//大寫字母
char convertedch;
if (ch >= 'A’ && ch <= 'z')
? ? ? ? {?
? ? ? ? ?//大寫字母轉(zhuǎn)換為小寫字母
? ? ? ? ?convertedch =ch+32;
? ? ? ? ?cout << "converted character: " << convertedch << endl;
? ? ? ? ?}
? ? ? ? ? ? ? else if (ch>='a'88 ch<= 'z')
? ? ? ? ? ? ? ?{
? ? ? ? ? ? ? ?// 小寫字母轉(zhuǎn)換為大寫字母
? ? ? ? ? ? ? ? convertedch=ch-32;
? ? ? ? ? ? ? ?cout << "converted character: " << convertedch << endl;
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?cout << "Invalid character!"? << endl;
? ? ? ? ? ? ? ? ? ? ? ? ? ? }
六、其他庫函數(shù)
1.memset()
memset()是一個(gè)用于設(shè)置內(nèi)存塊值的函數(shù)它的原型定義在<cstring>頭文件中，
函數(shù)的聲明如下:
void* memset(void* ptr,int value, size t num);
memset0)函數(shù)接受三個(gè)參數(shù):
1.ptr:指向要設(shè)置值的內(nèi)存塊的指針。
2.value:要設(shè)置的值，通常是一個(gè)整數(shù)。
3.num:要設(shè)置的字節(jié)數(shù)。
memset0函數(shù)將ptr指向的內(nèi)存塊的前num個(gè)字節(jié)設(shè)置為value的值。它返回一個(gè)指向ptr的指針。memset0函數(shù)通常用于初始化內(nèi)存塊，將其設(shè)置為特定的值。例如，如果要將一個(gè)整型數(shù)組的所有元素設(shè)置為0，可以使用memset0)函數(shù)如下
int arr[10];emset(arr,0,sizeof(arr));
在上述示例中，，memset(arr,0.sizeof(arr))將數(shù)組arr的所有元素設(shè)置為0,需要注意的是，memset()函數(shù)對于非字符類型的數(shù)組可能會產(chǎn)生未定義行為。在處理非字符類型的數(shù)組時(shí)，更好使用C++中的其他方法，如循環(huán)遍歷來視memset會將每個(gè)byte設(shè)置為value。
?
2.swap()
swap(T&a,T&b)函數(shù)接受兩個(gè)參數(shù):
1.a:要交換值的第一個(gè)變量的引用
2.b:要交換值的第二個(gè)變量的引用
swap()函數(shù)通過將第一個(gè)變量的值存儲到臨時(shí)變量中，然后將第二個(gè)變量的值賦給第一個(gè)變量，最后將臨時(shí)變量的值賦給第二個(gè)變量，實(shí)現(xiàn)兩個(gè)變量值的交換。
swap()函數(shù)可以用于交換任意類型的變量，包括基本類型(如整數(shù)、浮點(diǎn)數(shù)等)和自定義類型(如結(jié)構(gòu)體、類對象等)。
以下是一個(gè)示例，展示如何使用swap()函數(shù)交換兩個(gè)整數(shù)的值:
int a= 10;int b= 20;std::swap(a, b);
3.reverse()
reverse()是一個(gè)用于反轉(zhuǎn)容器中元素順序的函數(shù)。它的原型定義在<algorithm>頭文件中，函數(shù)的聲明如下
template<class BidirIt>
void reverse(BidirIt first, BidirIt last);
reverse()函數(shù)接受兩個(gè)參數(shù):
1.first:指向容器中要反轉(zhuǎn)的第一個(gè)元素的迭代器。
2.last:指向容器中要反轉(zhuǎn)的最后一個(gè)元素的下一個(gè)位置的迭代器
reverse()函數(shù)將[first,last)范圍內(nèi)的元素順序進(jìn)行反轉(zhuǎn)。也就是說，它會將[first,last)范圍內(nèi)的元素按相反的順序重新排列。
reverse()函數(shù)可用于反轉(zhuǎn)各種類型的容器，包括數(shù)組、向量、鏈表等。
以下是一個(gè)示例，展示如何使用reverse()函數(shù)反轉(zhuǎn)一個(gè)整型向量的元素順序:
代碼如下（示例）：
#include <iostream>
#include <vectar>
#include <algorith>
int main()
? ? ?{
? ? ? ? ?std::vector<int> vec = {1, 2, 3, 4, 5};
? ? ? ? ?std::reverse(vec.begin(), vec .end( ));
? ? ? ? ? ? ? for?(int num : vec)
? ? ? ? ? ? ? {
? ? ? ? ? ? ? ?std::cout << num <<" ";
? ? ? ? ? ? ? }
? ? ? ? ? ? ? std::cout << std::endl;
? ? ? ? ? ? ? return 0;
? ? ? ? ? ? ? }
在上述示例中，std::reverse(vec.begin()vec.end())將整型向量vec中的元素順序進(jìn)行反轉(zhuǎn)。最終輸出的結(jié)果是54321。需要注意的是，reverse()函數(shù)只能用于一"向迭代器的容器，因?yàn)樗枰軌蛳?#34;后遍歷容器中的元素。對于只支持單器的容器(如前向鏈表)，無法使用rev函數(shù)進(jìn)行反轉(zhuǎn)。
4.unique()
unique()是一個(gè)用于去除容器中相鄰重復(fù)元素的函數(shù),它的原型定義在<algorithm>頭文件中，
函數(shù)的聲明如下
template<class ForwardIt>
ForwardIt unique(ForwardIt first, ForwardIt last);
unique(first, last)函數(shù)接受兩個(gè)參數(shù):
1.first:指向容器中要去重的第一個(gè)元素的迭代器,
2.last:指向容器中要去重的最后元素的下一個(gè)位置的迭代器
unique()函數(shù)將[first, last)范圍內(nèi)的相鄰重復(fù)元素去除，并返回一指向去重后范圍的尾后迭代器去重后的范圍中只保留了第一個(gè)出現(xiàn)的元素，后續(xù)重復(fù)的元素都被移除。
unique()函數(shù)可用于去除各種類型的容器中的相鄰重復(fù)元素，包括數(shù)組、向量、鏈表等。
以下是一個(gè)示例，展示如何使用unique()函數(shù)去除一個(gè)整型向量中的相鄰重復(fù)元素:
int main()
? ? {
? ? ? ? ?std::vector<int> vec = {1, 1, 2, 2, 3, 3, 3.4, 4, 5)
? ? ? ? ?auto it = std::unique(vec.begin(), vec.end( ));
? ? ? ? ?vec.erase(it, vec.end());
? ? ? ? ?for (int num : vec)
? ? ? ? ? {
? ? ? ? ? ? ?std: :cout << num << "? ";
? ? ? ? ? ? ?std::cout << std::endl;
? ? ? ? ? ? ?return 0
? ? }