dijkstra堆優(yōu)化及set用法-展示頁(yè)
2024-10-11 21:43本頁(yè)面
【正文】 果 a是迭代器 ,就刪除迭代器指向的元素( a ) 順序查找 =a的第一個(gè)元素 ,返回迭代器 ( a ) 順序查找 a的第一個(gè)元素 ,返回迭代器 Set操作 ? () 求第 １ 個(gè)元素，返回迭代器，由于是順序的容器，所以第 １ 個(gè)元素就是最小的元素． () 求容器的末尾，表示容器到了末尾，返回迭代器，這個(gè)迭代器里沒(méi)有元素，專門表示末尾． () 求倒數(shù)第 １ 個(gè)元素，即最大元素，返回迭代器，（注意：這個(gè)迭代器是逆向迭代器和 ()的返回值類型不同） Set操作 ? () 求容器里元素的數(shù)量，返回整數(shù) () 判斷容器是否是空，空返回true,否則返回 false。a, const ss amp。Dijkstra堆優(yōu)化及 set用法 主講： wangfangbob Email:. Set功能 ? Set，顧名思義，就是集合的意思 ? 它支持插入，刪除，查找，首元素，末元素等操作，就像一個(gè)集合一樣． ? 而且所有的操作都是在嚴(yán)格 logn時(shí)間之內(nèi)完成，效率非常高．對(duì)于動(dòng)態(tài)維護(hù)可以說(shuō)是很理想的選擇 ? Set是一個(gè)有序的容器，里面的元素都是排好序的 Set實(shí)現(xiàn)簡(jiǎn)介 ? Set的實(shí)現(xiàn)是通過(guò) ２ 叉排序樹來(lái)實(shí)現(xiàn)，就是將所有的元素用一個(gè)樹來(lái)存儲(chǔ)，根元素大于左子樹的元素，小于右子樹的元素，所有的操作都是基于這個(gè)樹，通過(guò)判斷元素的大小來(lái)選擇對(duì)左子樹操作還是右子樹操作，這樣操作數(shù)量和樹的層數(shù)成正比． ? 這樣樹就有可能退化成一條線，所以 Set用一種平衡的 ２ 叉排序樹－－紅黑樹實(shí)現(xiàn)． Set對(duì)元素的要求 ? Set中的元素可以是任意類型的，但是由于需要排序，所以元素必須有一個(gè)序，即大小的比較關(guān)系，比如整數(shù)可以用＜比較． ? 比較關(guān)系是有要求的，必須和實(shí)數(shù)的＜類似，下面說(shuō)明對(duì)比較關(guān)系＜的要求 ? １ ．如果 a b, b c 則有 a c，即比較關(guān)系必須滿足傳遞性 ? ２ ． a b和 b c不能同時(shí)成立 ? 如果元素類型有比較關(guān)系，并且比較關(guān)系滿足以上 ２ 個(gè)條件，那么這個(gè)類型的元素就可以作為 Set中的元素來(lái)存儲(chǔ) 自定義元素類型 Set代碼 ? includeset typedef struct { 定義類型 } ss(類型名 )。 ? bool operator(
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1