STL的set關(guān)聯(lián)容器解析

現(xiàn)在說(shuō)下容器的種類(lèi)，分為關(guān)聯(lián)容器和順序容器：

關(guān)聯(lián)容器：就是通過(guò)鍵值進(jìn)行存儲(chǔ)和讀取的容器，

順序容器：就是根據(jù)元素在容器中的位置進(jìn)行存儲(chǔ)和讀取的容器，也即順序容器

而set容器的根本原理所在就是紅黑樹(shù)，紅黑樹(shù)是一種另類(lèi)的二叉樹(shù)，相較普通的二叉樹(shù)而言就有更好的統(tǒng)計(jì)性能，紅黑樹(shù)的定義是：

1、根節(jié)點(diǎn)是黑色的

2、節(jié)點(diǎn)不是紅色就是黑色的

3、每個(gè)紅色節(jié)點(diǎn)的左右節(jié)點(diǎn)必須是黑色節(jié)點(diǎn)

4、從葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑上具有相同的黑色節(jié)點(diǎn)和紅色節(jié)點(diǎn)

關(guān)于set關(guān)聯(lián)容器，的定義就是key-type和value-type相同的關(guān)聯(lián)容器

set容器中具有5個(gè)變量

M_color? ：標(biāo)記顏色

M_parent:標(biāo)記父節(jié)點(diǎn)所在

M_left：標(biāo)記左子節(jié)點(diǎn)

M_right：標(biāo)記右子節(jié)點(diǎn)所在

M_data：標(biāo)記了數(shù)據(jù)所在

關(guān)于set的插入操作，使用的是insert_unique也即不允許插入重復(fù)的值?。。。?br />

同時(shí)需要注意的是set容器不能插入重復(fù)的值

這樣還有一點(diǎn)就是：

關(guān)于set容器使用中序遍歷算法對(duì)set容器進(jìn)行遍歷操作：

所以begin()：返回的是最左節(jié)點(diǎn)，也即set容器中的最小值所在

end():函數(shù)返回的是根節(jié)點(diǎn)，因?yàn)楦鶕?jù)中序遍歷，最右節(jié)點(diǎn)的++操作就是根節(jié)點(diǎn)所在！?。?/p>

現(xiàn)在要說(shuō)的是set容器的++操作和--操作：

++操作：

??????? 根據(jù)中序遍歷，進(jìn)行向前遍歷遍歷結(jié)果應(yīng)該是由小到大的升序排列?。?/p>

--操作：

??????? 根據(jù)中序遍歷，進(jìn)行向后遍歷

set的應(yīng)用如下：

#include#includeusing?namespace?std;

int?main()
{
????sets;
????s.insert(1);
????s.insert(2);
????s.insert(3);
????s.insert(1);
????cout<<"set?的?size?值為?："<<s.size()<<endl;
????cout<<"set?的?maxsize的值為?："<<s.max_size()<<endl;
????cout<<"set?中的第一個(gè)元素是?："<<*s.begin()<<endl;
????cout<<"set?中的最后一個(gè)元素是:"<<*s.end()<<endl;
????s.clear();
????if(s.empty())
????{
????????cout<<"set?為空?！?。?<<endl;
????}
????cout<<"set?的?size?值為?："<<s.size()<<endl;
????cout<<"set?的?maxsize的值為?："<<s.max_size()<<endl;
????return?0;
}

關(guān)于mutlieset容器，與set容器不同的是mutileset容器可以存放相同的值，也即set使用的是insert_unique的是，而mutileset的插入使用的是insert_equal也即在mutile_equal可以插入相同的值，插入原則是：小于的值是放在當(dāng)前節(jié)點(diǎn)的左子樹(shù)上，而大于等于的數(shù)值則是放在當(dāng)前節(jié)點(diǎn)的右子樹(shù)上