看了看数据结构的书籍·,我想还是算了吧,数据结构书里面写的有点复杂,而且感觉有点抽象,以至于我不能理解,以后还是要学会看伪代码的,不然以后高端一点的书籍都会·看不懂, 我先看下别人的博客,
现在来总结一下别人的想法,1.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()
2.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()
3、priority_queue
这个是重点,优先队列,其可以在队列里面直接实现排序,然后按照一定的优先级来输出元素,这就是优先队列
在<queue>头文件中,还定义了另一个非常有用的模板类priority_queue(优先队列)。优先队列与队列的差别在于优先队列不是按照入队的顺序出队,而是按照队列中元素的优先权顺序出队(默认为大者优先,也可以通过指定算子来指定自己的优先顺序)。
priority_queue模板类有三个模板参数,第一个是元素类型,第二个容器类型,第三个是比较算子。其中后两个都可以省略,默认容器为vector,默认算子为less,即小的往前排,大的往后排(出队时序列尾的元素出队)。
定义priority_queue对象的示例代码如下:
priority_queue<int> q1;
priority_queue< pair<int, int> > q2; // 注意在两个尖括号之间一定要留空格。这个问题我是纠结了好久,自己最后也没有想出来,最后还是请教了大神
(我相信好多人都不会使用这个内定的函数)我吧我写的那个代码粘到最后面前了。
priority_queue<int, vector<int>, greater<int> > q3; // 定义小的先出队
priority_queue的基本操作与queue相同。
初学者在使用priority_queue时,最困难的可能就是如何定义比较算子了。
如果是基本数据类型,或已定义了比较运算符的类,可以直接用STL的less算子和greater算子——默认为使用less算子,即小的往前排,大的先出队。
如果要定义自己的比较算子,方法有多种,这里介绍其中的一种:重载比较运算符。优先队列试图将两个元素x和y代入比较运算符(对less算子,调用 x<y,对greater算子,调用x>y),若结果为真,则x排在y前面,y将先于x出队,反之,则将y排在x前面,x将先出队。
看下面这个简单的示例:
#include <iostream>
#include <queue>
using namespace std;
class T
{
public:
int x, y, z;
T(int a, int b, int c):x(a), y(b), z(c)
{
}
};
bool operator < (const T &t1, const T &t2)
{
return t1.z < t2.z; // 按照z的顺序来决定t1和t2的顺序
}结构体重载还是比较好用的
main()
{
priority_queue<T> q;
q.push(T(4,4,3));
q.push(T(2,2,5));
q.push(T(1,5,4));
q.push(T(3,3,6));
while (!q.empty())
{
T t = q.top(); q.pop();
cout << t.x << " " << t.y << " " << t.z << endl;
}
return 1;
}输出结果为(注意是按照z的顺序从大到小出队的):
3 3 6
2 2 5
1 5 4
4 4 3再看一个按照z的顺序从小到大出队的例子:
#include <iostream>
#include <queue>
using namespace std;
class T
{
public:
int x, y, z;
T(int a, int b, int c):x(a), y(b), z(c)
{
}
};
bool operator > (const T &t1, const T &t2)
{
return t1.z > t2.z;
}
main()
{
priority_queue<T, vector<T>, greater<T> > q;感觉还是这个比较好用!!!
q.push(T(4,4,3));
q.push(T(2,2,5));
q.push(T(1,5,4));
q.push(T(3,3,6));
while (!q.empty())
{
T t = q.top(); q.pop();
cout << t.x << " " << t.y << " " << t.z << endl;
}
return 1;
}输出结果为:
4 4 3
1 5 4
2 2 5
3 3 6如果我们把第一个例子中的比较运算符重载为:
bool operator < (const T &t1, const T &t2)
{
return t1.z > t2.z; // 按照z的顺序来决定t1和t2的顺序
}则第一个例子的程序会得到和第二个例子的程序相同的输出结果。
#include <iostream> #include <queue> using namespace std; //class T //{ //public: // int x, y, z; // T(int a, int b, int c):x(a), y(b), z(c) // { // } //}; //bool operator < (const T &t1, const T &t2) //{ // return t1.z < t2.z; // 按照z的顺序来决定t1和t2的顺序 //} ////运算符重载 int main() { //priority_queue<int, vector<int>, less<int> > q; //priority_queue < pair<int,int > >q; //priority_queue<int, vector<int>, greater<int> >q; priority_queue<pair<int, int>,vector<pair<int, int> >,greater<pair<int, int> > >q;这个应该是定义优先队列的通用式子 // priority_queue<int> q; // 设置一个类的优先队列 q.push(make_pair (3,4));这里要记住,这里应该是一个固定的格式 q.push(make_pair(5,6)) ; q.push (make_pair (1,7)); q.push (make_pair(2,8)); //压队列 // while (!q.empty()) // { // cout << q.top() << endl; //// T t = q.top(); // q.pop(); // // } while(!q.empty()) { pair<int, int>ans;这里的pair是一种类型,所以要定义一下,因为原来传入的是这个类型的数,所以输出也要这个类型的数 ans = q.top(); q.pop(); cout << ans.first << ends << ans.second << endl;这里还使用了first,second(这里只有这两种)其实就相当于定义的结构体,里面以后两个变量,这个只不过是包装好了的, }return 0; }下面就要上重点了,map
刚才发现了一篇比较好的博客也不管是否侵权了,就总结一下他的内容吧(原来用到的是可以判断是否有重复的)
1. map最基本的构造函数;
map<string , int >mapstring; map<int ,string >mapint;
map<sring, char>mapstring; map< char ,string>mapchar;
map<char ,int>mapchar; map<int ,char >mapint;2. map添加数据;
map<int ,string> maplive;
1.maplive.insert(pair<int,string>(102,"aclive"));
2.maplive.insert(map<int,string>::value_type(321,"hai"));
3, maplive[112]="April";//map中最简单最常用的插入添加!
3,map中元素的查找:find()函数返回一个迭代器指向键值为key的元素,如果没找到就返回指向map尾部的迭代器。
map<int ,string >::iterator l_it;;
l_it=maplive.find(112);
if(l_it==maplive.end())
cout<<"we do not find 112"<<endl;
else cout<<"wo find 112"<<endl;4,map中元素的删除:
如果删除112;
map<int ,string >::iterator l_it;;
l_it=maplive.find(112);
if(l_it==maplive.end())
cout<<"we do not find 112"<<endl;
else maplive.erase(l_it); //delete 112;
5,map中 swap的用法:
Map中的swap不是一个容器中的元素交换,而是两个容器交换;
For example:
#include <map>
#include <iostream>using namespace std;
int main( )
{
map <int, int> m1, m2, m3;
map <int, int>::iterator m1_Iter;m1.insert ( pair <int, int> ( 1, 10 ) );
m1.insert ( pair <int, int> ( 2, 20 ) );
m1.insert ( pair <int, int> ( 3, 30 ) );
m2.insert ( pair <int, int> ( 10, 100 ) );
m2.insert ( pair <int, int> ( 20, 200 ) );
m3.insert ( pair <int, int> ( 30, 300 ) );cout << "The original map m1 is:";
for ( m1_Iter = m1.begin( ); m1_Iter != m1.end( ); m1_Iter++ )
cout << " " << m1_Iter->second;
cout << "." << endl;// This is the member function version of swap
//m2 is said to be the argument map; m1 the target map
m1.swap( m2 );cout << "After swapping with m2, map m1 is:";
for ( m1_Iter = m1.begin( ); m1_Iter != m1.end( ); m1_Iter++ )
cout << " " << m1_Iter -> second;
cout << "." << endl;
cout << "After swapping with m2, map m2 is:";
for ( m1_Iter = m2.begin( ); m1_Iter != m2.end( ); m1_Iter++ )
cout << " " << m1_Iter -> second;
cout << "." << endl;
// This is the specialized template version of swap
swap( m1, m3 );cout << "After swapping with m3, map m1 is:";
for ( m1_Iter = m1.begin( ); m1_Iter != m1.end( ); m1_Iter++ )
cout << " " << m1_Iter -> second;
cout << "." << endl;
}6.map的sort问题:
Map中的元素是自动按key升序排序,所以不能对map用sort函数:
For example:
#include <map>
#include <iostream>using namespace std;
int main( )
{
map <int, int> m1;
map <int, int>::iterator m1_Iter;m1.insert ( pair <int, int> ( 1, 20 ) );
m1.insert ( pair <int, int> ( 4, 40 ) );
m1.insert ( pair <int, int> ( 3, 60 ) );
m1.insert ( pair <int, int> ( 2, 50 ) );
m1.insert ( pair <int, int> ( 6, 40 ) );
m1.insert ( pair <int, int> ( 7, 30 ) );cout << "The original map m1 is:"<<endl;
for ( m1_Iter = m1.begin( ); m1_Iter != m1.end( ); m1_Iter++ )
cout << m1_Iter->first<<" "<<m1_Iter->second<<endl;
}
The original map m1 is:
1 20
2 50
3 60
4 40
6 40
7 30
请按任意键继续. . .7, map的基本操作函数:
·
C++ Maps是一种关联式容器,包含“关键字/值”对
begin() 返回指向map头部的迭代器
clear() 删除所有元素
count() 返回指定元素出现的次数
empty() 如果map为空则返回true
end() 返回指向map末尾的迭代器
equal_range() 返回特殊条目的迭代器对
erase() 删除一个元素
find() 查找一个元素
get_allocator() 返回map的配置器
insert() 插入元素
key_comp() 返回比较元素key的函数
lower_bound() 返回键值>=给定元素的第一个位置
max_size() 返回可以容纳的最大元素个数
rbegin() 返回一个指向map尾部的逆向迭代器
rend() 返回一个指向map头部的逆向迭代器
size() 返回map中元素的个数
swap() 交换两个map
upper_bound() 返回键值>给定元素的第一个位置
value_comp() 返回比较元素value的函数以上粉色的内容全部是摘抄自别人的,还望别人不要怪我侵权,因为我实在对着这个map是一窍不通,这个map的最重要的一个作用其实就是映射,即一一对应,等下这里上一道例题,就是关于·map容器怎么盘冲