Boost.Range

Range 的概念


簡介

區間的概念類似於STL中的容器概念。一個區間提供了訪問一個半開放區間  [first,one_past_last) 的迭代器,還提供了關於區間中的元素數量的信息。但是,區間比容器少了一點點要求。

區間概念的動機是,有許多有用的、類似於容器的類型不能完全滿足容器的所有要求,而很多算法可以依據這個有所簡化的要求來編寫。具體的說,區間不要求:

由於第二個要求,區間對像必須以(常量或非常量)引用的方式傳入泛型代碼。

一個區間上可以執行的操作取決於其底層迭代器類型的 遍歷類別。因此區間概念的命名正是反映了其迭代器所支持的遍歷類別。有關區間命名的更多信息請見 術語及風格 一節。

下述概念以 元函數 的方式給出關聯類型,而且所有函數都是獨立函數,以用於間接層。


單遍區間

符號

X 一個類型,單遍區間的 model.
a 類型 X 的對象.

描述

一個區間 X,其 boost::range_iterator<X>::type 單遍迭代器 的 model。

關聯類型

Iterator type boost::range_iterator<X>::type 用於迭代區間中的元素的迭代器的類型。迭代器的 value type 應為區間的 value type. 從該迭代器類型到常量迭代器類型的轉換必須存在。
Const iterator type boost::range_const_iterator<X>::type 一個迭代器類型,該迭代器可用於檢測但不可修改區間中的元素。

有效表達式

以下表達式必須有效。

名字 表達式 返回類型
區間的始端 boost::begin(a) boost::range_iterator<X>::type 如果 a 為可變的,否則為 boost::range_const_iterator<X>::type
區間的末端 boost::end(a) boost::range_iterator<X>::type 如果 a 為可變的,否則為 boost::range_const_iterator<X>::type

表達式語義

表達式 語義 後置條件
boost::begin(a) 返回一個迭代器,指向區間中的第一個元素。 boost::begin(a) 是可提領的或是 past-the-end. 它是 past-the-end 當且僅當 boost::size(a) == 0.
boost::end(a) 返回一個迭代器,指向區間中的最後一個元素之後。 boost::end(a) 為 past-the-end.

複雜度保證

boost::end(a) 至多為分期線性時間,boost::begin(a) 為分期常量時間。大多數情況下,你可以期望兩個函數均為分期常量時間。

不變式

有效區間 對於任意區間 a, [boost::begin(a),boost::end(a)) 是一個有效區間,即 boost::end(a) 可以從 boost::begin(a) 在經過有限次遞增後到達。
完整性 一個對區間 [boost::begin(a),boost::end(a)) 進行迭代的算法將遍歷 a 的每一個元素。

參見

為 UDT 擴展本庫擴展

元函數的實現

函數的實現

容器


前向區間

符號

X 一個類型,前向區間的 model.
a 類型 X 的對象

描述

區間 Xboost::range_iterator<X>::type 前向遍歷迭代器 的 model

強化自

單遍區間

雙向區間

符號

X 一個類型,雙向區間的 model
a 類型 X 的對象

描述

該概念提供了迭代器用於從兩個方向(前向和後向)進行遍歷。boost::range_iterator<X>::type 的迭代器必須滿足 雙向遍歷迭代器 的所有要求。

強化自

前向區間

隨機訪問區間

描述

區間 Xboost::range_iterator<X>::type 隨機訪問遍歷迭代器 的 model

強化自

雙向區間


概念檢查

每一個區間概念都有一個對應的概念檢查類。這些類可以和 Boost Concept Check 庫一起使用,以確保模板參數的類型兼容於某個區間概念。如果不兼容,則產生一個編譯期錯誤。為區間概念所提供的檢查是關於迭代器遍歷類別的。例如,下面這行代碼檢查類型 T 是否符合 前向區間 的概念。
    function_requires<ForwardRangeConcept<T> >();
還有一個要進行的概念檢查是針對區間所基於的區間迭代器類型的值訪問屬性。例如檢查一個前向可讀區間,需要以下代碼。
    function_requires<ForwardRangeConcept<T> >();
function_requires<
ReadableIteratorConcept<
typename range_iterator<T>::type
>
>();
本庫提供了以下區間概念檢查類:

參見

區間術語及風格

迭代器概念

Boost Concept Check 庫


Copyright © 2000 Jeremy Siek
Copyright © 2004 Thorsten Ottosen. Use, modification and distribution is subject to the Boost Software License, Version 1.0.