学步园

#include<iostream><br /> //#include <fstream><br /> #include <algorithm><br /> #include <set><br /> #include <string><br /> using namespace std;</p> <p>struct Comp<br /> {<br /> bool operator()(const string& s1, const string& s2){<br /> if (s1.length() != s2.length())<br /> {<br /> return s1.length()<s2.length();<br /> }<br /> int c1 = count(s1.begin(), s1.end(), '1');<br /> int c2 = count(s2.begin(), s2.end(), '1');<br /> return (c1!=c2 ? c1<c2 : s1<s2);<br /> }<br /> };</p> <p>int main(int argc, char* argv[])<br /> {<br /> //ifstream cin("test.txt");<br /> //ifstream cin("a.txt");<br /> //calculate and store first<br /> multiset<string, Comp> ms;<br /> string s;<br /> while (cin>>s)<br /> {<br /> ms.insert(s);<br /> }<br /> for (multiset<string, Comp>::iterator it=ms.begin();it!=ms.end();++it)<br /> {<br /> cout<<*it<<endl;<br /> }</p> <p> return 0;</p> <p>}

multiset<string, Comp>的使用。

注意Comp结构体的写法

在STL中容器主要有两种，一种是序列式容器，如vector,list和deque；一种是关联式容器，如set,map。其中，序列式容器主要进行迭代算法，而关联式容器主要进行快速查找。

map被定义为一对值,key一般为字符串，value为数值，而set只有一key值，且对于任何key值，仅存储一份，若存储多份相同的key值，必使用multiset。默认情况下，set依所属型别默认的less_than排列。主要函数有find(),upper_bound(),lower_bound().

当然，你要用的话，一般还要用STL的第二个组件,泛型算法。

知道 set 构造是这样的 std::set<type, std::less<type> >其中 std::less<type> 和 std::greater<type> 指明了这两种排序的方式一个是升序，一个是降序，默认是 std::less<type> 升序，这意味着只有两个排序（也可能有自定义的吧），在 set 类中有 insert 这个成员函数，有三个重载，我就说其中两个 insert(x) 和 insert(i, x) 其中 i 表示指示器，x 是值。从上面的程序结果可能看出 sc.insert(sc.begin(), 'E'); 这样的，说明了插入位置但没有意义，都排序成了升序了，感觉就是不管插入到哪里，都最终std::less<type>排序方式排序了，重载的 insert(i, x) 这个函数的功能就没有意义了，多余了吗？insert(i, x) 这种方式下，如果你指明的i正确，那么他就可以加快速度。如果不指明i，那么从头部开始搜索插入位置，时间复杂度为log(n)。如果指明了i，那么从i开始搜索插入位置，如果你的i给得好，那么时间复杂度降为1。

参考：http://blog.csdn.net/leishiwei/archive/2009/11/04/4766653.aspx

http://www.rosoo.net/a/200911/8044.html