- STL源碼剖析 算法章節 算法總覽_CHYabc123456hh的博客-CSDN博客
質變算法
- 質變算法 - 會改變操作對象的數值，比如互換、替換、填寫、刪除、排列組合、分隔、隨機重排、排序等
#include <iostream>
#include <vector>int main(){int ia[] = {22,30,20,34,45,64,34,56,75,34};std::vector<int>iv(ia,ia+(sizeof (ia) / sizeof (int)));for (int i = 0; i < iv.size(); ++i) {std::cout << iv[i] << ' ';}std::cout << std::endl;std::cout << iv.size() << ' ';//錯誤的 sort屬于質變算法 不應該使用const迭代器
// std::vector<int>::const_iterator cit1 = iv.begin();
// std::vector<int>::const_iterator cit2 = iv.end();
// std::sort(iv.begin(),iv.end());std::vector<int>::iterator cit1 = iv.begin();std::vector<int>::iterator cit2 = iv.end();std::sort(cit1,cit2);}
非質變算法
- 運算過程中不會改變 迭代器標示出來的區間上的元素內容。查找(find)、匹配(find_if)、計數(count)、巡防(for_each)、比較(equal)、尋找極值(max、min)等
- 但是如果在迭代區間上應用一個會改變元素內容的仿函數，也會改變元素的數值
#include <iostream>
#include <vector>template<class T>
struct plus2{void operator()(T& x){x += 2;}
};//template <class T>
void plus3_fun(int& x){x += 3;
// std::cout << x << " ";
}int main(){int ia[] = {22,30,20,34,45,64,34,56,75,34};std::vector<int>iv(ia,ia+(sizeof (ia) / sizeof (int)));for (int i : iv) {std::cout << i << ' ';}std::cout << std::endl;std::cout << iv.size() << ' ';std::cout << std::endl;// std::for_each(iv.begin(),iv.end(),plus2<int>());std::for_each(iv.begin(),iv.end(), plus3_fun);for (int i : iv) {std::cout << i << ' ';}
}
- 算法的泛型話的主要目的是為了，抽象化操作對象的型別、操作對象的標示法和區間目標的移動行為，整個算法也就在一個抽象層面了
- 以簡單的循環查找為例，寫一個find函數
#include<iostream>int * find(int* arrayHead,int arraySize,int value){int i = 0;for (; i < arraySize; ++i) {if (arrayHead[i] == value){break;}}return &(arrayHead[i]);
}
int main(){int array[] = {11,13,34,56,77,8,945,56};int *ptr = nullptr;std::cout << sizeof(array) << std::endl;ptr = find(array,8,13);std::cout << *ptr;
}
- 設定end()即為指向array尾端以外的任何位置，主要目的是為了和其他array指針進行比較，但是不能提領其數值
#include<iostream>int * find(int* arrayHead,int arraySize,int value){int i = 0;for (; i < arraySize; ++i) {if (arrayHead[i] == value){break;}}return &(arrayHead[i]);
}
int main(){const int size = 8;int array[] = {11,13,34,56,77,8,945,56};int *end = array + size;//最后一個元素的位置int *ptr = nullptr;std::cout << sizeof(array)/sizeof(int) << std::endl;ptr = find(array,sizeof(array)/sizeof(int),13);if (ptr == end){std::cout << "Not found!" << std::endl;} else{std::cout << *ptr << " found!" << std::endl;}
}
- 上述find()暴露了容器太多的細節，且太限定于特定的容器。為了讓find函數適配于所有類型的容器，其操作需要更進一步的抽象化
int * find(int* begin,int* end,int value){while (begin != end && *begin != value){++begin;}return begin;
}
- 上述函數適用于[begin() , end) （不包含end指針，end是指最后元素的下一個位置）
#include<iostream>int * find(int* begin,int* end,int value){while (begin != end && *begin != value){++begin;}return begin;
}int main(){const int size = 8;int array[] = {11,13,34,56,77,8,945,56};int *end = array + size;//最后一個元素的位置int*ptr = find(array,end,13);if (ptr == end){std::cout << "not found" << std::endl;} elsestd::cout << *ptr << " found" << std::endl;//也可以適用于查找特定的子區間int* ip = find(array+2,array+5,3);
}
template<typename T> //關鍵詞typename 也可以使用class替代
T * find(T* begin,T* end,T value){//以下用到了operator!= operator* operator++//需要操作符重載while (begin != end && *begin != value){++begin;}//以下操作 會引發copy行為return begin;
}
- 數值的傳遞可由 pass by value改為pass by reference to const 主要目的是出于不是基本數據類型，對象很大，傳遞成本很高，使用引用傳遞可以避免這些成本
- 更進一步 超出指針的思維局限，比如find函數針對的是list，對于指針進行++運算不會將指針指向下一個串行節點，但是如果設計一個class，擁有原生指針的行為，并且對其進行++操作可以指向list的下一個節點，這里指定的是迭代器，其本質是一種智能指針，也就是行為類似指針的對象。
template <class Iterator,class T>
Iterator find(Iterator begin,Iterator end,const T& value){while (begin != end && *begin!=value){++begin;}return begin;
}
