C++?Boost?CircularBuffer算法超詳細(xì)精講
提要
庫(kù) Boost.CircularBuffer 提供了一個(gè)循環(huán)緩沖區(qū),它是一個(gè)具有以下兩個(gè)基本屬性的容器:
- 循環(huán)緩沖區(qū)的容量是恒定的,由您設(shè)置。當(dāng)您調(diào)用成員函數(shù)(例如 push_back())時(shí),容量不會(huì)自動(dòng)更改。只有您可以更改循環(huán)緩沖區(qū)的容量。循環(huán)緩沖區(qū)的大小不能超過(guò)您設(shè)置的容量。
- 盡管容量不變,但您可以隨時(shí)調(diào)用 push_back() 將元素插入循環(huán)緩沖區(qū)。如果已達(dá)到最大大小并且循環(huán)緩沖區(qū)已滿,則將覆蓋元素。
當(dāng)可用內(nèi)存量有限并且您需要防止容器任意增長(zhǎng)時(shí),循環(huán)緩沖區(qū)是有意義的。另一個(gè)例子是連續(xù)數(shù)據(jù)流,隨著新數(shù)據(jù)的可用,舊數(shù)據(jù)變得無(wú)關(guān)緊要。通過(guò)覆蓋舊數(shù)據(jù)自動(dòng)重用內(nèi)存。
要使用 Boost.CircularBuffer 中的循環(huán)緩沖區(qū),請(qǐng)包含頭文件 boost/circular_buffer.hpp。此頭文件定義類 boost::circular_buffer。
示例 16.1。使用 boost::circular_buffer
#include <boost/circular_buffer.hpp> #include <iostream> int main() { typedef boost::circular_buffer<int> circular_buffer; circular_buffer cb{3}; std::cout << cb.capacity() << '\n'; std::cout << cb.size() << '\n'; cb.push_back(0); cb.push_back(1); cb.push_back(2); std::cout << cb.size() << '\n'; cb.push_back(3); cb.push_back(4); cb.push_back(5); std::cout << cb.size() << '\n'; for (int i : cb) std::cout << i << '\n'; }
boost::circular_buffer 是一個(gè)模板,必須用類型實(shí)例化。例如,示例 16.1 中的循環(huán)緩沖區(qū) cb 存儲(chǔ) int 類型的數(shù)字。
循環(huán)緩沖區(qū)的容量是在實(shí)例化類時(shí)指定的,而不是通過(guò)模板參數(shù)。 boost::circular_buffer 的默認(rèn)構(gòu)造函數(shù)創(chuàng)建一個(gè)容量為零的緩沖區(qū)。另一個(gè)構(gòu)造函數(shù)可用于設(shè)置容量。在示例 16.1 中,緩沖區(qū) cb 具有三個(gè)元素的容量。
可以通過(guò)調(diào)用 capacity() 來(lái)查詢循環(huán)緩沖區(qū)的容量。在示例 16.1 中,capacity() 將返回 3。
容量不等于存儲(chǔ)元素的數(shù)量。雖然 capacity() 的返回值是常數(shù),但 size() 返回緩沖區(qū)中元素的數(shù)量,這可能不同。 size() 的返回值始終介于 0 和循環(huán)緩沖區(qū)的容量之間。
示例 16.1 在第一次調(diào)用 size() 時(shí)返回 0,因?yàn)榫彌_區(qū)不包含任何數(shù)據(jù)。調(diào)用 push_back() 三次后,緩沖區(qū)包含三個(gè)元素,第二次調(diào)用 size() 將返回 3。再次調(diào)用 push_back() 不會(huì)導(dǎo)致緩沖區(qū)增長(zhǎng)。這三個(gè)新數(shù)字會(huì)覆蓋之前的三個(gè)數(shù)字。因此,size() 在第三次調(diào)用時(shí)會(huì)返回 3。
作為驗(yàn)證,存儲(chǔ)的數(shù)字會(huì)在示例 16.1 的末尾寫入標(biāo)準(zhǔn)輸出。輸出包含數(shù)字 3、4 和 5,因?yàn)橄惹按鎯?chǔ)的數(shù)字已被覆蓋。
示例 16.2。 boost::circular_buffer 的各種成員函數(shù)
#include <boost/circular_buffer.hpp> #include <iostream> int main() { typedef boost::circular_buffer<int> circular_buffer; circular_buffer cb{3}; cb.push_back(0); cb.push_back(1); cb.push_back(2); cb.push_back(3); std::cout << std::boolalpha << cb.is_linearized() << '\n'; circular_buffer::array_range ar1, ar2; ar1 = cb.array_one(); ar2 = cb.array_two(); std::cout << ar1.second << ";" << ar2.second << '\n'; for (int i : cb) std::cout << i << '\n'; cb.linearize(); ar1 = cb.array_one(); ar2 = cb.array_two(); std::cout << ar1.second << ";" << ar2.second << '\n'; }
示例 16.2 使用了其他容器中不存在的成員函數(shù) is_linearized()、array_one()、array_two() 和 linearize()。這些成員函數(shù)闡明了循環(huán)緩沖區(qū)的內(nèi)部結(jié)構(gòu)。
循環(huán)緩沖區(qū)本質(zhì)上類似于 std::vector。因?yàn)殚_始和結(jié)束的定義很好,所以可以將向量視為傳統(tǒng)的 C 數(shù)組。也就是說(shuō),內(nèi)存是連續(xù)的,第一個(gè)和最后一個(gè)元素總是在最低和最高的內(nèi)存地址。但是,循環(huán)緩沖區(qū)不提供這樣的保證。
盡管談?wù)撗h(huán)緩沖區(qū)的開始和結(jié)束可能聽起來(lái)很奇怪,但它們確實(shí)存在??梢酝ㄟ^(guò)迭代器訪問(wèn)元素,并且 boost::circular_buffer 提供了成員函數(shù),例如 begin() 和 end()。雖然使用迭代器時(shí)不需要關(guān)心開始和結(jié)束的位置,但使用常規(guī)指針訪問(wèn)元素時(shí)情況會(huì)變得有點(diǎn)復(fù)雜,除非你使用 is_linearized()、array_one()、array_two()、和線性化()。
如果循環(huán)緩沖區(qū)的開頭位于最低內(nèi)存地址,則成員函數(shù) is_linearized() 返回 true。在這種情況下,緩沖區(qū)中的所有元素從頭到尾連續(xù)存儲(chǔ)在不斷增加的內(nèi)存地址中,并且可以像傳統(tǒng)的 C 數(shù)組一樣訪問(wèn)元素。
如果 is_linearized() 返回 false,則循環(huán)緩沖區(qū)的開頭不在最低內(nèi)存地址,示例 16.2 中就是這種情況。雖然前三個(gè)元素 0、1 和 2 完全按此順序存儲(chǔ),但第四次調(diào)用 push_back() 將用數(shù)字 3 覆蓋數(shù)字 0。因?yàn)?3 是調(diào)用 push_back() 添加的最后一個(gè)元素,它現(xiàn)在是循環(huán)緩沖區(qū)的新端。現(xiàn)在開始是編號(hào)為 1 的元素,它存儲(chǔ)在下一個(gè)更高的內(nèi)存地址。這意味著元素不再連續(xù)存儲(chǔ)在不斷增加的內(nèi)存地址中。
如果循環(huán)緩沖區(qū)的末尾位于比開頭低的內(nèi)存地址,則可以通過(guò)兩個(gè)傳統(tǒng)的 C 數(shù)組訪問(wèn)元素。為了避免計(jì)算每個(gè)數(shù)組的位置和大小,boost::circular_buffer 提供了成員函數(shù) array_one() 和 array_two()。
array_one() 和 array_two() 都返回一個(gè) std::pair,其第一個(gè)元素是指向相應(yīng)數(shù)組的指針,第二個(gè)元素是大小。 array_one() 訪問(wèn)循環(huán)緩沖區(qū)開頭的數(shù)組,array_two() 訪問(wèn)緩沖區(qū)末尾的數(shù)組。
如果循環(huán)緩沖區(qū)被線性化并且 is_linearized() 返回 true,則也可以調(diào)用 array_two()。但是,由于緩沖區(qū)中只有一個(gè)數(shù)組,因此第二個(gè)數(shù)組不包含任何元素。
為了簡(jiǎn)化問(wèn)題并將循環(huán)緩沖區(qū)視為傳統(tǒng)的 C 數(shù)組,您可以通過(guò)調(diào)用 linearize() 強(qiáng)制重新排列元素。完成后,您可以使用 array_one() 訪問(wèn)所有存儲(chǔ)的元素,而無(wú)需使用 array_two()。
Boost.CircularBuffer 提供了一個(gè)名為 boost::circular_buffer_space_optimized 的附加類。此類也在 boost/circular_buffer.hpp 中定義。盡管此類的使用方式與 boost::circular_buffer 相同,但它在實(shí)例化時(shí)不保留任何內(nèi)存。相反,內(nèi)存是在添加元素時(shí)動(dòng)態(tài)分配的,直到達(dá)到容量為止。刪除元素會(huì)相應(yīng)地釋放內(nèi)存。 boost::circular_buffer_space_optimized 更有效地管理內(nèi)存,因此在某些情況下可能是更好的選擇。例如,如果您需要一個(gè)大容量的循環(huán)緩沖區(qū),它可能是一個(gè)不錯(cuò)的選擇,但您的程序并不總是使用完整的緩沖區(qū)。
到此這篇關(guān)于C++ Boost CircularBuffer算法超詳細(xì)精講的文章就介紹到這了,更多相關(guān)C++ Boost CircularBuffer內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C語(yǔ)言中函數(shù)指針的三種使用方法總結(jié)
這篇文章主要介紹了 C語(yǔ)言中函數(shù)指針的三種使用方法總結(jié)的相關(guān)資料,希望通過(guò)本文大家能夠徹底掌握指針的使用方法,需要的朋友可以參考下2017-10-10C++實(shí)現(xiàn):螺旋矩陣的實(shí)例代碼
螺旋矩陣是指一個(gè)呈螺旋狀的矩陣,它的數(shù)字由第一行開 始到右邊不斷變大,向下變大, 向左變大,向上變大,如此循環(huán)。2013-03-03內(nèi)核線程優(yōu)先級(jí)設(shè)置的方法介紹
本篇文章介紹了,內(nèi)核線程優(yōu)先級(jí)設(shè)置的方法。需要的朋友參考下2013-05-05C++中關(guān)于std::queue?中遇到釋放內(nèi)存錯(cuò)誤的問(wèn)題
這篇文章主要介紹了std::queue中遇到釋放內(nèi)存錯(cuò)誤的問(wèn)題,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2023-07-07C++實(shí)現(xiàn)LeetCode(53.最大子數(shù)組)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(53.最大子數(shù)組),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07