網(wǎng)易云C++第七周筆記(GeekBand)

一、 變易算法
所謂變易算法是指那些改變?nèi)萜髦械膶ο蟮牟僮鳌?/p>

1.1 copy組

template <class InputIterator, class OutputIterator>

OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result);

Copy操作是將兩個輸入迭代器之間的元素拷貝到輸出迭代器處。注意拷貝時采用的是左對齊寄狼,會發(fā)生覆蓋囱持,使用時應該確保容器具有足夠的大小,或者使用inserter迭代器。注意荚藻,由于采用的是左對齊的方式咽扇,可以實現(xiàn)向量元素的左移邪财。

template <class BidirectionalIterator1, class BidirectionalIterator2>

BidirectionalIterator2 copy_backward (BidirectionalIterator1 first,

BidirectionalIterator1 last,

BidirectionalIterator2 result);

與普通的copy對應的,有一種右對齊的拷貝方式copy_backward质欲,指定的輸出迭代器為拷貝的末地址树埠。

template <class InputIterator, class OutputIterator>

OutputIterator copy_n (InputIterator first, int num, OutputIterator result);

也可以采用起始迭代器和個數(shù)進行拷貝。

template <class InputIterator, class OutputIterator, class UnaryPredicate>

OutputIterator copy_if (InputIterator first, InputIterator last,

OutputIterator result, UnaryPredicate pred);

也可以進行if條件的篩選嘶伟,pred參數(shù)可以是函數(shù)指針怎憋,函數(shù)對象,也可以采用匿名函數(shù)九昧。

1.2 swap組

template <class T> void swap (T& a, T& b);

Swap操作將a绊袋,b兩個容器(不是迭代器)中的元素交換。

template <class ForwardIterator1, class ForwardIterator2>

ForwardIterator2 swap_ranges (ForwardIterator1 first1, ForwardIterator1 last1,

ForwardIterator2 first2);

也可以采用元素區(qū)間的方式進行交換铸鹰。注意這里要求癌别,第一個區(qū)間要小于第二個區(qū)間。函數(shù)的操作是將第一個區(qū)間的全部n個元素和第二個區(qū)間的前n個元素交換蹋笼。也就是說展姐,第二個區(qū)間后邊的元素不會被改變躁垛。

1.3 transform

template <class InputIterator, class OutputIterator, class UnaryOperation>

OutputIterator transform (InputIterator first1, InputIterator last1,

OutputIterator result, UnaryOperation op);

Transform會把容器中的元素進行相應的"轉(zhuǎn)換",將每個元素丟給op函數(shù)進行操作圾笨,返回值存到result開始 位置中教馆。如果result == first1,就是完整的轉(zhuǎn)換操作擂达。

template <class InputIterator1, class InputIterator2,

class OutputIterator, class BinaryOperation>

OutputIterator transform (InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, OutputIterator result,

BinaryOperation binary_op);

這種重載的特點是土铺,最后的操作不再是一個單參操作,而是雙參操作谍婉。其第一個參數(shù)是first1到last1之間的每一個元素舒憾,而第二個參數(shù)則從first2開始,一一對應的進行選擇穗熬。

1.4 replace組

template <class ForwardIterator, class T>

void replace (ForwardIterator first, ForwardIterator last,

const T& old_value, const T& new_value);

普通的replace操作是镀迂,對于區(qū)間內(nèi)的操作,如果等于old_value,則將其替換為新的值唤蔗。

template <class ForwardIterator, class UnaryPredicate, class T>

void replace_if (ForwardIterator first, ForwardIterator last,

UnaryPredicate pred, const T& new_value );

也可以進行需要函數(shù)判斷替換的replace_if操作探遵,將區(qū)間內(nèi)的每個元素扔給函數(shù)對象,如果返回值為真則進行替換妓柜。

template <class InputIterator, class OutputIterator, class T>

OutputIterator replace_copy (InputIterator first, InputIterator last,

OutputIterator result,

const T& old_value, const T& new_value);

Replace_copy操作是將區(qū)間內(nèi)的元素先復制到目的迭代器指定的位置處箱季,注意目的迭代器的容量問題。隨后棍掐,并且對目的迭代器中的這些元素進行替換操作藏雏。

template <class InputIterator, class OutputIterator, class T>

OutputIterator replace_copy_if (InputIterator first, InputIterator last,

OutputIterator result,

UnaryPredicate pred, const T& new_value);

Replace_copy_if操作就是replace_if的帶復制版本。

1.5 fill

template <class ForwardIterator, class T>

void fill (ForwardIterator first, ForwardIterator last, const T& val);

將區(qū)間內(nèi)的元素直接用這個值進行填充作煌。

1.6 generate

template <class ForwardIterator, class Generator>

void generate (ForwardIterator first, ForwardIterator last, Generator gen);

將無參函數(shù)gen的返回值放在區(qū)間內(nèi)掘殴。通常用于產(chǎn)生隨機數(shù),例如:

Generate(v.begin(),v.end(),rand);

1.7 remove組

template <class ForwardIterator, class T>

ForwardIterator remove (ForwardIterator first, ForwardIterator last, const T& val);

Remove檢查區(qū)間內(nèi)的元素粟誓,如果相等奏寨,則將這個元素刪除,最后返回一個迭代器鹰服,指向這個被刪除后的區(qū)間中最后的元素病瞳。也就是說,如果原本最后一個元素沒有被刪除悲酷,則指向原本的最后一個元素套菜;如果原本的最后一個元素也被刪除了,則往前移動设易。

template <class ForwardIterator, class UnaryPredicate>

ForwardIterator remove_if (ForwardIterator first, ForwardIterator last,

UnaryPredicate pred);

在普通remove的基礎上笼踩,通過檢驗判別函數(shù)(單參數(shù) )決定是否remove。

template <class InputIterator, class OutputIterator, class T>

OutputIterator remove_copy (InputIterator first, InputIterator last,

OutputIterator result, const T& val);

在普通remove的基礎上亡嫌,改為先將其復制到新的位置嚎于,再對新的容器進行remove操作。

1.8 unique

template <class ForwardIterator>

ForwardIterator unique (ForwardIterator first, ForwardIterator last);

template <class ForwardIterator, class BinaryPredicate>

ForwardIterator unique (ForwardIterator first, ForwardIterator last,

BinaryPredicate pred);

Unique操作挟冠,第一種形式是將相同的元素刪除于购,只保留一份,返回的迭代器和remove操作一樣知染;第二種是通過一個pred函數(shù)的返回值來查看是否是一樣的肋僧,從中可以建立映射。

1.8 reverse

template <class BidirectionalIterator>

void reverse (BidirectionalIterator first, BidirectionalIterator last);

Reverse函數(shù)將容器首位倒置控淡,即"123"->"321";

1.9 rotate

template <class ForwardIterator>

void rotate (ForwardIterator first, ForwardIterator middle,

ForwardIterator last);

Rotate即翻轉(zhuǎn)操作嫌吠,以middle為界,把middle前邊的元素都移到最末尾掺炭,middle成為新的區(qū)間頭辫诅。

1.9 random_shuffle

generator by default (1)

template <class RandomAccessIterator>

void random_shuffle (RandomAccessIterator first, RandomAccessIterator last);

specific generator (2)

template <class RandomAccessIterator, class RandomNumberGenerator>

void random_shuffle (RandomAccessIterator first, RandomAccessIterator last,

RandomNumberGenerator& gen);

Shuffle即洗牌操作;將元素進行打亂涧狮。當進行自定操作時炕矮,則可能是N的階乘中情況中的任何一種。當自定義操作時候者冤,其行為是依次將第i號元素和第gen(i)號元素進行交換肤视,一直到容器底。

1.10 partition

template <class BidirectionalIterator, class UnaryPredicate>

BidirectionalIterator partition (BidirectionalIterator first,

BidirectionalIterator last, UnaryPredicate pred);

Partition的行為是按照pred的返回值的true或false進行劃分涉枫。劃分后返回的迭代器result邢滑,使得[r.begin(),result )為true,[result,r.end())為false愿汰。

二困后、 排序算法
2.1 普通排序

2.1.1 sort
default (1)

template <class RandomAccessIterator>

void sort (RandomAccessIterator first, RandomAccessIterator last);

custom (2)

template <class RandomAccessIterator, class Compare>

void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Sort有兩種形式,第一重型是默認是調(diào)用了operator<函數(shù)進行比較尼桶,小者在前操灿,也可以自行指定,兩兩相比返回值為1的元素在前泵督。

2.1.2 partial_sort
default (1)

template <class RandomAccessIterator>

void partial_sort (RandomAccessIterator first, RandomAccessIterator middle,

RandomAccessIterator last);

custom (2)

template <class RandomAccessIterator, class Compare>

void partial_sort (RandomAccessIterator first, RandomAccessIterator middle,

RandomAccessIterator last, Compare comp);

進行部分排序趾盐,使得first到middle的元素是有序的,而middle到end的元素是打亂的(具體順序不定)小腊。這個排序可以用來找到前n大或者前n小的元素救鲤。例如,原來v中的元素為3,2,1,4,5,1,0秩冈;調(diào)用partial_sort(v.begin(),v.begin+4,v.end())后本缠,結(jié)果是[0,1,1,2,…..(順序不定)]

2.1.3 binary_search
default (1)

template <class ForwardIterator, class T>

bool binary_search (ForwardIterator first, ForwardIterator last,

const T& val);

custom (2)

template <class ForwardIterator, class T, class Compare>

bool binary_search (ForwardIterator first, ForwardIterator last,

const T& val, Compare comp);

在排好序的情況下,進行二分搜索入问,查找值為val的元素丹锹。元素必須先手動排序稀颁。

2.1.4 merge
default (1)

template <class InputIterator1, class InputIterator2, class OutputIterator>

OutputIterator merge (InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, InputIterator2 last2,

OutputIterator result);

custom (2)

template <class InputIterator1, class InputIterator2,

class OutputIterator, class Compare>

OutputIterator merge (InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, InputIterator2 last2,

OutputIterator result, Compare comp);

將兩個已經(jīng)排好的序列進行快速有序合并。

2.2 集合排序算法

2.2.1 includes
template <class InputIterator1, class InputIterator2>

bool includes ( InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, InputIterator2 last2 );

template <class InputIterator1, class InputIterator2, class Compare>

bool includes ( InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, InputIterator2 last2, Compare comp );

檢查一個有序區(qū)間1內(nèi)是否包含另一個有序區(qū)間2內(nèi)的元素楣黍,注意如果排序方法不是operator <,則必須要顯式的聲明出來匾灶。所謂的包含是指,12345中包含了125,1234321包含了33租漂,并不要求連續(xù)阶女。

2.2 堆排序算法

2.2.1 make_heap
default (1)

template <class RandomAccessIterator>

void make_heap (RandomAccessIterator first, RandomAccessIterator last);

custom (2)

template <class RandomAccessIterator, class Compare>

void make_heap (RandomAccessIterator first, RandomAccessIterator last,

Compare comp );

生成一個堆,默認情況下采取operator<進行比較哩治,生成一個大頂堆秃踩;如果進行大于比較,則是生成小頂堆业筏。

這種堆在存儲時采用從上到下憔杨,從左至右的方式進行存儲。

2.2.2 push_heap
default (1)

template <class RandomAccessIterator>

void push_heap (RandomAccessIterator first, RandomAccessIterator last);

custom (2)

template <class RandomAccessIterator, class Compare>

void push_heap (RandomAccessIterator first, RandomAccessIterator last,

Compare comp);

Push_heap操作向堆中添加元素驾孔,并對其進行調(diào)整芍秆。其調(diào)整方法為先將其放到整個堆的末尾,然后再向前進行逐次交換翠勉。由于前面的元素都滿足平衡二叉樹的條件妖啥,這種方法的正確性得以保證。

2.2.3 pop_heap
default (1)

template <class RandomAccessIterator>

void pop_heap (RandomAccessIterator first, RandomAccessIterator last);

custom (2)

template <class RandomAccessIterator, class Compare>

void pop_heap (RandomAccessIterator first, RandomAccessIterator last,

Compare comp);

從堆頂彈出一個元素对碌。對于大頂堆荆虱,則代表彈出最大元素。彈出后重新調(diào)整為平衡二叉樹的方法是朽们,先將其和整個堆末尾的元素進行一次交換怀读,然后將其刪除。隨后骑脱,讓新的根頂元素逐次向下比較交換菜枷,每次都與子節(jié)點中比自己大的較大者交換,知道這一節(jié)點大于其子節(jié)點或是不存在子節(jié)點叁丧。采用這種交換的方式啤誊,保證了平衡二叉樹的緊密,而且具有l(wèi)ogn的時間復雜度拥娄。

2.2.4 sort_heap
default (1)

template <class RandomAccessIterator>

void sort_heap (RandomAccessIterator first, RandomAccessIterator last);

custom (2)

template <class RandomAccessIterator, class Compare>

void sort_heap (RandomAccessIterator first, RandomAccessIterator last,

Compare comp);

利用出堆操作對堆進行排序蚊锹。

三、 泛型數(shù)值算法
1.1 accumulate

sum (1)

template <class InputIterator, class T>

T accumulate (InputIterator first, InputIterator last, T init);

custom (2)

template <class InputIterator, class T, class BinaryOperation>

T accumulate (InputIterator first, InputIterator last, T init,

BinaryOperation binary_op);

Accumulate操作是以init為初始值稚瘾,和每個成員進行操作牡昆。默認情況下的操作為+=,也就是累加運算摊欠。如果指定了一個操作函數(shù)丢烘,那么每次操作result = op(*it,result);注意第一參數(shù)為容器元素柱宦。

例如,求1+…+100可以采用以下代碼:

vector<int> v(100);

iota(v.begin(),v.end(),1);//iota函數(shù)的作用是播瞳,以第三個參數(shù)為起始值捷沸,以遞增1方式填滿整個區(qū)間。

int sum = accumulate(v.begin(),v.end(),0);

1.2 inner_product

sum/multiply (1)

template <class InputIterator1, class InputIterator2, class T>

T inner_product (InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, T init);

custom (2)

template <class InputIterator1, class InputIterator2, class T,

class BinaryOperation1, class BinaryOperation2>

T inner_product (InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, T init,

BinaryOperation1 binary_op1,

BinaryOperation2 binary_op2);

Inner_product是向量內(nèi)積操作狐史,例如,給定向量a[2] = {1,2};b[2] = {3,4};則默認情況下说墨,返回值為13+24骏全;自定義的方式下,則op2表示按位置一一對應時進行何種運算尼斧,而op1則表示對這些所有結(jié)果進行何種運算姜贡。例如,若使用inner_product(a,a+3,b,1,multiplies<int>(),plus<int>());則計算1(1+3)(2+4)的結(jié)果棺棵。

1.3 partial_sum

sum (1)

template <class InputIterator, class OutputIterator>

OutputIterator partial_sum (InputIterator first, InputIterator last,

OutputIterator result);

custom (2)

template <class InputIterator, class OutputIterator, class BinaryOperation>

OutputIterator partial_sum (InputIterator first, InputIterator last,

一種zigzag形式的運算楼咳,如圖所示,對1,2,3,4,5進行此種運算的過程是:

可以看到烛恤,產(chǎn)生的結(jié)果是一組數(shù)據(jù)母怜,每一個數(shù)據(jù)都是前n個數(shù)據(jù)的累計。

1.4 adjacent_difference

difference (1)

template <class InputIterator, class OutputIterator>

OutputIterator adjacent_difference (InputIterator first, InputIterator last,

OutputIterator result);

custom (2)

template <class InputIterator, class OutputIterator, class BinaryOperation>

OutputIterator adjacent_difference ( InputIterator first, InputIterator last,

OutputIterator result, BinaryOperation binary_op );

最后編輯于
?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末缚柏,一起剝皮案震驚了整個濱河市苹熏,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌币喧,老刑警劉巖轨域,帶你破解...
    沈念sama閱讀 219,589評論 6 508
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異杀餐,居然都是意外死亡干发,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,615評論 3 396
  • 文/潘曉璐 我一進店門史翘,熙熙樓的掌柜王于貴愁眉苦臉地迎上來枉长,“玉大人,你說我怎么就攤上這事恶座〔笫睿” “怎么了?”我有些...
    開封第一講書人閱讀 165,933評論 0 356
  • 文/不壞的土叔 我叫張陵跨琳,是天一觀的道長自点。 經(jīng)常有香客問我,道長脉让,這世上最難降的妖魔是什么桂敛? 我笑而不...
    開封第一講書人閱讀 58,976評論 1 295
  • 正文 為了忘掉前任功炮,我火速辦了婚禮,結(jié)果婚禮上术唬,老公的妹妹穿的比我還像新娘薪伏。我一直安慰自己,他們只是感情好粗仓,可當我...
    茶點故事閱讀 67,999評論 6 393
  • 文/花漫 我一把揭開白布嫁怀。 她就那樣靜靜地躺著,像睡著了一般借浊。 火紅的嫁衣襯著肌膚如雪塘淑。 梳的紋絲不亂的頭發(fā)上距糖,一...
    開封第一講書人閱讀 51,775評論 1 307
  • 那天岭皂,我揣著相機與錄音,去河邊找鬼铅碍。 笑死曙蒸,一個胖子當著我的面吹牛捌治,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播纽窟,決...
    沈念sama閱讀 40,474評論 3 420
  • 文/蒼蘭香墨 我猛地睜開眼肖油,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了师倔?” 一聲冷哼從身側(cè)響起构韵,我...
    開封第一講書人閱讀 39,359評論 0 276
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎趋艘,沒想到半個月后疲恢,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,854評論 1 317
  • 正文 獨居荒郊野嶺守林人離奇死亡瓷胧,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,007評論 3 338
  • 正文 我和宋清朗相戀三年显拳,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片搓萧。...
    茶點故事閱讀 40,146評論 1 351
  • 序言:一個原本活蹦亂跳的男人離奇死亡杂数,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出瘸洛,到底是詐尸還是另有隱情揍移,我是刑警寧澤,帶...
    沈念sama閱讀 35,826評論 5 346
  • 正文 年R本政府宣布反肋,位于F島的核電站那伐,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜罕邀,卻給世界環(huán)境...
    茶點故事閱讀 41,484評論 3 331
  • 文/蒙蒙 一畅形、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧诉探,春花似錦日熬、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,029評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至敬肚,卻和暖如春怕敬,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背帘皿。 一陣腳步聲響...
    開封第一講書人閱讀 33,153評論 1 272
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留畸陡,地道東北人鹰溜。 一個月前我還...
    沈念sama閱讀 48,420評論 3 373
  • 正文 我出身青樓,卻偏偏與公主長得像丁恭,于是被迫代替她去往敵國和親曹动。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 45,107評論 2 356

推薦閱讀更多精彩內(nèi)容