模板化循環緩衝區容器

circular_buffer<T, Alloc>

Boost

目錄

描述
介紹性示例
概要
原理
- 線程安全性
- 覆寫操作
- 寫入到一個滿的緩衝區
- 從一個空的緩衝區讀取/刪除
- 迭代器失效
警告
對調試的支持
更多例子
頭文件
模型概念
模板參數
公有類型
構造函數和析構函數
公有成員函數
獨立函數
備註
參見
鳴謝
發佈說明
Circular Buffer
: 循環緩衝區(也稱為 環ringcyclic buffer)。

描 述

術語 循環緩衝區circular buffer 通常指的是內存中的一塊用於保存輸入數據的區域。當緩衝區被填入時,新的數據從緩衝區的開始被寫入,並覆蓋掉舊的數據。(見圖)

circular_buffer 是一個符合STL的容器。它是一種類似於 std::liststd::deque 的序列。它支持隨機訪問迭代器,在緩衝區頭部或尾部的常量時間插入和刪除操作,與 std 算法的互操作能力。circular_buffer 被特別設計為提供固定容量的存儲大小。當其容量被用完時,新插入的元素會覆蓋緩衝區頭部或尾部(取決於使用何種插入操作)的元素。

circular_buffer 僅在創建時、顯式調整容量時,或需要重新調整大小或賦值操作時才進行內存分配。另一方面,還有一個 circular_buffer_space_optimized 可用。它是 circular_buffer 的一個適配器,它不在創建時分配內存,而是在需要時分配內存。

介 紹性示例

以是一個使用 circular_buffer 的簡單例子:

 #include <boost/circular_buffer.hpp>

int main(int /*argc*/, char* /*argv*/[]) {

// 創建一個容量為3個整數的循環緩衝區。
boost::circular_buffer<int> cb(3);

// 插入一些元素到緩衝區。
cb.push_back(1);
cb.push_back(2);
cb.push_back(3);

int a = cb[0]; // a == 1
int b = cb[1]; // b == 2
int c = cb[2]; // c == 3

// 現在緩衝已滿,再插入元素將覆寫最前面的元素。

cb.push_back(4); // 用 4 覆蓋 1.
cb.push_back(5); // 用 5 覆蓋 2.

// 現在緩衝區包含 3, 4 和 5.

a = cb[0]; // a == 3
b = cb[1]; // b == 4
c = cb[2]; // c == 5

// 可以從前端或後端彈出元素。

cb.pop_back(); // 5 被刪除。
cb.pop_front(); // 3 被刪除。

int d = cb[0]; // d == 4

return 0;
}

概要

namespace boost {

template <class T, class Alloc>
class circular_buffer
{
public:
typedef typename Alloc::value_type value_type;
typedef typename Alloc::pointer pointer;
typedef typename Alloc::const_pointer const_pointer;
typedef typename Alloc::reference reference;
typedef typename Alloc::const_reference const_reference;
typedef typename Alloc::difference_type difference_type;
typedef typename Alloc::size_type size_type;
typedef Alloc allocator_type;
typedef implementation-defined const_iterator;
typedef implementation-defined iterator;
typedef boost::reverse_iterator<const_iterator> const_reverse_iterator;
typedef boost::reverse_iterator<iterator> reverse_iterator;
typedef std::pair<pointer, size_type> array_range;
typedef std::pair<const_pointer, size_type> const_array_range;
typedef size_type capacity_type;

explicit circular_buffer(const allocator_type& alloc = allocator_type());
explicit circular_buffer(capacity_type capacity, const allocator_type& alloc = allocator_type());
circular_buffer(size_type n, const_reference item, const allocator_type& alloc = allocator_type());
circular_buffer(capacity_type capacity, size_type n, const_reference item, const allocator_type& alloc = allocator_type());
circular_buffer(const circular_buffer<T, Alloc>& cb);
template <class InputIterator>
circular_buffer(InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());
template <class InputIterator>
circular_buffer(capacity_type capacity, InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());
~circular_buffer();

allocator_type get_allocator() const;
allocator_type& get_allocator();
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
reverse_iterator rbegin();
reverse_iterator rend();
const_reverse_iterator rbegin() const;
const_reverse_iterator rend() const;
reference operator[](size_type index);
const_reference operator[](size_type index) const;
reference at(size_type index);
const_reference at(size_type index) const;
reference front();
reference back();
const_reference front() const;
const_reference back() const;
array_range array_one();
array_range array_two();
const_array_range array_one() const;
const_array_range array_two() const;
pointer linearize();
bool is_linearized() const;
void rotate(const_iterator new_begin);
size_type size() const;
size_type max_size() const;
bool empty() const;
bool full() const;
size_type reserve() const;
capacity_type capacity() const;
void set_capacity(capacity_type new_capacity);
void resize(size_type new_size, const_reference item = value_type());
void rset_capacity(capacity_type new_capacity);
void rresize(size_type new_size, const_reference item = value_type());
circular_buffer<T, Alloc>& operator=(const circular_buffer<T, Alloc>& cb);
void assign(size_type n, const_reference item);
void assign(capacity_type capacity, size_type n, const_reference item);
template <class InputIterator>
void assign(InputIterator first, InputIterator last);
template <class InputIterator>
void assign(capacity_type capacity, InputIterator first, InputIterator last);
void swap(circular_buffer<T, Alloc>& cb);
void push_back(const_reference item = value_type());
void push_front(const_reference item = value_type());
void pop_back();
void pop_front();
iterator insert(iterator pos, const_reference item = value_type());
void insert(iterator pos, size_type n, const_reference item);
template <class InputIterator>
void insert(iterator pos, InputIterator first, InputIterator last);
iterator rinsert(iterator pos, const_reference item = value_type());
void rinsert(iterator pos, size_type n, const_reference item);
template <class InputIterator>
void rinsert(iterator pos, InputIterator first, InputIterator last);
iterator erase(iterator pos);
iterator erase(iterator first, iterator last);
iterator rerase(iterator pos);
iterator rerase(iterator first, iterator last);
void clear();
};

template <class T, class Alloc>
bool operator==(const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs);
template <class T, class Alloc>
bool operator<(const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs);
template <class T, class Alloc>
bool operator!=(const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs);
template <class T, class Alloc>
bool operator>(const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs);
template <class T, class Alloc>
bool operator<=(const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs);
template <class T, class Alloc>
bool operator>=(const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs);
template <class T, class Alloc>
void swap(circular_buffer<T, Alloc>& lhs, circular_buffer<T, Alloc>& rhs);

} // namespace boost

原理

circular_buffer 背後的動機是創建一個可以與STL無縫使用的容器。另外,circular_buffer 的設計受到以下原則的指導:

  1. 對於常見應用具有最大的效率
  2. 適用於多種用途
  3. 緩衝區的行為應盡可能符合直覺
  4. 適合於通過適配器進行特化。(circular_buffer_space_optimized 就是一個適配器的例子)
  5. 易於調試。(詳見 對 調試的支持)

為了達到最高的效率,circular_buffer 將它的元素保存在一片連 續內存中,這樣可以:

  1. 使用固定的內存,不需要隱式或意外的內存分配。
  2. 從前端或後端進行快速的常量時間的插入和刪除元素。
  3. 快速的常量時間的對元素進行隨機訪問。
  4. 適用於實時和對性能有嚴格要求的應用程序。

circular_buffer 的可能應用包括:

circular_buffer 的:

線 程安全性

circular_buffer 的線程安全性與大多數STL實現中的容器的線程安全性相同。即 circular_buffer 不是線程安全的。線程安全僅 在以下情形時被保證:對 circular_buffer 的不同實例進行並發訪問是安全的,對共享的 circular_buffer 進行並發讀訪問是安全的。

如果多個線程訪問同一個 circular_buffer, 且至少有一個線程可能會進行寫訪問,則用戶要負責確保各個線程在訪問容器時互斥。線程間的互斥可以通過對底層的 circular_buffer 操作增加一個鎖獲取和釋放來實現。(請見 有界緩衝區示例)

覆寫操作

覆寫操作發生在當一個元素被插入到一個滿的 circular_buffer 中時 - 舊的元素將被新元素所覆蓋。在正式審查時,曾經對"覆寫某個元素"的精確意義進行過討論。它可能是析構一個原有的元素並接著原地構造一個新元素,也可能是 將新元素賦值到舊元素中。circular_buffer 最終實現了賦值操 作,因為它更為高效。

從被保存元素的業務邏輯觀點來看,析構/構造操作與賦值操作其實是一樣的。但是,在極少見的情形下(如果有)它們之間可能有不同。如果 元素本身需要 以析構/構造操作來替換賦值操作,可能考慮對該元素實現一個賦值操作的包裝器,並改為保存該包裝器。需要注意,保存這個包裝器有一個缺點。對該包裝器的每 次賦值都要調用析構/構造操作 - 不僅是在該包裝器被覆寫時(即緩衝區滿時),也會發生在對被保存包裝器進行移位時(例如,在容器中央插入)。

寫入到 一個滿的緩衝區

當數據源產生的數據多於固定大小緩衝區可以容納的數量時,通常有以下幾種選擇:

  1. 通知數據源等待,直至緩衝區有空間為止(如通過拋出一個溢出異常)。
  2. 如果最舊的數據最為重要,則忽略來自數據源的新數據,直至緩衝區有空間為止。
  3. 如果最新的數據最為重要,則覆寫最舊的數據。
  4. 讓數據產生者負責在寫入數據前檢查緩衝區的大小。

顯然,circular_buffer 實現了第三種選擇。但是它實現其它選擇 - 尤其是前兩個 - 則可能不太明顯。你可能覺得 circular_buffer 應該實現前面三種選項並提供一個機制來在它們之間進行選擇。這種印象是錯的。circular_buffer 被設計並優化為循環的(這意味著在緩衝區滿時將覆寫最舊的數據)。如果有這樣一種控制機制,它只會把事情弄複雜,而且 circular_buffer 的使用也可能會不夠方便。

此外,前兩個選項(還有第四個)並不要求緩衝區是循環的。如果需要前兩個選項,請考慮實現 std::vector 的一個適配器。這種情況下,circular_buffer 不適合用於適配,因為和 std::vector 相比,它要為其循環行為負出一定的開銷。

從 一個空的緩衝區讀取/刪除

當從一個空緩衝區讀取或刪除元素時,緩衝區應可以通知數據消耗者(例如通過拋出一個下溢異常)它沒有元素保存。因為以下兩個原因,circular_buffer 沒有實現這一行為:

  1. 它會引入性能的開銷。
  2. 其它 std 容器也沒有這樣做。

從一個空的 std 容器中讀取或刪除一個元素(如通過調用 front()pop_back())被認為是 bug,circular_buffer 也一樣。數據消耗者在從容器中讀取/刪除元素之前,必須測試它是否為空。不過,從 circular_buffer 讀取時,有一個選項決定 at() 方法在索引超界時是否拋出異常。

迭代器失效

如果一個迭代器所指的元素被刪除或被另一個元素覆寫,通常認為該迭代器將失效。該規則是 對 調試的支持 所強制的,並且被記錄在每一個方法中。不過,有些使用 circular_buffer 的應用可能要求較松的規則:迭代器僅當其指向未初始化內存時才無效。考慮以下例子:

 #define BOOST_CB_DISABLE_DEBUG // 調試支持已關閉,否則代碼將引發運行期錯誤。

#include <boost/circular_buffer.hpp>
#include <assert.h>

int main(int /*argc*/, char* /*argv*/[]) {

boost::circular_buffer<int> cb(3);

cb.push_back(1);
cb.push_back(2);
cb.push_back(3);

boost::circular_buffer<int>::iterator it = cb.begin();

assert(*it == 1);

cb.push_back(4);

assert(*it == 4); // 該迭代器仍指向已初始化的內存。

return 0;
}

該迭代器不再指向原來的元素(從"嚴格"的觀點來看,它被認為是無效的),但它仍然指向內存中同一個有效的位置。 circular_buffer 所支持的對迭代器失效的"寬鬆"定義被認為是實現細節,而不是完整的特性。迭代器依然有效的規則可以由 soft_iterator_invalidation.cpp 中的代碼推斷得到。

警告

circular_buffer 不能用於保存指向動態分配對象的指針。當一個 circular_buffer 變滿時,後來的插入將覆寫已保存的指針 - 這會導致內存洩漏。建議採用智能指針[1]來代替。(任何 std::auto_ptr 容器都被認為是非常危險的[2])

雖然 circular_buffer 的內部是循環的,但它的迭代器不是circular_buffer 的迭代器僅在範圍 [begin(), end()] 內有效。如,迭代器 (begin() - 1)(end() + 1) 均為無效。

對調試的支持

為了幫助程序員避免和發現常見的 bugs, circular_buffer 包括了一些對調試的支持。

circular_buffer 維護了一個有效迭代器列表。一旦任何元素被銷毀,指向該元素的所有迭代器將被從這個列表中刪除,明確失效(設置一個失效標誌)。對調試的支持還包括多個斷 言(BOOST_ASSERT 宏),這樣可以確保 circular_buffer 和它的迭代器在運行期正確使用。當一個無效迭代器被使用時,斷言將報告一個錯誤。顯式的迭代器失效和斷言的使用是一種非常強的調試技術,可以捕捉到大多數 錯誤。

此外,在調試模式下,由 circular_buffer 分配的未初始化內存會用值 0xcc 進行填充。這樣可以幫助程序員在調試代碼時分辨出已初始化和未初始化的內存。詳情請參見源代碼。

對調試的支持僅在調試模式下打開(即在 NDEBUG 未定義時)。也可以通過定義 BOOST_CB_DISABLE_DEBUG 宏來顯式關閉它。

更多的例子

以下例子包含了 circular_buffer 的各種用法。

 #include <boost/circular_buffer.hpp>
#include <numeric>
#include <assert.h>

int main(int /*argc*/, char* /*argv*/[])
{
// 創建一個容量為3的循環緩衝區
boost::circular_buffer<int> cb(3);

// 插入一些元素到循環緩衝區
cb.push_back(1);
cb.push_back(2);

// 斷言
assert(cb[0] == 1);
assert(cb[1] == 2);
assert(!cb.full());
assert(cb.size() == 2);
assert(cb.capacity() == 3);

// 再插入其它元素
cb.push_back(3);
cb.push_back(4);

// 求和
int sum = std::accumulate(cb.begin(), cb.end(), 0);

// 斷言
assert(cb[0] == 2);
assert(cb[1] == 3);
assert(cb[2] == 4);
assert(*cb.begin() == 2);
assert(cb.front() == 2);
assert(cb.back() == 4);
assert(sum == 9);
assert(cb.full());
assert(cb.size() == 3);
assert(cb.capacity() == 3);

return 0;
}

circular_buffer 的容量為3個 int. 因此,緩衝區的大小不會超過3。算法 accumulate 計算被存元素的總和。circular_buffer 的語義可以從斷言進行推斷。

有 界緩衝區示例

有界緩衝區通常用於生產者-消費者模式,其中生產者線程產生一些事項並將它們保存在容器中,而消費者線程從容器中取出這些事項並處理它 們。有界緩衝區必須保證當容器滿時,生產者不會插入,同樣當容器空時消費者不會取出,並且每個事項正好被一個消費者消耗。

下例示範了 circular_buffer 如何被用作有界緩衝區的底層容器。

 #include <boost/circular_buffer.hpp>
#include <boost/thread/mutex.hpp>
#include <boost/thread/condition.hpp>
#include <boost/thread/thread.hpp>
#include <boost/progress.hpp>
#include <boost/bind.hpp>

template <class T>
class bounded_buffer {
public:

typedef boost::circular_buffer<T> container_type;
typedef typename container_type::size_type size_type;
typedef typename container_type::value_type value_type;

explicit bounded_buffer(size_type capacity) : m_unread(0), m_container(capacity) {}

void push_front(const value_type& item) {
boost::mutex::scoped_lock lock(m_mutex);
m_not_full.wait(lock, boost::bind(&bounded_buffer<value_type>::is_not_full, this));
m_container.push_front(item);
++m_unread;
lock.unlock();
m_not_empty.notify_one();
}

void pop_back(value_type* pItem) {
boost::mutex::scoped_lock lock(m_mutex);
m_not_empty.wait(lock, boost::bind(&bounded_buffer<value_type>::is_not_empty, this));
*pItem = m_container[--m_unread];
lock.unlock();
m_not_full.notify_one();
}

private:
bounded_buffer(const bounded_buffer&); // 禁止複製構造函數
bounded_buffer& operator = (const bounded_buffer&); // 禁止賦值操作符

bool is_not_empty() const { return m_unread > 0; }
bool is_not_full() const { return m_unread < m_container.capacity(); }

size_type m_unread;
container_type m_container;
boost::mutex m_mutex;
boost::condition m_not_empty;
boost::condition m_not_full;
};

bounded_buffer 使用了 Boost ThreadsBoost Bind 庫。

方法 push_front() 被生產者線程調用以插入新事項到緩衝區中。該方法鎖住互斥體並等待至有空間容納新事項。(互斥體在等待期間會被解鎖,當條件滿足時再重新鎖住)。如果緩衝 區中有空間可用,執行將繼續,該方法插入新事項到 circular_buffer 的尾部。然後遞增未讀項計數並解鎖互斥體(如果在互斥體解鎖前拋出異常,互斥體會由 scoped_lock 的析構函數自動解鎖)。最後該方法通知正在等待新事項被插入到緩衝區中的消費者線程。

方法 pop_back() 被消費者線程調用以從緩衝區讀取一個事項。該方法鎖住互斥體並等待至緩衝區中有未讀項。如果有至少一個未讀項,該方法就遞減未讀項計數並從 circular_buffer 讀出下一個事項。然後解鎖互斥體並通知正在等待緩衝區有空間容納新事項的生產者線程。

方法 pop_back() 並不刪除事項,被讀事項保留在 circular_buffer 中,當 circular_buffer 滿時它將被新事項(由生產者插入)所替換。該方法比顯式調用 circular_bufferpop_back() 方法刪除該事項更為高效。這種方法基於以下假設,即新事項的賦值(替換)操作比析構(刪除)舊項並原地構造(插入)新項更為高效。

要和基於不同容器的有界緩衝區進行比較,可以編譯並運行 bounded_buffer_comparison.cpp. 該測試將表明,基於 circular_buffer 的有界緩衝區比基於 std::deque 的有界緩衝區更為高效。(在實踐中的結果可能不一樣,因為該測試會受到如即時CPU負荷等外部因素的影響)。

頭文件

circular_buffer 定義於文件 boost/circular_buffer.hpp 中。頭文件 boost/circular_buffer_fwd.hpp 中有 circular_buffer 的前向聲明。

模型概念

隨 機訪問容器Random Access Container, 前 端插入序列Front Insertion Sequence後 端插入序列Back Insertion Sequence

模板參 數

參數 說明 缺省值

公有類型

類型 說明
value_type 保存在 circular_buffer 中的元素的類型。
pointer 元素的指針類型。
const_pointer 元素的常量指針類型。
reference 元素的引用類型。
const_reference 元素的常量引用類型。
difference_type 距離類型。(用於表示兩個迭代器間距離的有符號整數類型)
size_type 大小類型。(用於表示容器距離類型的任一非負值的無符號整數類型)
allocator_type circular_buffer 中使用的分配器類型。
const_iterator 用於遍歷 circular_buffer 的常量(隨機訪問)迭代器
iterator 用於遍歷 circular_buffer 的(隨機訪問)迭代器
const_reverse_iterator 用於反向遍歷 circular_buffer 的常量迭代器。
reverse_iterator 用於反向遍歷 circular_buffer 的迭代器。
array_range 數組範圍。(一個 std::pair 的 typedef,其 first 元素是指向數組頭部的指針,second 元素表示數組的大小)
const_array_range 常量數組的範圍。(一個 std::pair 的 typedef,其 first 元素是指向常量數組頭部的指針,second 元素表示常量數組的大小)
capacity_type 容量類型。(和 size_type 一樣 - 為了和 circular_buffer_space_optimized 的一致性而定義)

構 造函數和析構函數

explicit circular_buffer(const allocator_type& alloc = allocator_type());

以最大容量創建一個空的 circular_buffer.
作用:
capacity() == max_size() && size() == 0
參數:
alloc
分配器。
拋出:
如果內存耗盡則拋出一個分配錯誤(如果使用標準分配器則為 std::bad_alloc)。
複雜度:
常數。
警告:
該構造函數只是為了與STL容器的定義兼容而定義的。應避免使用它,因為它會分配很大的內存空間(取決於分配器的 max_size())。
explicit circular_buffer(capacity_type capacity, const allocator_type& alloc = allocator_type());

以指定容量創建一個空的 circular_buffer.
作用:
capacity() == capacity && size() == 0
參數:
capacity
可以保存在 circular_buffer 中的元素最大數量。
alloc
分配器。
拋出:
如果內存耗盡則拋出一個分配錯誤(如果使用標準分配器則為 std::bad_alloc)。
複雜度:
常數。
circular_buffer(size_type n, const_reference item, const allocator_type& alloc = allocator_type());

以指定容量創建一個滿的 circular_buffer,並填入 itemn 份拷貝。
作用:
capacity() == n && full() && (*this)[0] == item && (*this)[1] == item && ... && (*this)[n - 1] == item
參數:
n
要填入到被創建 circular_buffer 中的元素數量。
item
要填入到被創建 circular_buffer 中的元素。
alloc
分配器。
拋出:
如果內存耗盡則拋出一個分配錯誤(如果使用標準分配器則為 std::bad_alloc)。
T::T(const T&) 拋出的任何異常。
複雜度:
線性(與 n 相關)。
circular_buffer(capacity_type capacity, size_type n, const_reference item, const allocator_type& alloc = allocator_type());

以指定容量創建一個 circular_buffer,並填入 itemn 份拷貝。
前提條件:
capacity >= n
作用:
capacity() == capacity && size() == n && (*this)[0] == item && (*this)[1] == item && ... && (*this)[n - 1] == item
參數:
capacity
被創建 circular_buffer 的容量。
n
要填入到被創建 circular_buffer 中的元素數量。
item
要填入到被創建 circular_buffer 中的元素。
alloc
分配器。
拋出:
如果內存耗盡則拋出一個分配錯誤(如果使用標準分配器則為 std::bad_alloc)。
T::T(const T&) 拋出的任何異常。
複雜度:
線性(與 n 相關)。
circular_buffer(const circular_buffer<T,Alloc>& cb);

複製構造函數。

創建指定 circular_buffer 的一個拷貝。

作用:
*this == cb
參數:
cb
被複製的 circular_buffer.
拋出:
如果內存耗盡則拋出一個分配錯誤(如果使用標準分配器則為 std::bad_alloc)。
T::T(const T&) 拋出的任何異常。
複雜度:
線性(與 cb 的大小相關)。
template <class InputIterator>
circular_buffer(InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());


創建一個滿的 circular_buffer,以指定區間的拷貝填充。
前提條件:
有效區間 [first, last).
firstlast 必須符合 輸 入迭代器InputIterator 的要求。
作用:
capacity() == std::distance(first, last) && full() && (*this)[0]== *first && (*this)[1] == *(first + 1) && ... && (*this)[std::distance(first, last) - 1] == *(last - 1)
參數:
first
被複製的區間的開始。
last
被複製的區間的結束。
alloc
分配器。
拋出:
如果內存耗盡則拋出一個分配錯誤(如果使用標準分配器則為 std::bad_alloc)。
T::T(const T&) 拋出的任何異常。
複雜度:
線性(與 std::distance(first, last)& nbsp;相關)。
template <class InputIterator>
circular_buffer(capacity_type capacity, InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());


創建一個指定容量的 circular_buffer,以指定區間的拷貝填充。
前提條件:
有效區間 [first, last).
firstlast 必須符合 輸 入迭代器InputIterator 的要求。
作用:
capacity() == capacity && size() <= std::distance(first, last) && (*this)[0]== *(last - capacity) && (*this)[1] == *(last - capacity + 1) && ... && (*this)[capacity - 1] == *(last - 1)
如果被複製的區間 [first, last) 中的元素數量大於指定的容量,則只有區間 [last - capacity, last) 中的元素被複製。
參數:
capacity
被創建的 circular_buffer 的容量。
first
被複製的區間的開始。
last
被複製的區間的結束。
alloc
分配器。
拋出:
如果內存耗盡則拋出一個分配錯誤(如果使用標準分配器則為 std::bad_alloc)。
T::T(const T&) 拋出的任何異常。
複雜度:
線性(與 std::distance(first, last) 相關; 如果 InputIterator隨 機訪問迭代器RandomAccessIterator 則與 min[capacity, std::distance(first, last)] 相關)。
~circular_buffer();

析構函數。

銷毀 circular_buffer.

拋出:
無。
迭代器失效:
所有指向 circular_buffer 的迭代器(包括等於 end() 的迭代器)均失效。
複雜度:
線性(與 circular_buffer 的大小相關)。
參見:
clear()

公有成員函數

allocator_type get_allocator() const;

取出分配器。
返回:
分配器。
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
不會令任何迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
 獲取分配器引用的 get_allocator()
allocator_type& get_allocator();

取出分配器的引用。
返回:
分配器的一個引用。
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
不會令任何迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
說明:
加入這一方法是為了優化帶狀態分配器的獲取,雖然使用帶狀態分配器在STL中是不好的。
參見:
get_allocator() const
iterator begin();

取得指向 circular_buffer 頭部的迭代器。
返回:
一個隨機訪問迭代器,指向 circular_buffer 的第一個元素。如果 circular_buffer 為空則返回一個等於 end() 的迭代器。
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
不會令任何迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
end(), rbegin(), rend()
iterator end();

取得指向 circular_buffer 尾部的迭代器。
返回:
一個隨機訪問迭代器,指向 circular_buffer 最後一個元素的下一個位置。如果 circular_buffer 為空則返回一個等於 begin() 的迭代器。
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
不會令任何迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
begin(), rbegin(), rend()
const_iterator begin() const;

取得指向 circular_buffer 頭部的常量迭代器。
返回:
一個常量隨機訪問迭代器,指向 circular_buffer 的第一個元素。如果 circular_buffer 為空則返回一個等於 end() const  的迭代器。
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
不會令任何迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
end() const, rbegin() const, rend() const
const_iterator end() const;

取得指向 circular_buffer 尾部的常量迭代器。
返回:
一個常量隨機訪問迭代器,指向 circular_buffer 最後一個元素的下一個位置。如果 circular_buffer 為空則返回一個等於 begin() const 的迭代器。
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
不會令任何迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
begin() const, rbegin() const, rend() const
reverse_iterator rbegin();

取得指向"反向" circular_buffer 頭部的迭代器。
返回:
一個反向隨機訪問迭代器,指向 circular_buffer 的最後一個元素。如果 circular_buffer 為空則返回一個等於 rend() 的迭代器。
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
不會令任何迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
rend(), begin(), end()
reverse_iterator rend();

取得指向"反向" circular_buffer 的尾部的迭代器。
返回:
一個反向隨機訪問迭代器,指向 circular_buffer 第一個元素的前一個位置。如果 circular_buffer 為空則返回一個等於 rbegin() 的迭代器。
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
不會令任何迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
rbegin(), begin(), end()
const_reverse_iterator rbegin() const;

取得指向"反向" circular_buffer 頭部的常量迭代器。
返回:
一個常量反向隨機訪問迭代器,指向 circular_buffer 的最後一個元素。如果 circular_buffer 為空則返回一個等於 rend() const 的迭代器。
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
不會令任何迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
rend() const, begin() const, end() const
const_reverse_iterator rend() const;

取得指向"reversed" circular_buffer 尾部的常量迭代器。
返回:
一個常量反向隨機訪問迭代器,指向 circular_buffer 第一個元素的前一個位置。如果 circular_buffer 為空則返回一個等於 rbegin() const 的迭代器。
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
不會令任何迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
rbegin() const, begin() const, end() const
reference operator[](size_type index);

取得在 index 位置上的元素。
前提條件:
0 <= index && index < size()
參數:
index
元素的位置。
返回:
位於 index 位置上的元素的引用。
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
不會令任何迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
at()
const_reference operator[](size_type index) const;

取得位於 index 位置的元素。
前提條件:
0 <= index && index < size()
參數:
index
元素的位置。
返回:
位於 index 位置的元素的常量引用。
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
不會令任何迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
at() const
reference at(size_type index);

取得位於 index 位置的元素。
參數:
index
元素的位置。
返回:
位於 index 位置的元素的引用。
拋出:
std::out_of_rangeindex 無效(若 index >= size())。
異常安全性:
強。
迭代器失效:
不會令任何迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
operator[]
const_reference at(size_type index) const;

取得位於 index 位置的元素。
參數
index
元素的位置。
返回:
位於 index 位置的元素的常量引用。
拋出:
std::out_of_rangeindex 無效(若 index >= size())。
異常安全性:
強。
迭代器失效:
不會令任何迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
operator[] const
reference front();

取得第一個元素。
前提條件:
!empty()
返回:
circular_buffer 的第一個元素的引用。
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
不會令任何迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
back()
reference back();

取得最後一個元素。
前提條件:
!empty()
返回:
circular_buffer 最後一個元素的引用。
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
不會令任何迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
front()
const_reference front() const;

取得第一個元素。
前提條件:
!empty()
返回:
circular_buffer 第一個元素的常量引用。
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
不會令任何迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
back() const
const_reference back() const;

取得最後一個元素。
前提條件:
!empty()
返回:
circular_buffer 最後一個元素的常量引用。
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
不會令任何迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
front() const
array_range array_one();

取得內部緩衝區的首個連續數組。

該方法與 array_two() 結合可用於將所存數據以數組方式傳遞給傳統的 C API。假設有一個容量為10的 circular_buffer, 包含7個字符 'a', 'b', ..., 'g',其中 buff[0] == 'a', buff[1] == 'b', ... buff[6] == 'g':

circular_buffer<char> buff(10);

其內部的表示通常不是線性的,內部緩衝區的狀態可能如下:

|e|f|g| | | |a|b|c|d|
end ---^
begin -------^


其中 |a|b|c|d| 表示"數組一",|e|f|g| 表示"數組二",而 | | | | 為空閒空間。
現在考慮一個典型的C風格函數,它寫入數據到一個文件中:

int write(int file_desc, char* buff, int num_bytes);

有兩種方法將 circular_buffer 中的內容寫到一個文件中。要麼使用 array_one()array_two() 方法並調用 write 函數兩次:

array_range ar = buff.array_one();
write(file_desc, ar.first, ar.second);
ar = buff.array_two();
write(file_desc, ar.first, ar.second);


或者使用 linearize() 方法:

write(file_desc, buff.linearize(), buff.size());

由於 array_one()array_two() 方法的複雜度為常數,所以當 write 方法較為"廉價"時第一個選擇更適合。另一方面,當調用 write 方法較為"昂貴"時第二個選擇更為適合,linearize() 方法的調用是線性複雜度的。

返回:
內部緩衝區首個連續數組的數組區間。當 circular_buffer 為空時,返回數組的大小為 0.
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
不會令任何迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
警告:
通常,調用任何修改 circular_buffer 內部狀態的方法都可能會破壞內部緩衝區的線性,並令得由 array_one()array_two()& nbsp;(以及它們的常量版本)所返回的數組區間失效。
說明:
當內部緩衝區為線性時,如 |a|b|c|d|e|f|g| | | | ,"數組一"代表 |a|b|c|d|e|f|g| 而"數組二"不存在(array_two() 方法返回一個大小為 0 的數組)。
參見:
array_two(), linearize()
array_range array_two();

取得內部緩衝區的第二個連續數組。

該方法與 array_one() 結合可用於將所存數據以數組方式傳遞給傳統的 C API。

返回:
內部緩衝區的第二個連續數組的數組區間。當內部緩衝區為線性時或 circular_buffer 為空時,返回數組的大小為 0.
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
不會令任何迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
array_one()
const_array_range array_one() const;

取得內部緩衝區的首個連續數組。

該方法與 array_two() const 結合可用於將所存數據以數組方式傳遞給傳統的 C API。

返回:
內部緩衝區的首個連續數組的數組區間。當 circular_buffer 為空時,返回數組的大小為 0.
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
不會令任何迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
array_two() const; array_one() 詳細說明了如何傳遞數據給傳統的 C API.
const_array_range array_two() const;

取得內部緩衝區的第二個連續數組。

該方法與 array_one() const 結合可用於將所存數據以數組方式傳遞給傳統的 C API。

返回:
內部緩衝區的第二個連續數組的數組區間。當內部緩衝區為線性時或 circular_buffer 為空時,返回數組的大小為 0.
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
不會令任何迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
array_one() const
pointer linearize();

將內部緩衝區線性化至一個連續數組。

該方法用於將所存數據以數組方式傳遞給傳統的 C API。

作用:
&(*this)[0] < &(*this)[1] < ... < &(*this)[size() - 1]
返回:
指向數組起始的指針,或者如果為空則返回 0.
拋出:
T::T(const T&) 拋出的任何異常。
T::operator = (const T&) 拋出的任何異常。
異常安全性:
基本;如果在拋出一節中所列的操作不拋出的話則沒有異常拋出。
迭代器失效:
所有指向 circular_buffer 的迭代器均失效(除了等於 end() 的迭代器);如果後續條件(見作用)在調用之前已滿足則不會令任何迭代器失效。
複雜度:
線性(與 circular_buffer 的大小相關);如果後續條件(見作用)已滿足則為常數複雜度。
警告:
通常,調用任何會修改 circular_buffer 內部狀態的方法都可能會破壞內部緩衝區的線性,並令得返回的指針失效。
參見:
array_one()array_two() 給出了另一個方法來傳遞數據給傳統的 C API;is_linearized(), rotate(const_iterator)
bool is_linearized() const;

這個 circular_buffer 是線性化的嗎?
返回:
如果內部緩衝區被線性化到一個連續數組(即 circular_buffer 符合條件 &(*this)[0] < &(*this)[1] < ... < &(*this)[size() - 1])則返回 true;否則返回 false
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
不會令任何迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。 
參見:
linearize(), array_one(), array_two()
void rotate(const_iterator new_begin);

旋轉 circular_buffer 中的元素。

一個比 std::rotate 更為高效的實現。

先驗條件:
new_begin 是一個指向 circular_buffer 末尾以外地方的有效迭代器。
作用:
假設在調用該方法之前有:

m == std::distance(new_begin, end())
n == std::distance(begin(), new_begin)
val_0 == *new_begin, val_1 == *(new_begin + 1), ... val_m == *(new_begin + m)
val_r1 == *(new_begin - 1), val_r2 == *(new_begin - 2), ... val_rn == *(new_begin - n)

則在調用之後有:

val_0 == (*this)[0] && val_1 == (*this)[1] && ... && val_m == (*this)[m - 1] && val_r1 == (*this)[m + n - 1] && val_r2 == (*this)[m + n - 2] && ... && val_rn == (*this)[m]
參數:
new_begin
新的起始點。
拋出:
T::T(const T&) 拋出的任何異常。
T::operator = (const T&) 拋出的任何異常。
異常安全性:
基本;如果 circular_buffer 為滿或 new_begin 指向 begin() 或在拋出一節中給出的操作沒有拋出,則不拋出。
迭代器失效:
如果 m < n,則指向最後 m 個元素的迭代器失效(包括 new_begin,但不包括等於 end() 的迭代器),否則指向頭 n 個元素的迭代器失效;如果 circular_buffer 為滿則沒有迭代器失效。
複雜度:
線懷(與 std::min(m, n) 相關);如果 circular_buffer 為滿則為常數。
參見:
std::rotate
size_type size() const;

取得當前保存在 circular_buffer 中的元素數量。
返回:
保存在 circular_buffer 中的元素數量。
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
不會令任何迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
capacity(), max_size(), reserve(), resize(size_type, const_reference)
size_type max_size() const;

取得 circular_buffer 的最大可能大小或容量(取決於分配器的 max_size())。
返回:
可以設置的 circular_buffer 的最大大小/容量。
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
不會令任何迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
size(), capacity(), reserve()
bool empty() const;

circular_buffer 是否為空?
返回:
true 如果 circular_buffer 中沒有元素;否則返回 false.
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
不會令任何迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
full()
bool full() const;

circular_buffer 是否已滿?
返回:
true 如果保存在 circular_buffer 中的元素數量等於 circular_buffer 的容量;否則返回 false.
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
不會令任何迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
empty()
size_type reserve() const;

取得可以插入到 circular_buffer 中而不覆寫任何已存元素的最大元素數量。
返回:
capacity() - size()
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
不會令任何迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
capacity(), size(), max_size()
capacity_type capacity() const;

取得 circular_buffer 的容量。
返回:
可以保存在 circular_buffer 的最大元素數量。
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
不會令任何迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
reserve(), size(), max_size(), set_capacity(capacity_type)
void set_capacity(capacity_type new_capacity);

修改 circular_buffer 的容量。
作用:
capacity() == new_capacity && size() <= new_capacity

如果當前保存在 circular_buffer 中的元素數量大於希望設置的新容量,則 [size() - new_capacity]最後的元素將被刪除,新的 size 將等於 new_capacity.
參數:
new_capacity
新的容量。
拋出:
如果內存耗盡則拋出一個內存分配錯誤(std::bad_alloc 如果使用標準分配器)。
T::T(const T&) 拋出的任何異常。
異常安全性:
強。
迭代器失效:
指向 circular_buffer 的所有迭代器均失效(除了等於 end() 的迭代器),如果新的容量與原有容量不同。
複雜度:
線性(與 min[size(), new_capacity] 相關)。
參見:
rset_capacity(capacity_type), resize(size_type, const_reference)
void resize(size_type new_size, const_reference item = value_type());

修改 circular_buffer 的大小。
作用:
size() == new_size && capacity() >= new_size

如果新的大小大於當前大小,則 item 的多個拷貝被插入到 circular_buffer後端以達到希望的大小。如 果最終的大小超出當前的容量,則將容量設置為 new_size.
如果當前保存在 circular_buffer 中的元素數量大於希望的新大小,則最後 [size() - new_size] 個元素將被刪除。(容量保持不變)
參數:
new_size
新的大小。
item
用於填充 circular_buffer 的元素,以達到所要求的大小(見作用)。
拋出:
如果內存耗盡則拋出一個內存分配錯誤(std::bad_alloc 如果使用標準分配器)。
T::T(const T&) 拋出的任何異常。
異常安全性:
基本。
迭代器失效:
指向 circular_buffer 的所有迭代器均失效(除了等於 end() 的迭代器),如果新的大小大於當前容量。如果新的大小小於當前大小則指向被刪除元素的迭代器失效。否則沒有迭代器失效。
複雜度:
線性(與 circular_buffer 的新大小相關)。
參見:
rresize(size_type, const_reference), set_capacity(capacity_type)
void rset_capacity(capacity_type new_capacity);

修改 circular_buffer 的容量。
作用:
capacity() == new_capacity && size() <= new_capacity

如果當前保存在 circular_buffer 中的元素數量大於所希望的新容量,則 [size() - new_capacity] 個元素被刪除,新的大小等於 new_capacity.
Parameter(s):
new_capacity
新的容量。
拋出:
如果內存耗盡則拋出一個內存分配錯誤(std::bad_alloc 如果使用標準分配器)。
T::T(const T&) 拋出的任何異常。
異常安全性:
強。
迭代器失效:
如果新的容量不同於原有容量,則指向 circular_buffer 的所有迭代器均失效(除了等於 end() 的迭代器)。
複雜度:
線性(與 min[size(), new_capacity] 相關)。
參見:
set_capacity(capacity_type), rresize(size_type, const_reference)
void rresize(size_type new_size, const_reference item = value_type());

修改 circular_buffer 的大小。
作用:
size() == new_size && capacity() >= new_size

如果新的大小大於當前大小,則 item 的多份拷貝將被插入到 circular_buffer前端以達到所希望的大小。 如果所得的大小超過當前的容量,則容量被設置為 new_size.
如果當前保存在 circular_buffer 中的元素數量大於所希望的新大小,則 [size() - new_size] 個元素將被刪除。(容量保持不變)
參數:
new_size
新的大小。
item
被填充到 circular_buffer 中的元素,以達到所要求的大小。(見作用)
拋出:
如果內存耗盡則拋出一個內存分配錯誤(std::bad_alloc 如果使用標準分配器)。
T::T(const T&) 拋出的任何異常。
異常安全性:
基本。
迭代器失效:
如果新的大小大於當前容量,則指向 circular_buffer 的所有迭代器均失效(除了等於 end() 的迭代器)。如果新的大小小於原有大小,則指向被刪除元素的迭代器失效。否則沒有迭代器失效。
複雜度:
線性(與 circular_buffer 的新大小相關)。
參見:
resize(size_type, const_reference), rset_capacity(capacity_type)
circular_buffer<T,Alloc>& operator=(const circular_buffer<T,Alloc>& cb);

賦值操作符。

使得 circular_buffer 成為給定 circular_buffer 的一個拷貝。

作用:
*this == cb
參數:
cb
被複製的 circular_buffer.
拋出:
如果內存耗盡則拋出一個內存分配錯誤(std::bad_alloc 如果使用標準分配器)。
T::T(const T&) 拋出的任何異常。
異常安全性:
強。
迭代器失效:
所有指向 circular_buffer 的迭代器均失效(除了等於 end() 的迭代器)。
複雜度:
線性(與 cb 的大小相關)。
參見:
assign(size_type, const_reference), assign(capacity_type, size_type, const_reference), assign(InputIterator, InputIterator), assign(capacity_type, InputIterator, InputIterator)
void assign(size_type n, const_reference item);

賦值 n 個 items 到 circular_buffer 中。

circular_buffer 中的原有內容將被刪除並替換為 itemn 個拷貝。

作用:
capacity() == n && size() == n && (*this)[0] == item && (*this)[1] == item && ... && (*this) [n - 1] == item
參數:
n
被填充到 circular_buffer 中的元素數量。
item
被填充到 circular_buffer 中的元素。
拋出:
如果內存耗盡則拋出一個內存分配錯誤(std::bad_alloc 如果使用標準分配器)。
T::T(const T&) 拋出的任何異常。
異常安全性:
基本。
迭代器失效:
指向 circular_buffer 的所有迭代器均失效(除了等於 end() 的迭代器)。
複雜度:
線性(與 n 相關)。
參見:
operator=, assign(capacity_type, size_type, const_reference), assign(InputIterator, InputIterator), assign(capacity_type, InputIterator, InputIterator)
void assign(capacity_type capacity, size_type n, const_reference item);

賦值 n 個 items 到指定容量的 circular_buffer.

circular_buffer 的容量將被設置為給定值,circular_buffer 中的內容被刪除並替換為 itemn 份拷貝。

前提條件:
capacity >= n
作用:
capacity() == capacity && size() == n && (*this)[0] == item && (*this)[1] == item && ... && (*this) [n - 1] == item
參數:
capacity
新的容量。
n
被填充到 circular_buffer 中的元素數量。
item
被填充到 circular_buffer 中的元素。
拋出:
如果內存耗盡則拋出一個內存分配錯誤(std::bad_alloc 如果使用標準分配器)。
T::T(const T&) 拋出的任何異常。
異常安全性:
基本。
迭代器失效:
指向 circular_buffer 的所有迭代器均失效(除了等於 end() 的迭代器)。
複雜度:
線性(與 n 相關)。
參見:
operator=, assign(size_type, const_reference), assign(InputIterator, InputIterator), assign(capacity_type, InputIterator, InputIterator)
template <class InputIterator>
void assign(InputIterator first, InputIterator last);


將給定區間賦值到 circular_buffer.

circular_buffer 的內容被刪除並替換為來自給定區間的元素的拷貝。

前提條件:
有效區間 [first, last).
firstlast 必須符合 輸 入迭代器InputIterator 的要求。
作用:
capacity() == std::distance(first, last) && size() == std::distance(first, last) && (*this)[0]== *first && (*this)[1] == *(first + 1) && ... && (*this)[std::distance(first, last) - 1] == *(last - 1)
參數
first
被複製區間的開始。
last
被複製區間的結束。
拋出:
如果內存耗盡則拋出一個內存分配錯誤(std::bad_alloc 如果使用標準分配器)。
T::T(const T&) 拋出的任何異常。
異常安全性:
基本。
迭代器失效:
指向 circular_buffer 的所有迭代器均失效(除了等於 end() 的迭代器)。
複雜度:
線性(與 std::distance(first, last) 相關)。
參見:
operator=, assign(size_type, const_reference), assign(capacity_type, size_type, const_reference), assign(capacity_type, InputIterator, InputIterator)
template <class InputIterator>
void assign(capacity_type capacity, InputIterator first, InputIterator last);


將給定區間賦值到指定容量的 circular_buffer 中。

circular_buffer 的容量將被設置為指定值,circular_buffer 的內容被刪除並替換為來自給定區間的元素的拷貝。

前提條件:
有效區間 [first, last).
firstlast 必須符合 輸 入迭代器InputIterator 的要求。
作用:
capacity() == capacity && size() <= std::distance(first, last) && (*this)[0]== *(last - capacity) && (*this)[1] == *(last - capacity + 1) && ... && (*this)[capacity - 1] == *(last - 1)

如果被複製的來自 range [first, last) 的元素數量大於給定的 capacity, 則只有區間 [last - capacity, last) 中的元素被複製。
參數:
capacity
新的容量。
first
被複製區間的開始。
last
被複製區間的結束。
拋出:
如果內存耗盡則拋出一個內存分配錯誤(std::bad_alloc 如果使用標準分配器)。
T::T(const T&) 拋出的任何異常。
異常安全性:
基本。
迭代器失效:
指向 circular_buffer 的所有迭代器均失效(除了等於 end() 的迭代器)。
複雜度:
線性(與 std::distance(first, last) 相關;如果 InputIterator隨 機訪問迭代器RandomAccessIterator 則與 min[capacity, std::distance(first, last)] 相關)。
參見:
operator=, assign(size_type, const_reference), assign(capacity_type, size_type, const_reference), assign(InputIterator, InputIterator)
void swap(circular_buffer<T,Alloc>& cb);

交換兩個 circular_buffers 的內容。
作用:
this 包含 cb 中的元素,反之亦然;this 的容量等於 cb 的容量,反之亦然。
參數:
cb
被交換的 circular_buffer.
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
兩個 circular_buffers 的所有迭代器均失效。(另一方面,這些迭代器仍舊指向同一個元素但卻是不同的容器。如果你想使用這一特性,則必須關閉 對調試的支持,否則在使用這些失效迭代器時就會報告一個斷言。)
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
swap(circular_buffer<T, Alloc>&, circular_buffer<T, Alloc>&)
void push_back(const_reference item = value_type());

插入一個新元素到 circular_buffer 的末端。
作用:
如果 capacity() > 0back() == item
如果 circular_buffer 已滿,則刪除第一個元素。如果容量為 0, 則不插入。
參數:
item
被插入的元素。
拋出:
T::T(const T&) 拋出的任何異常。
異常安全性:
基本;如果在拋出一節中列出的操作沒有拋出的話則無拋出。
迭代器失效:
除了指向被覆寫元素的迭代器外,沒有迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
push_front(const_reference), pop_back(), pop_front()
void push_front(const_reference item = value_type());

插入一個新元素到 circular_buffer 的頭部。
作用:
如果 capacity() > 0front() == item
如果 circular_buffer 已滿,則最後一個元素被刪除。如果容量為 0, 則不插入。
參數:
item
被插入的元素。
拋出:
T::T(const T&) 拋出的任何異常。
異常安全性:
基本;如果在拋出一節中列出的操作沒有拋出的話則無拋出。
迭代器失效:
除了指向被覆寫元素的迭代器外,沒有迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
push_back(const_reference), pop_back(), pop_front()
void pop_back();

circular_buffer 中刪除最後一個元素。
前提條件:
!empty()
作用:
circular_buffer 中刪除最後一個元素。
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
只有指向被刪元素的迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
pop_front(), push_back(const_reference), push_front(const_reference)
void pop_front();

circular_buffer 中刪除第一個元素。
前提條件:
!empty()
作用:
circular_buffer 中的第一個元素被刪除。
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
只有指向被刪元素的迭代器失效。
複雜度:
常數(與 circular_buffer 的大小相關)。
參見:
pop_back(), push_back(const_reference), push_front(const_reference)
iterator insert(iterator pos, const_reference item = value_type());

在指定位置插入一個元素。
前提條件:
pos 是一個指向 circular_buffer 或其尾部的有效迭代器。
作用:
item 被插入到位置 pos.
如果 circular_buffer 是滿的,則第一個元素被覆寫。如果 circular_buffer 是滿的且 pos 指向 begin(), 則該元素不會被插入。如果容量為 0, 則不插入。
參數:
pos
指定 item 插入的位置的迭代器。
item
被插入的元素。
返回:
指向插入後元素的迭代器,如果 item 未插入則返回 begin()。(見作 用)
拋出:
T::T(const T&) 拋出的任何異常。
T::operator = (const T&) 拋出的任何異常。
異常安全性:
基本;如果拋出一節中列出的操作沒有拋出則不拋出異常。
迭代器失效:
指向插入點(包括 pos)及插入點之後的迭代器(直至未 尾;除了等於 end() 的迭代器)均失效。指向被覆寫元素的迭代器也失效。
複雜度:
線性(與 std::distance(pos, end()) 相關)。
參見:
insert(iterator, size_type, value_type), insert(iterator, InputIterator, InputIterator), rinsert(iterator, value_type), rinsert(iterator, size_type, value_type), rinsert(iterator, InputIterator, InputIterator)
void insert(iterator pos, size_type n, const_reference item);

插入 itemn 份拷貝到指定位置。
前提條件:
pos 為指向 circular_buffer 或其尾部的有效迭代器。
作用:
min[n, (pos - begin()) + reserve()] 個元素將被插入到位置 pos.
circular_buffer 頭部的 min[pos - begin(), max[0, n - reserve()]] 個元素將被覆寫。
(詳細解釋請見例子)
參數:
pos
指定 items 插入位置的迭代器。
n
被插入的 items 數量。
item
被插入的元素。
拋出:
T::T(const T&)  拋出的任何異常。
T::operator = (const T&)& nbsp;拋出的任何異常。
異常安全性:
基本;如果拋出一節中列出的操作沒有拋出則不拋出異常。
迭代器失效:
指向插入點(包括 pos)及插入點之後的迭代器(直至未 尾;除了等於 end() 的迭代器)均失效。指向被覆寫元素的迭代器也失效。
複雜度:
線性(與 min[capacity(), std::distance(pos, end()) + n] 相關)。
例子:
考慮一個容量為6而大小為4的 circular_buffer。 其內部緩衝區可能如下:

|1|2|3|4| | |
p ---^

在位置 p 插入5個元素後:

insert(p, (size_t)5, 0);

實際上只有4個元素被插入而元素 12 則被覆寫。這是由於插入操作要保持容量不變。插入後的內部緩衝區如下:

|0|0|0|0|3|4|

作為比較,如果容量無需保持,則內部緩衝區會是這樣:|1|2|0|0|0|0|0|3|4|.
參見:
insert(iterator, value_type), insert(iterator, InputIterator, InputIterator), rinsert(iterator, value_type), rinsert(iterator, size_type, value_type), rinsert(iterator, InputIterator, InputIterator)
template <class InputIterator>
void insert(iterator pos, InputIterator first, InputIterator last);


將區間 [first, last) 插入到指定位置。
前提條件:
pos 為指向 circular_buffer 或其尾部的有效迭代器。 
有效區間 [first, last) 其中 firstlast 符合 輸入迭代器 InputIterator 的要求。
作用:
區間 [first + max[0, distance(first, last) - (pos - begin()) - reserve()], last) 中的元素被插入到位置 pos.
circular_buffer 頭部的 min[pos - begin(), max[0, distance(first, last) - reserve()]] 個元素被覆寫。
(詳細解釋請見例子)
參數:
pos
指定區間插入位置的迭代器。
first
被插入區間的開始。
last
被插入區間的結束。
拋出:
T::T(const T&)  拋出的任何異常。
T::operator = (const T&)& nbsp;拋出的任何異常。
異常安全性:
基本;如果拋出一節中列出的操作沒有拋出則不拋出異常。
迭代器失效:
指向插入點(包括 pos)及插入點之後的迭代器(直至未 尾;除了等於 end() 的迭代器)均失效。指向被覆寫元素的迭代器也失效。
複雜度:
線性(與 [std::distance(pos, end()) + std::distance(first, last)] 相關;如果 InputIterator隨 機訪問迭代器RandomAccessIterator 則與 min[capacity(), std::distance(pos, end()) + std::distance(first, last)] 相關)。
例子:
考慮一個容量為6而大小為4的 circular_buffer。 其內部緩衝區可能如下:

|1|2|3|4| | |
p ---^

在位置 p 插入一個區間的元素後:

int array[] = { 5, 6, 7, 8, 9 };
insert(p, array, array + 5);

實際上只有指定區間中的元素 6, 7, 89 被插入,而元素 12 被覆寫。這是由於插入操作要保持容量不變。插入後的內部緩衝區如下:

|6|7|8|9|3|4|

作為比較,如果容量無需保持,則內部緩衝區會是這樣:|1|2|5|6|7|8|9|3|4|.
參見:
insert(iterator, value_type), insert(iterator, size_type, value_type), rinsert(iterator, value_type), rinsert(iterator, size_type, value_type), rinsert(iterator, InputIterator, InputIterator)
iterator rinsert(iterator pos, const_reference item = value_type());

在指定位置之前插入一個元素。
前提條件:
pos 是一個指向 circular_buffer 或其尾部的有效迭代器。 
作用:
item 被插入到位置& nbsp; pos 之前。
如果 circular_buffer 已滿,則最後一個元素被覆寫。如果 circular_buffer 已滿且 pos 指向 end(), 則 item 不會被插入。如果容量為 0, 也不插入。
參數:
pos
指定 item 插入的位置之前的迭代器。
item
被插入的元素。 
返回:
指向插入後元素的迭代器,如果 item 未插入則返回 end()。(見作 用)
拋出:
T::T(const T&)  拋出的任何異常。
T::operator = (const T&)& nbsp;拋出的任何異常。
異常安全性:
基本;如果拋出一節中列出的操作沒有拋出則不拋出異常。
迭代器失效:
指向插入點之前的迭代器(直至開始,除了 pos)均失效。 指向被覆寫元素的迭代器也失效。
複雜度:
線性(與 std::distance(begin(), pos) 相關)。
參見:
rinsert(iterator, size_type, value_type), rinsert(iterator, InputIterator, InputIterator), insert(iterator, value_type), insert(iterator, size_type, value_type), insert(iterator, InputIterator, InputIterator)
void rinsert(iterator pos, size_type n, const_reference item);

插入 itemn 份拷貝到指定位置之前。
前提條件:
pos 為指向 circular_buffer 或其尾部的有效迭代器。
作用:
min[n, (end() - pos) + reserve()]& nbsp;個元素將被插入到位置 pos 之前。
circular_buffer 尾部的 min[end() - pos, max[0, n - reserve()]] 個元素將被覆寫。
(詳細解釋請見例子
參數:
pos
指定 items 插入位置的迭代器。
n
被插入的 items 數量。 
item
被插入的元素。
拋出:
T::T(const T&)  拋出的任何異常。
T::operator = (const T&)& nbsp;拋出的任何異常。
異常安全性:
基本;如果拋出一節中列出的操作沒有拋出則不拋出異常。
迭代器失效:
指向插入點之前的迭代器(直至開始,除了 pos)均失效。 指向被覆寫元素的迭代器也失效。 
複雜度:
線性(與 min[capacity(), std::distance(begin(), pos) + n] 相關)。
例子:
考慮一個容量為6而大小為4的 circular_buffer。 其內部緩衝區可能如下:

|1|2|3|4| | |
p ---^

在位置 p 之前插入5個元素後:

rinsert(p, (size_t)5, 0);

實際上只有4個元素被插入,而元素 34 被覆寫。這是由於插入操作要保持容量不變。插入後的內部緩衝區如下:

|1|2|0|0|0|0|

作為比較,如果容量無需保持,則內部緩衝區會是這樣: |1|2|0|0|0|0|0|3|4|.
參見:
rinsert(iterator, value_type), rinsert(iterator, InputIterator, InputIterator), insert(iterator, value_type), insert(iterator, size_type, value_type), insert(iterator, InputIterator, InputIterator)
template <class InputIterator>
void rinsert(iterator pos, InputIterator first, InputIterator last);


將區間 [first, last) 插入到指定位置之前。
前提條件:
pos 為指向 circular_buffer 或其尾部的有效迭代器。 
有效區間 [first, last) 其中 firstlast 符合 輸入迭代器 InputIterator 的要求。
作用:
區間 [first, last - max[0, distance(first, last) - (end() - pos) - reserve()]) 中的元素被插入到位置 pos 之前。
circular_buffer 尾部的 min[end() - pos, max[0, distance(first, last) - reserve()]] 個元素被覆寫。
(詳細解釋請見例子)
參數:
pos
指定區間插入位置的迭代器。
first
被插入區間的開始。
last
被插入區間的結束。
拋出:
T::T(const T&)  拋出的任何異常。
T::operator = (const T&)& nbsp;拋出的任何異常。
異常安全性:
基本;如果拋出一節中列出的操作沒有拋出則不拋出異常。
迭代器失效:
指向插入點之前的迭代器(直至開始,除了 pos)均失效。 指向被覆寫元素的迭代器也失效。 
複雜度:
線性(與 [std::distance(begin(), pos) + std::distance(first, last)] 相關;如果 InputIterator隨 機訪問迭代器RandomAccessIterator 則與 min[capacity(), std::distance(begin(), pos) + std::distance(first, last)] 相關)。
例子:
考慮一個容量為6而大小為4的 circular_buffer。 其內部緩衝區可能如下:

|1|2|3|4| | |
p ---^

在位置 p 之前插入一個區間的元素後:

int array[] = { 5, 6, 7, 8, 9 };
insert(p, array, array + 5);

實際上只有指定區間中的元素 5, 6, 78 被插入,而元素 34 被覆寫。這是由於插入操作要保持容量不變。插入後的內部緩衝區如下:

|1|2|5|6|7|8|

作為比較,如果容量無需保持,則內部緩衝區會是這樣:|1|2|5|6|7|8|9|3|4|.
參見:
rinsert(iterator, value_type), rinsert(iterator, size_type, value_type), insert(iterator, value_type), insert(iterator, size_type, value_type), insert(iterator, InputIterator, InputIterator)
iterator erase(iterator pos);

刪除指定位置的一個元素。
前提條件:
pos 是一個指向 circular_buffer& nbsp;的有效迭代器(但不是 end())。
作用:
位置 pos 的元素被刪除。
參數:
pos
指向被刪除元素的迭代器。
返回:
指向被刪除元素之後第一個元素的迭代器,如果不存在這樣的元素則返回 end().
拋出:
T::operator = (const T&)& nbsp;拋出的任何異常。
異常安全性:
基本;如果拋出一節中列出的操作沒有拋出則不拋出異常。
迭代器失效:
指向被刪除元素及其之後的元素的迭代器(直至未尾;除了等於 end() 的迭代器)均失效。
複雜度:
線性(與 std::distance(pos, end()) 相關)。
參見:
erase(iterator, iterator), rerase(iterator), rerase(iterator, iterator), clear()
iterator erase(iterator first, iterator last);

刪除區間 [first, last).
前提條件:
有效區間 [first, last).
作用:
區間 [first, last) 中的元素被刪除。(如果 first == last 則沒有刪除)
參數:
first
被刪除區間的開始。
last
被刪除區間的結束。
返回:
指向被刪除元素之後第一個元素的迭代器,如果不存在這樣的元素則返回 end().
拋出:
T::operator = (const T&)& nbsp;拋出的任何異常。
異常安全性:
基本;如果拋出一節中列出的操作沒有拋出則不拋出異常。
迭代器失效:
指向被刪除元素及其之後的元素的迭代器(直至未尾;除了等於 end() 的迭代器)均失效。
複雜度:
線性(與 std::distance(first, end()) 相關)。
參見:
erase(iterator), rerase(iterator), rerase(iterator, iterator), clear()
iterator rerase(iterator pos);

刪除指定位置的一個元素。
前提條件:
pos 是一個指向 circular_buffer& nbsp;的有效迭代器(但不是 end())。  
作用:
位置 pos 的元素被刪除。
參數:
pos
指向被刪除元素的迭代器。
返回:
指向被刪除元素之前第一個元素的迭代器,如果不存在這樣的元素則返回 begin().
拋出:
T::operator = (const T&)& nbsp;拋出的任何異常。
異常安全性:
基本;如果拋出一節中列出的操作沒有拋出則不拋出異常。
迭代器失效:
指向被刪除元素及其之前的元素的迭代器(直至開始)均失效。
複雜度:
線性(與 std::distance(begin(), pos) 相關)。
說明:
該方法與 erase(iterator) 方法對稱,且如果迭代器 pos 靠近 circular_buffer 的頭部則比 erase(iterator) 更高效。(請見複雜度)
參見:
erase(iterator), erase(iterator, iterator), rerase(iterator, iterator), clear()
iterator rerase(iterator first, iterator last);

刪除區間 [first, last).
前提條件:
有效區間 [first, last).
作用:
區間 [first, last) 中的元素被刪除。(如果 first == last 則沒有刪除)
參數:
first
被刪除區間的開始。
last
被刪除區間的結束。
返回:
指向被刪除元素之前第一個元素的迭代器,如果不存在這樣的元素則返回 begin().
拋出:
T::operator = (const T&)& nbsp;拋出的任何異常。
異常安全性:
基本;如果拋出一節中列出的操作沒有拋出則不拋出異常。
迭代器失效:
指向被刪除元素及其之前的元素的迭代器(直至開始)均失效。
複雜度:
線性(與 std::distance(begin()last) 相關)。
說明:
該方法與 erase(iterator, iterator) 方法對稱,且如果 std::distance(begin(), first) 小於 std::distance(last, end()) 則比 erase(iterator, iterator) 更高效。
參見:
erase(iterator), erase(iterator, iterator), rerase(iterator), clear()
void clear();

刪除 circular_buffer 中的所有元素。
作用:
size() == 0
拋出:
無。
異常安全性:
無拋出。
迭代器失效:
指向 circular_buffer 的所有迭代器(除了等於 end() 的迭代器)均失效。
複雜度:
線性(與 circular_buffer 的大小相關)。
參見:
~circular_buffer(), erase(iterator), erase(iterator, iterator), rerase(iterator), rerase(iterator, iterator)

獨立函數

template <class T, class Alloc>
bool operator==(const circular_buffer<T,Alloc>& lhs, const circular_buffer<T,Alloc>& rhs);


逐個元素比較兩個 circular_buffers 判斷它們是否相等。
參數:
lhs
用於比較的 circular_buffer.
rhs
用於比較的 circular_buffer.
返回:
lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin())
拋出:
無。
複雜度:
線性(與 circular_buffers 的大小相關)。
迭代器失效:
不會令任何迭代器失效。
template <class T, class Alloc>
bool operator<(const circular_buffer<T,Alloc>& lhs, const circular_buffer<T,Alloc>& rhs);


逐個元素比較兩個 circular_buffers 判斷左操作數是否小於右操作數。
參數
lhs
用於比較的 circular_buffer.
rhs
用於比較的 circular_buffer.
返回:
std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end())
拋出:
無。
複雜度:
線性(與 circular_buffers 的大小相關)。
迭代器失效:
不會令任何迭代器失效。
template <class T, class Alloc>
bool operator!=(const circular_buffer<T,Alloc>& lhs, const circular_buffer<T,Alloc>& rhs);


逐個元素比較兩個 circular_buffers 判斷它們是否不等。
參數:
lhs
用於比較的 circular_buffer.
rhs
用於比較的 circular_buffer.
返回:
!(lhs == rhs)
拋出:
無。
複雜度:
線性(與 circular_buffers 的大小相關)。
迭代器失效:
不會令任何迭代器失效。
參見:
operator==(const circular_buffer<T,Alloc>&, const circular_buffer<T,Alloc>&)
template <class T, class Alloc>
bool operator>(const circular_buffer<T,Alloc>& lhs, const circular_buffer<T,Alloc>& rhs);


逐個元素比較兩個 circular_buffers 判斷左操作數是否大於右操作數。
參數:
lhs
用於比較的 circular_buffer.
rhs
用於比較的 circular_buffer.
返回:
rhs < lhs
拋出:
無。
複雜度:
線性(與 circular_buffers 的大小相關)。
迭代器失效:
不會令任何迭代器失效。
參見:
operator<(const circular_buffer<T,Alloc>&, const circular_buffer<T,Alloc>&)
template <class T, class Alloc>
bool operator<=(const circular_buffer<T,Alloc>& lhs, const circular_buffer<T,Alloc>& rhs);


逐個元素比較兩個 circular_buffers 判斷左操作數小於等於右操作數。
參數:
lhs
用於比較的 circular_buffer.
rhs
用於比較的 circular_buffer.
返回:
!(rhs < lhs)
拋出:
無。
複雜度:
線性(與 circular_buffers 的大小相關)。
迭代器失效:
不會令任何迭代器失效。
參見:
operator<(const circular_buffer<T,Alloc>&, const circular_buffer<T,Alloc>&)
template <class T, class Alloc>
bool operator>=(const circular_buffer<T,Alloc>& lhs, const circular_buffer<T,Alloc>& rhs);


逐個元素比較兩個 circular_buffers 判斷左操作數是否大於等於右操作數。
參數:
lhs
用於比較的 circular_buffer.
rhs
用於比較的 circular_buffer.
返回:
!(lhs < rhs)
拋出:
無。
複雜度:
線性(與 circular_buffers 的大小相關)。
迭代器失效:
不會令任何迭代器失效。
參見:
operator<(const circular_buffer<T,Alloc>&, const circular_buffer<T,Alloc>&)
template <class T, class Alloc>
void swap(circular_buffer<T,Alloc>& lhs, circular_buffer<T,Alloc>& rhs);


交換兩個 circular_buffers 的內容。
作用:
lhs 包含原 rhs 的元素,反之亦然。
參數:
lhs
rhs 交換內容的 circular_buffer.
rhs
與 lhs 交換內容的 circular_buffer.
拋出:
無。
複雜度:
常數(與 circular_buffers 的大小相關)。
迭代器失效:
兩個 circular_buffers 的所有迭代器均失效。(另一方面,這些迭代器仍舊指向同一個元素但卻是不同的容器。如果你想使用這一特性,則必須關閉 對調試的支持,否則在使用這些失效迭代器時就會報告一個斷言。)
參見:
swap(circular_buffer<T, Alloc>&)

備註

  1. Boost 中包含有智能指針的一個很好的實現。

  2. 永遠不要創建 std::auto_ptr 的循環緩衝區。詳細討論請參考 Scott Meyers 的名著 作用ive STL. (Meyers S., Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library. Addison-Wesley, 2001.)

參見

boost::circular_buffer_space_optimized, std::vector, std::list, std::deque

鳴謝

The circular_buffer has a short history. Its first version was a std::deque adaptor. This container was not very effective because of many reallocations when inserting/removing an element. Thomas Wenish did a review of this version and motivated me to create a circular buffer which allocates memory at once when created.

The second version adapted std::vector but it has been abandoned soon because of limited control over iterator invalidation.

The current version is a full-fledged STL compliant container. Pavel Vozenilek did a thorough review of this version and came with many good ideas and improvements. Also, I would like to thank Howard Hinnant, Nigel Stewart and everyone who participated at the formal review for valuable comments and ideas.

發佈說明

Boost 1.37

Boost 1.36

Boost 1.35