1. 簡(jiǎn)介

C++ 標(biāo)準(zhǔn)容器不夠用，問(wèn)題主要在性能的一些方面。

一方面是小容器，C++ 對(duì)此有特殊優(yōu)化（MSVC有，gcc clang等沒(méi)去看源碼，不確定）的是?，當(dāng)字符串比較短時(shí)，使用的是對(duì)象的內(nèi)置空間來(lái)存儲(chǔ)，當(dāng)字符串較長(zhǎng)時(shí)，就改用動(dòng)態(tài)分配的空間。但其余容器（如?，等）就沒(méi)有此類優(yōu)化了。同時(shí)，標(biāo)準(zhǔn)庫(kù)里也沒(méi)有提供此類容器（例如 boost 的?）。

另一方面是 set 和 map 底層用了紅黑樹(shù)，而有時(shí)候我們需要的是一個(gè)有序連續(xù)序列容器。這類容器對(duì)應(yīng)的是 boost 的??和?。此類容器在小容器的情況下會(huì)比紅黑樹(shù)快一些，搭配 small_vector 極佳。

GitHub 上沒(méi)有我滿意的輕量級(jí)實(shí)現(xiàn)，因此就我來(lái)造這些輪子吧。

https://github.com/Ubpa/UsmallFlat

純頭文件，直接拷貝拖進(jìn)項(xiàng)目里就可以用?；?C++20 實(shí)現(xiàn)。

2. 輪子總覽

這次我造的輪子有

一開(kāi)始叫?，用于表示固定容量 fixed capacity，由于容易產(chǎn)生歧義，故改為主流的?。

• ：固定容量的?，接口上類似?，區(qū)別在于其在對(duì)象內(nèi)有固定大小的空間用于存儲(chǔ)數(shù)據(jù)，但容量有限，不可擴(kuò)充。

• ： 類似?，區(qū)別在于其在對(duì)象內(nèi)有固定大小的空間用于存儲(chǔ)數(shù)據(jù)（用?實(shí)現(xiàn)）。當(dāng)元素個(gè)數(shù)超過(guò)該固定大小時(shí)，會(huì)動(dòng)態(tài)分配空間用于存儲(chǔ)所有數(shù)據(jù)。

• ：類似?，區(qū)別在于其底層并非是紅黑樹(shù)，而是一個(gè)有序數(shù)組，因此可以提供??等接口。

• ：類似?，區(qū)別在于并非是紅黑樹(shù)，而是一個(gè)有序數(shù)組，因此可以提供??等接口。實(shí)際上它是用??實(shí)現(xiàn)的。

以上是四個(gè)核心容器。?容器能用來(lái)實(shí)現(xiàn)非??的容器，因此還有以下容器

• ： 類似?，區(qū)別在于其底層并非是紅黑樹(shù)，而是一個(gè)有序數(shù)組，因此可以提供??等接口。 實(shí)際上它是用??實(shí)現(xiàn)的。

• ：類似?， 區(qū)別在于其底層并非是紅黑樹(shù)，而是一個(gè)有序數(shù)組，因此可以提供??等接口。 實(shí)際上它是用??實(shí)現(xiàn)的。

這里??的指的是這類容器允許用戶使用自己的??作為底層容器。 因此通過(guò)結(jié)合?，，?和?， 又能多出大概 5 * 4 = 20 個(gè)容器。

上述容器的接口遵循標(biāo)準(zhǔn)容器。

關(guān)于 flat 容器的算法復(fù)雜度問(wèn)題，各接口主要用了二分法 + vector，所以復(fù)雜度問(wèn)題上都是挺直觀的，具體可參考 boost 的說(shuō)明?boost | flat_set?等。

3. 使用示例

常用容器為

• ：?+?

• ，，，：?+?

• ，，，：?+?

用法上完全同于標(biāo)準(zhǔn)容器?；局С忠磺?C++11/14/17/20 的接口（除了 set 和 map 的 node 相關(guān)接口，因?yàn)檫@里的容器為 flat，沒(méi)有 node 的概念）。對(duì)于 flat 容器，還額外新增 vector 的接口（data，capacity，front，back，reserve，shrink_to_fit）。

這里就簡(jiǎn)單舉例一下：

4. 總結(jié)

歡迎使用，感謝閱讀！如有錯(cuò)誤，歡迎指正，感謝各位。

整理了一些最新LinuxC/C++服務(wù)器開(kāi)發(fā)/架構(gòu)師面試題、學(xué)習(xí)資料、教學(xué)視頻和學(xué)習(xí)路線腦圖（資料包括C/C++，Linux，golang技術(shù)，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒體，CDN，P2P，K8S，Docker，TCP/IP，協(xié)程，DPDK，ffmpeg等），免費(fèi)分享有需要的可以自行添加學(xué)習(xí)交流群960994558進(jìn)群領(lǐng)?。