南京网站建设推广,电信备案网站,个人网站模版,福田附近公司做网站建设哪家效益快1.关于setC STL 之所以得到广泛的赞誉#xff0c;也被很多人使用#xff0c;不只是提供了像vector, string, list等方便的容器#xff0c;更重要的是STL封装了许多复杂的数据结构算法和大量常用数据结构操作。vector封装数组#xff0c;list封装了链表#xff0c;map和set…1.关于setC STL 之所以得到广泛的赞誉也被很多人使用不只是提供了像vector, string, list等方便的容器更重要的是STL封装了许多复杂的数据结构算法和大量常用数据结构操作。vector封装数组list封装了链表map和set封装了二叉树等在封装这些数据结构的时候STL按照程序员的使用习惯以成员函数方式提供的常用操作如插入、排序、删除、查找等。让用户在STL使用过程中并不会感到陌生。关于set必须说明的是set关联式容器。set作为一个容器也是用来存储同一数据类型的数据类型并且能从一个数据集合中取出数据在set中每个元素的值都唯一而且系统能根据元素的值自动进行排序。应该注意的是set中数元素的值不能直接被改变。C STL中标准关联容器set, multiset, map, multimap内部采用的就是一种非常高效的平衡检索二叉树红黑树也成为RB树(Red-Black Tree)。RB树的统计性能要好于一般平衡二叉树所以被STL选择作为了关联容器的内部结构。关于set有下面几个问题(1)为何map和set的插入删除效率比用其他序列容器高大部分人说很简单因为对于关联容器来说不需要做内存拷贝和内存移动。说对了确实如此。set容器内所有元素都是以节点的方式来存储其节点结构和链表差不多指向父节点和子节点。结构图可能如下A/ \B C/ \ / \D E F G因此插入的时候只需要稍做变换把节点的指针指向新的节点就可以了。删除的时候类似稍做变换后把指向删除节点的指针指向其他节点也OK了。这里的一切操作就是指针换来换去和内存移动没有关系。(2)为何每次insert之后以前保存的iterator不会失效iterator这里就相当于指向节点的指针内存没有变指向内存的指针怎么会失效呢(当然被删除的那个元素本身已经失效了)。相对于vector来说每一次删除和插入指针都有可能失效调用push_back在尾部插入也是如此。因为为了保证内部数据的连续存放iterator指向的那块内存在删除和插入过程中可能已经被其他内存覆盖或者内存已经被释放了。即使时push_back的时候容器内部空间可能不够需要一块新的更大的内存只有把以前的内存释放申请新的更大的内存复制已有的数据元素到新的内存最后把需要插入的元素放到最后那么以前的内存指针自然就不可用了。特别时在和find等算法在一起使用的时候牢记这个原则不要使用过期的iterator。(3)当数据元素增多时set的插入和搜索速度变化如何如果你知道log2的关系你应该就彻底了解这个答案。在set中查找是使用二分查找也就是说如果有16个元素最多需要比较4次就能找到结果有32个元素最多比较5次。那么有10000个呢最多比较的次数为log10000最多为14次如果是20000个元素呢最多不过15次。看见了吧当数据量增大一倍的时候搜索次数只不过多了1次多了1/14的搜索时间而已。你明白这个道理后就可以安心往里面放入元素了。2.set中常用的方法--------------------------------------------------------------------------------begin() ,返回set容器的第一个元素end() ,返回set容器的最后一个元素clear() ,删除set容器中的所有的元素empty() ,判断set容器是否为空max_size() ,返回set容器可能包含的元素最大个数size() ,返回当前set容器中的元素个数rbegin ,返回的值和end()相同rend() ,返回的值和rbegin()相同写一个程序练一练这几个简单操作吧#include #include using namespace std;int main(){set s;s.insert(1);s.insert(2);s.insert(3);s.insert(1);coutcoutcoutcouts.clear();if(s.empty()){cout}coutcoutreturn 0;}运行结果小结插入3之后虽然插入了一个1但是我们发现set中最后一个值仍然是3哈这就是set 。还要注意begin() 和 end()函数是不检查set是否为空的使用前最好使用empty()检验一下set是否为空.--------------------------------------------------------------------------------count() 用来查找set中某个某个键值出现的次数。这个函数在set并不是很实用因为一个键值在set只可能出现0或1次这样就变成了判断某一键值是否在set出现过了。示例代码#include #include using namespace std;int main(){set s;s.insert(1);s.insert(2);s.insert(3);s.insert(1);coutcoutreturn 0;}运行结果equal_range() 返回一对定位器分别表示第一个大于或等于给定关键值的元素和 第一个大于给定关键值的元素这个返回值是一个pair类型如果这一对定位器中哪个返回失败就会等于end()的值。具体这个有什么用途我还没遇到过~~~示例代码#include #include using namespace std;int main(){set s;set::iterator iter;for(int i 1 ; i 5; i){s.insert(i);}for(iter s.begin() ; iter ! s.end() ; iter){cout}coutpair::const_iterator,set::const_iterator pr;pr s.equal_range(3);coutcoutreturn 0;}运行结果erase(iterator) ,删除定位器iterator指向的值erase(first,second),删除定位器first和second之间的值erase(key_value),删除键值key_value的值看看程序吧#include #include using namespace std;int main(){set s;set::const_iterator iter;set::iterator first;set::iterator second;for(int i 1 ; i 10 ; i){s.insert(i);}//第一种删除s.erase(s.begin());//第二种删除first s.begin();second s.begin();second;second;s.erase(first,second);//第三种删除s.erase(8);coutfor(iter s.begin() ; iter ! s.end() ; iter){cout}coutreturn 0;}运行结果小结set中的删除操作是不进行任何的错误检查的比如定位器的是否合法等等所以用的时候自己一定要注意。--------------------------------------------------------------------------------find() 返回给定值值得定位器如果没找到则返回end()。示例代码#include #include using namespace std;int main(){int a[] {1,2,3};set s(a,a3);set::iterator iter;if((iter s.find(2)) ! s.end()){cout}return 0;}insert(key_value); 将key_value插入到set中 返回值是pair::iterator,boolbool标志着插入是否成功而iterator代表插入的位置若key_value已经在set中则iterator表示的key_value在set中的位置。inset(first,second);将定位器first到second之间的元素插入到set中返回值是void.示例代码#include #include using namespace std;int main(){int a[] {1,2,3};set s;set::iterator iter;s.insert(a,a3);for(iter s.begin() ; iter ! s.end() ; iter){cout}coutpair::iterator,bool pr;pr s.insert(5);if(pr.second){cout}return 0;}运行结果lower_bound(key_value) 返回第一个大于等于key_value的定位器upper_bound(key_value)返回最后一个大于等于key_value的定位器示例代码#include #include using namespace std;int main(){set s;s.insert(1);s.insert(3);s.insert(4);coutcoutcoutreturn 0;}运行结果
