c++stl容器之stack,queue,优先队列,以及map

时间:2022-01-25 17:39:28

看了看数据结构的书籍·,我想还是算了吧,数据结构书里面写的有点复杂,而且感觉有点抽象,以至于我不能理解,以后还是要学会看伪代码的,不然以后高端一点的书籍都会·看不懂, 我先看下别人的博客,

现在来总结一下别人的想法,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容器怎么盘冲