一、stack
stack 模板类的定义在<stack>头文件中。
stack 模板类需要两个模板参数,一个是元素类型,一个容器类型,但只有元素类型是必要
的,在不指定容器类型时,默认的容器类型为deque。
定义stack 对象的示例代码如下:
stack<int> s1;
stack<string> s2;
stack 的基本操作有:
入栈,如例:s.push(x);
出栈,如例:s.pop();注意,出栈操作只是删除栈顶元素,并不返回该元素。
访问栈顶,如例:s.top()
判断栈空,如例:s.empty(),当栈空时,返回true。
访问栈中的元素个数,如例:s.size()。
二、queue
queue 模板类的定义在<queue>头文件中。
与stack 模板类很相似,queue 模板类也需要两个模板参数,一个是元素类型,一个容器类
型,元素类型是必要的,容器类型是可选的,默认为deque 类型。
定义queue 对象的示例代码如下:
queue<int> q1;
queue<double> q2;
queue 的基本操作有:
入队,如例:q.push(x); 将x 接到队列的末端。
出队,如例:q.pop(); 弹出队列的第一个元素,注意,并不会返回被弹出元素的值。
访问队首元素,如例:q.front(),即最早被压入队列的元素。
访问队尾元素,如例:q.back(),即最后被压入队列的元素。
判断队列空,如例:q.empty(),当队列空时,返回true。
访问队列中的元素个数,如例:q.size()
三,Set
转自:http://blog.csdn.net/wangran51/article/details/8836160
set集合容器:实现了红黑树的平衡二叉检索树的数据结构,插入元素时,它会自动调整二叉树的排列,把元素放到适当的位置,以保证每个子树根节点键值大于左子树所有节点的键值,小于右子树所有节点的键值;另外,还得保证根节点左子树的高度与右子树高度相等。
平衡二叉检索树使用中序遍历算法,检索效率高于vector、deque和list等容器,另外使用中序遍历可将键值按照从小到大遍历出来。
构造set集合主要目的是为了快速检索,不可直接去修改键值。
常用操作:
1.元素插入:insert()
2.中序遍历:类似vector遍历(用迭代器)
3.反向遍历:利用反向迭代器reverse_iterator。
例:
set<int> s;
......
set<int>::reverse_iterator rit;
for(rit=s.rbegin();rit!=s.rend();rit++)
4.元素删除:与插入一样,可以高效的删除,并自动调整使红黑树平衡。
set<int> s;
s.erase(2); //删除键值为2的元素
s.clear();
5.元素检索:find(),若找到,返回该键值迭代器的位置,否则,返回最后一个元素后面一个位置。
set<int> s;
set<int>::iterator it;
it=s.find(5); //查找键值为5的元素
if(it!=s.end()) //找到
cout<<*it<<endl;
else //未找到
cout<<"未找到";
6.自定义比较函数
(1)元素不是结构体:
例:
//自定义比较函数myComp,重载“()”操作符
struct myComp
{
bool operator()(const your_type &a,const your_type &b)
[
return a.data-b.data>0;
}
}
set<int,myComp>s;
......
set<int,myComp>::iterator it;
(2)如果元素是结构体,可以直接将比较函数写在结构体内。
例:
struct Info
{
string name;
float score;
//重载“<”操作符,自定义排序规则
bool operator < (const Info &a) const
{
//按score从大到小排列
return a.score<score;
}
}
set<Info> s;
......
set<Info>::iterator it;
四,map和unorder_map
转:http://blog.csdn.net/orzlzro/article/details/7099231
今天看到 boost::unordered_map, 它与 stl::map的区别就是,stl::map是按照operator<比较判断元素是否相同,以及比较元素的大小,然后选择合适的位置插入到树 中。所以,如果对map进行遍历(中序遍历)的话,输出的结果是有序的。顺序就是按照operator< 定义的大小排序。
而boost::unordered_map是计算元素的Hash值,根据Hash值判断元素是否相同。所以,对unordered_map进行遍历,结果是无序的。
用法的区别就是,stl::map 的key需要定义operator< 。 而boost::unordered_map需要定义hash_value函数并且重载operator==。对于内置类型,如string,这些都不用 操心。对于自定义的类型做key,就需要自己重载operator< 或者hash_value()了。
最后,说,当不需要结果排好序时,最好用unordered_map。
其实,stl::map对于与java中的TreeMap,而boost::unordered_map对应于java中的HashMap。
stl::map
#include<string>
#include<iostream>
#include<map> using namespace std; struct person
{
string name;
int age; person(string name, int age)
{
this->name = name;
this->age = age;
} bool operator < (const person& p) const
{
return this->age < p.age;
}
}; map<person,int> m;
int main()
{
person p1("Tom1",20);
person p2("Tom2",22);
person p3("Tom3",22);
person p4("Tom4",23);
person p5("Tom5",24);
m.insert(make_pair(p3, 100));
m.insert(make_pair(p4, 100));
m.insert(make_pair(p5, 100));
m.insert(make_pair(p1, 100));
m.insert(make_pair(p2, 100)); for(map<person, int>::iterator iter = m.begin(); iter != m.end(); iter++)
{
cout<<iter->first.name<<"\t"<<iter->first.age<<endl;
} return 0;
}
output:
Tom1 20
Tom3 22
Tom4 23
Tom5 24
operator<的重载一定要定义成const。因为map内部实现时调用operator<的函数好像是const。
由于operator<比较的只是age,所以因为Tom2和Tom3的age相同,所以最终结果里面只有Tom3,没有Tom2
boost::unordered_map
#include<string>
#include<iostream> #include<boost/unordered_map.hpp> using namespace std; struct person
{
string name;
int age; person(string name, int age)
{
this->name = name;
this->age = age;
} bool operator== (const person& p) const
{
return name==p.name && age==p.age;
}
}; size_t hash_value(const person& p)
{
size_t seed = 0;
boost::hash_combine(seed, boost::hash_value(p.name));
boost::hash_combine(seed, boost::hash_value(p.age));
return seed;
} int main()
{
typedef boost::unordered_map<person,int> umap;
umap m;
person p1("Tom1",20);
person p2("Tom2",22);
person p3("Tom3",22);
person p4("Tom4",23);
person p5("Tom5",24);
m.insert(umap::value_type(p3, 100));
m.insert(umap::value_type(p4, 100));
m.insert(umap::value_type(p5, 100));
m.insert(umap::value_type(p1, 100));
m.insert(umap::value_type(p2, 100)); for(umap::iterator iter = m.begin(); iter != m.end(); iter++)
{
cout<<iter->first.name<<"\t"<<iter->first.age<<endl;
} return 0;
}
输出
Tom1 20
Tom5 24
Tom4 23
Tom2 22
Tom3 22
必须要自定义operator==和hash_value。
重载operator==是因为,如果两个元素的hash_value的值相同,并不能断定这两个元素就相同,必须再调用operator==。
当然,如果hash_value的值不同,就不需要调用operator==了。