原文網(wǎng)址

參考網(wǎng)址

• C語(yǔ)言中文網(wǎng)

請(qǐng)你來(lái)說(shuō)一下map和set有什么區(qū)別，分別又是怎么實(shí)現(xiàn)的？

• map和set都是C++的關(guān)聯(lián)容器，其底層實(shí)現(xiàn)都是紅黑樹(shù)（RB-Tree）。由于 map 和set所開(kāi)放的各種操作接口，RB-tree 也都提供了，所以幾乎所有的 map 和set的操作行為，都只是轉(zhuǎn)調(diào) RB-tree 的操作行為。

map和set區(qū)別在于

• （1）map中的元素是key-value（關(guān)鍵字—值）對(duì)：關(guān)鍵字起到索引的作用，值則表示與索引相關(guān)聯(lián)的數(shù)據(jù)；Set與之相對(duì)就是關(guān)鍵字的簡(jiǎn)單集合，set中每個(gè)元素只包含一個(gè)關(guān)鍵字。
• （2）set的迭代器是const的，不允許修改元素的值；map允許修改value，但不允許修改key。其原因是因?yàn)閙ap和set是根據(jù)關(guān)鍵字排序來(lái)保證其有序性的，如果允許修改key的話，那么首先需要?jiǎng)h除該鍵，然后調(diào)節(jié)平衡，再插入修改后的鍵值，調(diào)節(jié)平衡，如此一來(lái)，嚴(yán)重破壞了map和set的結(jié)構(gòu)，導(dǎo)致iterator失效，不知道應(yīng)該指向改變前的位置，還是指向改變后的位置。所以STL中將set的迭代器設(shè)置成const，不允許修改迭代器的值；而map的迭代器則不允許修改key值，允許修改value值。
• （3）map支持下標(biāo)操作，set不支持下標(biāo)操作。map可以用key做下標(biāo)，map的下標(biāo)運(yùn)算符[ ]將關(guān)鍵碼作為下標(biāo)去執(zhí)行查找，如果關(guān)鍵碼不存在，則插入一個(gè)具有該關(guān)鍵碼和mapped_type類型默認(rèn)值的元素至map中，因此下標(biāo)運(yùn)算符[ ]在map應(yīng)用中需要慎用，const_map不能用，只希望確定某一個(gè)關(guān)鍵值是否存在而不希望插入元素時(shí)也不應(yīng)該使用，mapped_type類型沒(méi)有默認(rèn)值也不應(yīng)該使用。如果find能解決需要，盡可能用find。

請(qǐng)你來(lái)介紹一下STL的allocaotr??

• STL的分配器用于封裝STL容器在內(nèi)存管理上的底層細(xì)節(jié)。在C++中，其內(nèi)存配置和釋放如下：
• new運(yùn)算分兩個(gè)階段：(1)調(diào)用::operator new配置內(nèi)存;(2)調(diào)用對(duì)象構(gòu)造函數(shù)構(gòu)造對(duì)象內(nèi)容
• delete運(yùn)算分兩個(gè)階段：(1)調(diào)用對(duì)象析構(gòu)函數(shù)；(2)調(diào)用::operator delete釋放內(nèi)存
• 為了精密分工，STL allocator將兩個(gè)階段操作區(qū)分開(kāi)來(lái)：內(nèi)存配置有alloc::allocate()負(fù)責(zé)，內(nèi)存釋放由alloc::deallocate()負(fù)責(zé)；對(duì)象構(gòu)造由::construct()負(fù)責(zé)，對(duì)象析構(gòu)由::destroy()負(fù)責(zé)。
• 同時(shí)為了提升內(nèi)存管理的效率，減少申請(qǐng)小內(nèi)存造成的內(nèi)存碎片問(wèn)題，SGI STL采用了兩級(jí)配置器，當(dāng)分配的空間大小超過(guò)128B時(shí)，會(huì)使用第一級(jí)空間配置器；當(dāng)分配的空間大小小于128B時(shí)，將使用第二級(jí)空間配置器。第一級(jí)空間配置器直接使用malloc()、realloc()、free()函數(shù)進(jìn)行內(nèi)存空間的分配和釋放，而第二級(jí)空間配置器采用了內(nèi)存池技術(shù)，通過(guò)空閑鏈表來(lái)管理內(nèi)存。

參考鏈接

• 標(biāo)準(zhǔn)庫(kù) STL ：Allocator能做什么？
• C++中std::allocator的使用
• 第10篇:C++ 堆內(nèi)存管理器-allocator

?請(qǐng)你來(lái)說(shuō)一說(shuō)STL迭代器刪除元素

• 這個(gè)主要考察的是迭代器失效的問(wèn)題。
• 1.對(duì)于序列容器vector,deque來(lái)說(shuō)，使用erase(itertor)后，后邊的每個(gè)元素的迭代器都會(huì)失效，但是后邊每個(gè)元素都會(huì)往前移動(dòng)一個(gè)位置，但是erase會(huì)返回下一個(gè)有效的迭代器；
• 2.對(duì)于關(guān)聯(lián)容器map set來(lái)說(shuō)，使用了erase(iterator)后，當(dāng)前元素的迭代器失效，但是其結(jié)構(gòu)是紅黑樹(shù)，刪除當(dāng)前元素的，不會(huì)影響到下一個(gè)元素的迭代器，所以在調(diào)用erase之前，記錄下一個(gè)元素的迭代器即可。
• 3.對(duì)于list來(lái)說(shuō)，它使用了不連續(xù)分配的內(nèi)存，并且它的erase方法也會(huì)返回下一個(gè)有效的iterator，因此上面兩種正確的方法都可以使用。

請(qǐng)你說(shuō)一說(shuō)STL中MAP數(shù)據(jù)存放形式

• 紅黑樹(shù)。unordered map底層結(jié)構(gòu)是哈希表

請(qǐng)你講講STL有什么基本組成

• 容器、算法、迭代器、函數(shù)對(duì)象、適配器、內(nèi)存分配器這 6 部分構(gòu)成，其中后面 4 部分是為前 2 部分服務(wù)的

STL的組成含義

容器	一些封裝數(shù)據(jù)結(jié)構(gòu)的模板類，例如 vector 向量容器、list 列表容器等。
算法	STL 提供了非常多（大約 100 個(gè)）的數(shù)據(jù)結(jié)構(gòu)算法，它們都被設(shè)計(jì)成一個(gè)個(gè)的模板函數(shù)，這些算法在 std 命名空間中定義，其中大部分算法都包含在頭文件 <algorithm> 中，少部分位于頭文件 <numeric> 中。
迭代器	在?C++?STL 中，對(duì)容器中數(shù)據(jù)的讀和寫(xiě)，是通過(guò)迭代器完成的，扮演著容器和算法之間的膠合劑。
函數(shù)對(duì)象	如果一個(gè)類將 () 運(yùn)算符重載為成員函數(shù)，這個(gè)類就稱為函數(shù)對(duì)象類，這個(gè)類的對(duì)象就是函數(shù)對(duì)象（又稱仿函數(shù)）。
適配器	可以使一個(gè)類的接口（模板的參數(shù)）適配成用戶指定的形式，從而讓原本不能在一起工作的兩個(gè)類工作在一起。值得一提的是，容器、迭代器和函數(shù)都有適配器。
內(nèi)存分配器	為容器類模板提供自定義的內(nèi)存申請(qǐng)和釋放功能，由于往往只有高級(jí)用戶才有改變內(nèi)存分配策略的需求，因此內(nèi)存分配器對(duì)于一般用戶來(lái)說(shuō)，并不常用。

頭文件

• <iterator> <functional> <vector> <deque> <list> <queue> <stack> <set> <map> <algorithm> <numeric> <memory> <utility>?

注意事項(xiàng)

• 分配器給容器分配存儲(chǔ)空間
• 算法通過(guò)迭代器獲取容器中的內(nèi)容
• 仿函數(shù)可以協(xié)助算法完成各種操作
• 配接器用來(lái)套接適配仿函數(shù)

參考鏈接

• C++ STL基本組成（6大組件+13個(gè)頭文件）

請(qǐng)你說(shuō)說(shuō)STL中map與unordered_map

Map映射

• map 的所有元素都是 pair，同時(shí)擁有實(shí)值（value）和鍵值（key）。pair 的第一元素被視為鍵值，第二元素被視為實(shí)值。所有元素都會(huì)根據(jù)元素的鍵值自動(dòng)被排序。不允許鍵值重復(fù)。
• 底層實(shí)現(xiàn)：紅黑樹(shù)
• 適用場(chǎng)景：有序鍵值對(duì)不重復(fù)映射

Multimap

• 多重映射。multimap 的所有元素都是 pair，同時(shí)擁有實(shí)值（value）和鍵值（key）。pair 的第一元素被視為鍵值，第二元素被視為實(shí)值。所有元素都會(huì)根據(jù)元素的鍵值自動(dòng)被排序。允許鍵值重復(fù)。
• 底層實(shí)現(xiàn)：紅黑樹(shù)
• 適用場(chǎng)景：有序鍵值對(duì)可重復(fù)映射

請(qǐng)你說(shuō)一說(shuō)vector和list的區(qū)別，應(yīng)用，越詳細(xì)越好

Vector

• 連續(xù)存儲(chǔ)的容器，動(dòng)態(tài)數(shù)組，在堆上分配空間，本質(zhì)是鏈表
• 底層實(shí)現(xiàn)：數(shù)組
• 兩倍容量增長(zhǎng)：
• vector 增加（插入）新元素時(shí)，如果未超過(guò)當(dāng)時(shí)的容量，則還有剩余空間，那么直接添加到最后（插入指定位置），然后調(diào)整迭代器。
• 如果沒(méi)有剩余空間了，則會(huì)重新配置原有元素個(gè)數(shù)的兩倍空間，然后將原空間元素通過(guò)復(fù)制的方式初始化新空間，再向新空間增加元素，最后析構(gòu)并釋放原空間，之前的迭代器會(huì)失效。

性能：

• 訪問(wèn)：O(1)
• 插入：在最后插入（空間夠）：很快
• 在最后插入（空間不夠）：需要內(nèi)存申請(qǐng)和釋放，以及對(duì)之前數(shù)據(jù)進(jìn)行拷貝。
• 在中間插入（空間夠）：內(nèi)存拷貝
• 在中間插入（空間不夠）：需要內(nèi)存申請(qǐng)和釋放，以及對(duì)之前數(shù)據(jù)進(jìn)行拷貝。
• 刪除：在最后刪除：很快
• 在中間刪除：內(nèi)存拷貝
• 適用場(chǎng)景：經(jīng)常隨機(jī)訪問(wèn)，且不經(jīng)常對(duì)非尾節(jié)點(diǎn)進(jìn)行插入刪除。

List

• 動(dòng)態(tài)鏈表，在堆上分配空間，每插入一個(gè)元數(shù)都會(huì)分配空間，每刪除一個(gè)元素都會(huì)釋放空間。
• 底層：雙向鏈表

性能

• 訪問(wèn)：隨機(jī)訪問(wèn)性能很差，只能快速訪問(wèn)頭尾節(jié)點(diǎn)。
• 插入：很快，一般是常數(shù)開(kāi)銷
• 刪除：很快，一般是常數(shù)開(kāi)銷
• 適用場(chǎng)景：經(jīng)常插入刪除大量數(shù)據(jù)

區(qū)別

• 1）vector底層實(shí)現(xiàn)是數(shù)組；list是雙向 鏈表。
• 2）vector支持隨機(jī)訪問(wèn)，list不支持。
• 3）vector是順序內(nèi)存，list不是。
• 4）vector在中間節(jié)點(diǎn)進(jìn)行插入刪除會(huì)導(dǎo)致內(nèi)存拷貝，list不會(huì)。
• 5）vector一次性分配好內(nèi)存，不夠時(shí)才進(jìn)行2倍擴(kuò)容；list每次插入新節(jié)點(diǎn)都會(huì)進(jìn)行內(nèi)存申請(qǐng)。
• 6）vector隨機(jī)訪問(wèn)性能好，插入刪除性能差；list隨機(jī)訪問(wèn)性能差，插入刪除性能好。

應(yīng)用

• vector擁有一段連續(xù)的內(nèi)存空間，因此支持隨機(jī)訪問(wèn)，如果需要高效的隨即訪問(wèn)，而不在乎插入和刪除的效率，使用vector。
• list擁有一段不連續(xù)的內(nèi)存空間，如果需要高效的插入和刪除，而不關(guān)心隨機(jī)訪問(wèn)，則應(yīng)使用list。

請(qǐng)你來(lái)說(shuō)一下STL中迭代器的作用，有指針為何還要迭代器

1、迭代器

• Iterator（迭代器）模式又稱Cursor（游標(biāo)）模式，用于提供一種方法順序訪問(wèn)一個(gè)聚合對(duì)象中各個(gè)元素, 而又不需暴露該對(duì)象的內(nèi)部表示?；蛘哌@樣說(shuō)可能更容易理解：Iterator模式是運(yùn)用于聚合對(duì)象的一種模式，通過(guò)運(yùn)用該模式，使得我們可以在不知道對(duì)象內(nèi)部表示的情況下，按照一定順序（由iterator提供的方法）訪問(wèn)聚合對(duì)象中的各個(gè)元素。
• 由于Iterator模式的以上特性：與聚合對(duì)象耦合，在一定程度上限制了它的廣泛運(yùn)用，一般僅用于底層聚合支持類，如STL的list、vector、stack等容器類及ostream_iterator等擴(kuò)展iterator。

2、迭代器和指針的區(qū)別

• 迭代器不是指針，是類模板，表現(xiàn)的像指針。他只是模擬了指針的一些功能，通過(guò)重載了指針的一些操作符，->、*、++、--等。迭代器封裝了指針，是一個(gè)“可遍歷STL（ Standard Template Library）容器內(nèi)全部或部分元素”的對(duì)象，?本質(zhì)是封裝了原生指針，是指針概念的一種提升（lift），提供了比指針更高級(jí)的行為，相當(dāng)于一種智能指針，他可以根據(jù)不同類型的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)不同的++，--等操作。
• 迭代器返回的是對(duì)象引用而不是對(duì)象的值，所以cout只能輸出迭代器使用*取值后的值而不能直接輸出其自身。

3、迭代器產(chǎn)生原因

• Iterator類的訪問(wèn)方式就是把不同集合類的訪問(wèn)邏輯抽象出來(lái)，使得不用暴露集合內(nèi)部的結(jié)構(gòu)而達(dá)到循環(huán)遍歷集合的效果。

請(qǐng)你說(shuō)一說(shuō)epoll原理

• 調(diào)用順序：
• int epoll_create(int size);
• int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);
• int epoll_wait(int epfd, struct epoll_event *events,int maxevents, int timeout);
• 首先創(chuàng)建一個(gè)epoll對(duì)象，然后使用epoll_ctl對(duì)這個(gè)對(duì)象進(jìn)行操作，把需要監(jiān)控的描述添加進(jìn)去，這些描述如將會(huì)以epoll_event結(jié)構(gòu)體的形式組成一顆紅黑樹(shù)，接著阻塞在epoll_wait，進(jìn)入大循環(huán)，當(dāng)某個(gè)fd上有事件發(fā)生時(shí)，內(nèi)核將會(huì)把其對(duì)應(yīng)的結(jié)構(gòu)體放入到一個(gè)鏈表中，返回有事件發(fā)生的鏈表。

參考鏈接

• epoll使用詳解

?n個(gè)整數(shù)的無(wú)序數(shù)組，找到每個(gè)元素后面比它大的第一個(gè)數(shù)，要求時(shí)間復(fù)雜度為O(N)

#include <iostream> #include <vector> #include <stack> using namespace std;//n個(gè)整數(shù)的無(wú)序數(shù)組，找到每個(gè)元素后面比它大的第一個(gè)數(shù)，要求時(shí)間復(fù)雜度為O(N) vector<int> find(vector<int> &num) {int len = num.size();//空數(shù)組，返回空if(len == 0)return {};stack<int> notFind;//棧：num中還未找到符合條件的元素索引vector<int> res(len, -1);//返回結(jié)果：初始化-1，表示未找到int i = 0;while(i < len)//遍歷數(shù)組{//如果?？栈蛘弋?dāng)前num元素不大于棧頂，將當(dāng)前元素壓棧，索引后移if(notFind.empty() || num[notFind.top()] >= num[i])notFind.push(i++);else//有待處理元素，且num當(dāng)前元素大于棧頂索引元素，符合條件，更新結(jié)果數(shù)組中該索引的值，棧頂出棧。{res[notFind.top()] = num[i];notFind.pop();}}return res; }int main() {vector<int> num = {1, 3, 2, 4, 99, 101, 5, 8};// vector<int> num = {1, 1, 1, 1, 1, 1, 1};// vector<int> num = {};vector<int> res = find(num);for(auto i : res)cout << i << " ";return 0; }

請(qǐng)你回答一下STL里resize和reserve的區(qū)別

• resize()：改變當(dāng)前容器內(nèi)含有元素的數(shù)量(size())，eg: vector<int>v; v.resize(len);v的size變?yōu)閘en,如果原來(lái)v的size小于len，那么容器新增（len-size）個(gè)元素，元素的值為默認(rèn)為0.當(dāng)v.push_back(3);之后，則是3是放在了v的末尾，即下標(biāo)為len，此時(shí)容器是size為len+1；
• reserve()：改變當(dāng)前容器的最大容量（capacity）,它不會(huì)生成元素，只是確定這個(gè)容器允許放入多少對(duì)象，如果reserve(len)的值大于當(dāng)前的capacity()，那么會(huì)重新分配一塊能存len個(gè)對(duì)象的空間，然后把之前v.size()個(gè)對(duì)象通過(guò)copy construtor復(fù)制過(guò)來(lái)，銷毀之前的內(nèi)存；
• vector 的reserve增加了vector的capacity，但是它的size沒(méi)有改變！而resize改變了vector的capacity同時(shí)也增加了它的size！
• 原因如下： ?reserve是容器預(yù)留空間，但在空間內(nèi)不真正創(chuàng)建元素對(duì)象，所以在沒(méi)有添加新的對(duì)象之前，不能引用容器內(nèi)的元素。加入新的元素時(shí)，要調(diào)用push_back()/insert()函數(shù)。
• ?resize是改變?nèi)萜鞯拇笮?#xff0c;且在創(chuàng)建對(duì)象，因此，調(diào)用這個(gè)函數(shù)之后，就可以引用容器內(nèi)的對(duì)象了，因此當(dāng)加入新的元素時(shí)，用operator[]操作符，或者用迭代器來(lái)引用元素對(duì)象。此時(shí)再調(diào)用push_back()函數(shù)，是加在這個(gè)新的空間后面的。
• resize增加大的容量超過(guò)reserve，會(huì)將capacity和size一樣
• resize減少容量 不會(huì)影響到capacity
• 通過(guò) shrink_to_fit 將capacity保持和size一致的大小

參考鏈接

• vector::shrink_to_fit()

測(cè)試代碼

#include <iostream> #include <vector> using namespace std; int main() {vector<int> a;a.reserve(100);a.resize(50);cout<<a.size()<<" "<<a.capacity()<<endl;//50 100a.resize(150);cout<<a.size()<<" "<<a.capacity()<<endl;//150 150a.reserve(50);cout<<a.size()<<" "<<a.capacity()<<endl;//150 150a.reserve(200);cout<<a.size()<<" "<<a.capacity()<<endl;//150 200a.resize(50);cout<<a.size()<<" "<<a.capacity()<<endl;//50 200a.shrink_to_fit();cout<<a.size()<<" "<<a.capacity()<<endl;//50 50 }

請(qǐng)你說(shuō)一說(shuō)stl里面set和map怎么實(shí)現(xiàn)的

• 集合，所有元素都會(huì)根據(jù)元素的值自動(dòng)被排序，且不允許重復(fù)。
• 底層實(shí)現(xiàn)：紅黑樹(shù)
• set 底層是通過(guò)紅黑樹(shù)（RB-tree）來(lái)實(shí)現(xiàn)的，由于紅黑樹(shù)是一種平衡二叉搜索樹(shù)，自動(dòng)排序的效果很不錯(cuò)，所以標(biāo)準(zhǔn)的 STL 的 set 即以 RB-Tree 為底層機(jī)制。又由于 set 所開(kāi)放的各種操作接口，RB-tree 也都提供了，所以幾乎所有的 set 操作行為，都只有轉(zhuǎn)調(diào)用 RB-tree 的操作行為而已。
• 適用場(chǎng)景：有序不重復(fù)集合
• map映射。map 的所有元素都是 pair，同時(shí)擁有實(shí)值（value）和鍵值（key）。pair 的第一元素被視為鍵值，第二元素被視為實(shí)值。所有元素都會(huì)根據(jù)元素的鍵值自動(dòng)被排序。不允許鍵值重復(fù)。
• 底層：紅黑樹(shù)
• 適用場(chǎng)景：有序鍵值對(duì)不重復(fù)映射

總結(jié)

以上是生活随笔為你收集整理的牛客网C++面经 容器和算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。