C++ STL(标准模板库)引入及使用 2

如题目＞▽＜

容器

---

向量 vector// 查找 find()–>查不到返回_set.end()

cout<<*_set.find(100)<<endl;
// 二分查找，直接键入目标值
cout<<*_set.lower_bound(3)<<e ndl;
cout<<*_set.upper_bound(3)<<endl;
vector<int>arr1(10000, 0x3f3f3f3f);//第一个是大小，第二个是初始值

• 传入值

  arr.push_back(1);
  arr.emplace_back(1);//推荐，这个是按引用传递，能快一点
  arr[3]=1;//直接更改

• 大小&容积

  for (int i = 0; i < 10;i++){
      arr.emplace_back(1);//size（大小）与capacity（容积）的比较
      cout << arr.size() << "/" << arr.capacity() << endl;//倍增->log n
  }

• 提取最值&求和

  cout<< *max_element(all(arr))<<endl;//求最大值
  cout<< *minelement(all(arr))<<endl;//求最小值
  cout << accumulate(all(arr), 0);//求和，初值为零

• 重定义大小&清空

  arr.resize(100);
  cout << arr.size() << "/" << arr.capacity() << endl;
  arr.clear();//在size清空的条件下，不清空capacity
  arr.emplace_back(1);
  cout << arr.size() << "/" << arr.capacity() << endl;

• 推荐宏定义

  #define all(arr) arr.begin(),arr.end()
  #define rall(arr) arr.rbegin(),arr.rend()
  #define pb emplace_back

• 离散化(得到大数字的相对大小，有些大数要存到的下标太大存不下)

  sort(all(arr));
  arr.erase(unique(all(arr)), arr.end());

• 邻接表（超好用）

  struct Edge
  {
      int v, cost;
      Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
  };
  vector<Edge> E[N];
  void addEdge(int u,int v,int w=1){
      E[u].emplace_back(Edge(v, w));
  }

  栈 队列 双端队列 stack queue deque

  栈（建议手写，容易被卡）

  stack<int> stk;//建立
  stk.push(1);//推入栈
  cout << stk.top();//输出栈顶
  puts(stk.empty() ? "Yes" : "No");//判断是否空
  if(!stk.empty())
      cout << "size=" <<stk.size();//输出栈的大小
  stk.pop();//弹出栈顶
  stk = stack<int>();//清空栈

  队列

  queue<int> Q;//建立
  Q.push(1);//入队
  cout << Q.front();//输出队首
  Q.pop();//弹出
  Q.empty();
  Q.size(); 

  双端队列（可以O(1)操作队首的vector）

  deque<int> dq(10,1);//初始化构造
  //int arr[]={1,2,3,4,5};
  //deque<int> dq(begin(arr),end(arr));//数组构造
  
  dq.pop_front();//弹出队首
  dq.pop_back();//弹出队尾

• 单调队列(滑动窗口的最值)
  题目

  void mono_queue(const vector<int>&V,int m){//传入vector的引用及滑动窗口的大小
      int n = V.size();
      deque<int> Q;
      for (int i = 0; i < n;i++){
          if(!Q.empty()&&i-Q.front()>=m)
              Q.pop_front();
          while(!Q.empty()&&V[Q.back()]<V[i])
              Q.pop_back();
          Q.push_back(i);
          if(i>=m-1){
              cout << V[Q.front()] << " ";
          }
      }
  }

  集合 Set

• 基于红黑树(RB-tree)实现，特点是元素具有互异性

• 优点：有序容器，能实现高效插入、查找、删除（Ologn）

• 使用multiset可以允许元素重复

  set<int> _set;//默认升序
  //set<int,greater<int> > _set;//加入降序比较器
  // insert 返回值为 pair<set<class>::iterator,bool>
  _set.insert(1);_set.insert(2);_set.insert(3);_set.insert(1);
  //set 的迭代器是只读的->const_iterator
  
  // 查找 find()-->查不到返回_set.end()
  cout<<*_set.find(100)<<endl;
  // 二分查找，直接键入目标值
  cout<<*_set.lower_bound(3)<<endl;
  cout<<*_set.upper_bound(3)<<endl;
  
  // erase 删除元素
  _set.erase(1);
  //删除元素指引位置
  _set.erase(_set.insert(454).x);
  //删除一段区间
  _set.erase(_set.lower_bound(114),_set.lower_bound(514));//删除[114,514]内的值

  映射 Map

• 同样基于红黑树(RB-tree)的有序容器（按照key排序）,map可建立[数据结构]到[数据结构]的映射，可以说是very good

• 通常使用场景在于离散化、建立映射关系等等。它同样支持高效插入，查询，修改(可修改value，不能修改key)，以及删除

• 每个key(键)只能出现一次，不允许重复。

  //前两个是类型，后面的是比较方式
  map<string,int,comp>mp;
  // insert(k,v) -->pair<key,value>  -->p.first p.second
  mp.insert({"daisuke",520});
  
  //使用重载的[]输出，或者迭代器输出
  cout<<mp["daisuke"]<<endl;
  for(auto p:mp)
      cout<<p.first<<":"<<p.second<<endl;
  
  // 查找 find()-->查不到返回_set.end()
  cout<<mp.find(100)->second<<endl;
  // 二分查找，直接键入目标值
  cout<<mp.lower_bound(3)->second<<endl;
  cout<<mp.upper_bound(3)->second<<endl;
  
  //排序方式，先看长度，再看字典序
  struct comp{
      bool operator()(const string&a,const string&b)const{
          int la=a.size();
          int lb=b.size();
          return la!=lb?la<lb:a<b;
      }
  }
  
  // 键值是否出现过(这个复杂度还不如直接用lower_bound)
  puts(mp.count("daisuke")?"Yes":"No");

  无序哈希表 unordered_x

  优点：查询速度很快
  缺点：哈希表建立比较耗费时间
  适用：查找较多时

赏

来根小鱼干好吗o( =·ω·= )m

支付宝

微信