![[ 永遠的UNIX::UNIX技術資料的寶庫 ]](/images/title.gif) GB | BIG5
|
| 首頁 > 編程技術 > C/C++ > 正文 |
 |
| 標準C程式庫--標準樣版庫-集合樣版 |
| http://home.pchome.com.tw/computer/cpp2000/ (2001-06-01 15:00:01) |
過去幾年以來，C++ 程式語言的標準語言定義程序經歷了一個大改變。此標準化程序便是標準資料結構庫的產生，此程式庫通常稱為「標準樣版庫」( Standard Template Library ) 或 STL 。由於 STL 是 C++ 語言定義的一部份，因此使用 STL 的程式應該享有高度可植性，因為任何標榜支援 " 標準C++" 的編譯程式都必須提供 STL 實作。
疊代字只是一種類似指標的物件，可以用來循環存取容器中的所有元素。由於不同的演算法需要以個種不同的方式來遊歷容器，因此有各種不同的疊代子形式。標準樣版庫中的每個容器類都提供一種疊代子，適合和實作容器所用的儲存技巧配合使用。
set 資料型態的設計是為了有效率地進行所有運算，不超過 O( log n ) 的步驟。並不像向量或串列中的情況，例如，檢查一個值是否有出現在一個向量或串列中時，向量和串列樣版需要 O( n ) 的步驟，而集合只需要 O( log n ) 的步驟及可。
集合資料說明
集合資料型態有三種形式：集合- 不允許一個元素出現一次以上。多集合-允許元素重出現。位元集合-維護一圈有限圍的整數集合。更雜的集合運算包括兩集合的聯集、交集與差集，這些運算正是集合觀念特有的特徵。聯集：兩集合的聯集是將屬於第二個集合但八屬於第一個集點的所有元素加入第一個集合。交集：兩集合的交集是同時出現在兩集合中的所有元素所成的集合。差集：它是屬於第一個集合但不屬於第二個集合的所有元素所成的集合。子集：如果一個集合的所有元素都屬於另一個集合，則前者是後者的子集。大部分的集合運算都使用通用演算法的方式來進行實作。
集合是儲存唯一值的簡單群集。雖然集合是不需要順序的，但是標準樣版庫中的 set 資料結構卻是以一種有序表示法來儲存元素的。這樣可以快速插入，移除等運算。設計師在使用 set 資料結構前，必須引入 < set.h > 。
Top
宣告和初始化集合
set 及 multiset 資料型態是利用樣版語法實作出來的，其中樣版引數為集合所包含的元素型態。集合與多集合所儲存的元素必須能夠識別小於比較運算子 ( < ) 和等於運算子 ( = ) 。
set set_one; // 宣告整數型態的集合變數
set set_four (aList.begin(), aList.end()); // 將其它型態的資料結構，利用疊代子的方式拷貝到集合結構。
swap
Top
集合插入
insert 將元素插入集合，此函式傳回一個結構 ( pair ) ，其中第一個成員是一個疊代子，代表新插入元素的位置；第二個成員是一個 bool ，指出是否進行了插入運算。
Top
從集合中移除元素
erase 此函式有三種形式。利用鍵值刪除、利用疊代子刪除或用疊代子形成的圍來作刪除。
set_three.erase(4); //第一種
set::iterator five = set_three.find(5); //第二種
set_three.erase(five);
set::iterator seven = set_three.find(7); //第三種
set::iterator eleven = set_three.find(11);
set_three.erase (seven, eleven);
Top
集合搜尋
size 傳回中的元素個數。
empty 此集合是否為空的。
find 大部分用於 set 結構。傳回被搜尋值的位置，以一個疊代子的方式來表示。如果找不到，便傳回和 end() 成員相同的疊代子。
lower_bound 需應用在 multiset 型態上。傳回引數值第一次出現的位置。
upper_bound 需應用在 multiset 型態上。傳回引數值之後的第一個元素。
equal_range 需應用在 multiset 型態上。傳回一個結構，包含 lower_bound 和 upper_bound 的傳回值。
count 傳回引數在集合中出現的次數。如果是 set 型態時，此值為 0 或 1。
Top
集合疊代子
begin 傳回起始疊代子。
end 傳回終結疊代子
rbegin 傳回逆向起始疊代子。
rend 傳回逆向終結疊代子。
Top
位元集合說明
位元集合是一系列的 0 / 1 位元值。主要用於記錄元素是否出現在集合中，而較一般性的 set 資冊型態則儲存真正的值。當設計師需要使用此集合時需包含 < bitset.h > 。注意位元集合並不支援任何的疊代子。並且提供資料流的運算。
Top
宣告和初始化位元集合
位元集合是用樣版實作出來的。樣版參數並不是指定資料型態，其真正功能為指定位元個數，必須填入整數。宣告位元集合有三種方式：
bitset<126> bset_one; // bset_one 位元個數為 126 個。
bitset<126> bset_two(100); // bset_two 位元個數為 100 ，此用法用於宣告大量的位元集合。
bitset<126> small_set("10101010"); // 利用字串語法為初始化。
Top
存取和測試元素
和向量相同位元集合可使用類似陣列的存取方式來存取。不過標準樣版庫也提供一些成員函式來協助。
test 引數為整數，傳回 bool 值。
any 測試所有的值是否為 on 。
none 測試所有的值是否為 off 。
set 要將一個位元設定成 1 ，不含任何引函式將所有位元值都設定為 0 。
reset 要將一個位元設定成 0 ，不含任何引函式將所有位元值都清成 0 。
flip 反轉位元功能。
bset_one.flip(); // 反轉所有位元
bset_one.flip(12); // 反轉第 12 個位元
size 在集合中的元素大小。
count 傳回等於 1 的位元個數。
Top
在位元集合中的操作
~ 將位元集合作邏輯中的補數運算。
& 將兩位元集合作邏輯中的 and 運算。
| 將兩位元集合作邏輯中的 or 運算。
^ 將兩位元集合作邏輯中的 xor 運算。
<< 、>> 右旋和左旋的運算。
Top
位元集合的轉換
to_ulong 將位元集合轉換成長整數。如果超過圍時，丟出一個 overflow_error 例外。
to_string 將位元集合轉換成字串。
(http://www.fanqiang.com)
進入【UNIX論壇】
|
|
| 相關文章 |
標準C程式庫--問題例--類型 String (2001-06-01 16:10:00)
標準C程式庫--標準樣版庫-集合樣版 (2001-06-01 15:00:01)
標準C程式庫--標準樣版庫-雙頭佇列樣版 (2001-06-01 14:08:00)
標準C程式庫--標準樣版庫-串列樣版 (2001-06-01 13:04:00)
標準C程式庫--標準樣版庫-向量樣版 (2001-06-01 12:10:01)
標準C程式庫--標準樣版庫-字串樣版 (2001-06-01 11:00:00)
|
|
|
|
|
★ 樊強制作 歡迎分享 ★ |