标准C程式库--标准样版库-集合样版

过去几年以来，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);    file://第一种

set::iterator five = set_three.find(5);    file://第二种
set_three.erase(five);

set::iterator seven = set_three.find(7);        file://第三种
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    将位元集合转换成字串。