知识点总结——STL相关(持续补充)

---恢复内容开始---

C++ STL 与ACM竞赛相关的应用

1、vector

vector是动态数组,可以理解为是能够根据需要随时申请内存的动态数组。

常用操作如下:

  • 容量
    • vec.size()    向量大小
    • vec.empty()  向量判空 (如果为空==true、不为空==false)
  • 修改
    • vec.push_back()   向向量末尾添加一个元素
    • vec.pop_back()   删除向量末尾元素
    • vec.insert()     向向量中任意位置插入元素
    • vec.erase()    删除任意位置元素
    • vec.swap(,)    交换任意两个位置的向量
    • vec.clear()    清空向量元素
  • 迭代器
    • vec.begin()    开始指针
    • vec.end()    末尾指针
  • 元素访问
    • vec[1],vec[2]   下标直接访问
    • vec.front()    访问第一个元素
    • vec.back()    访问最后一个元素

示例:

#include <bits/stdc++.h>
using namespace std; vector<int>v;///声明部分
int main()
{
v.push_back();
v.push_back();
v.push_back();
v.push_back();
v.push_back();
v.push_back();
v.push_back();///插入元素
if(!v.empty())///判断是否为空
{
v.pop_back();///3 出
v.pop_back();///1 出
v.pop_back();///2 出
}
///迭代器的用法
vector <int> :: iterator it;
for(it=v.begin();it != v.end(); it++)///遍历元素
{
cout<<*it<<endl;
}
v.insert(it,,);///vector 后面会输出 4个0
///插入的位置取决于指针的位置
for(it=v.begin();it != v.end(); it++)///遍历元素
{
cout<<*it<<endl;
}
}

2、set和multiset

set顾名思义就是集合,里面没有重复的元素;但multiset可以有重复的元素,并且能够自动的从小到大排序

常用操作如下:

  • 大小、判空
    • s.size()  返回元素个数
    • s.empty()  判断是否为空
  • 增加、删除函数
    • s.insert()  向集合内插入元素
    • s.erase()  删除集合内有确定值的元素
  • 迭代器
    • iterator insert(iterator it,x):在迭代器it处插入元素x
    • iterator erase(iterator it):删除迭代器指针it处元素
    • iterator erase(iterator first,iterator last):删除[first, last)之间元素
    • iterator begin():返回首元素的迭代器指针
    • iterator end():返回尾元素的迭代器指针   
    • reverse_iterator rbegin():返回尾元素的逆向迭代器指针 (即最后一个)  
    • reverse_iterator rend():返回首元素前一个位置的迭代器指针

示例

为了更好的展示STL中的这个功能,我打算在这里放一道题

UVa 11136  

题目大意:超市抽奖,找到每天消费最多的和消费最少的,拿出来给他们奖励,奖励就是消费之差。

下面是代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
long long maxx,minn,sum; ///根据题目要求要用long long
int k,p,q;
multiset<int >s;
int n;
while(scanf("%d",&n) && n)
{
sum=;
s.clear();///在一次开始之前需要清空multiset
cin>>k;
while(k--)
{
cin>>p;
for(int i=;i<p;i++)
{
cin>>q;
s.insert(q);///multiset的插入操作
}
///multiset 自动排序
minn=*(s.begin()); ///找到最小的(可以重复)
maxx=*(s.rbegin()); ///反序查找第一个,也就是最后一个
///s.end() 表示的是最后一个的下一个 sum+= maxx-minn; s.erase(s.find(maxx)); ///s.erase() 括号里面若是值,会把所有相同重复的都删掉
s.erase(s.find(minn)); ///s.find () 若有,只返回一个值
}
cout<<sum<<endl;
}
}

---恢复内容开始---

C++ STL 与ACM竞赛相关的应用

1、vector

vector是动态数组,可以理解为是能够根据需要随时申请内存的动态数组。

常用操作如下:

  • 容量
    • vec.size()    向量大小
    • vec.empty()  向量判空 (如果为空==true、不为空==false)
  • 修改
    • vec.push_back()   向向量末尾添加一个元素
    • vec.pop_back()   删除向量末尾元素
    • vec.insert()     向向量中任意位置插入元素
    • vec.erase()    删除任意位置元素
    • vec.swap(,)    交换任意两个位置的向量
    • vec.clear()    清空向量元素
  • 迭代器
    • vec.begin()    开始指针
    • vec.end()    末尾指针
  • 元素访问
    • vec[1],vec[2]   下标直接访问
    • vec.front()    访问第一个元素
    • vec.back()    访问最后一个元素

示例:

#include <bits/stdc++.h>
using namespace std; vector<int>v;///声明部分
int main()
{
v.push_back();
v.push_back();
v.push_back();
v.push_back();
v.push_back();
v.push_back();
v.push_back();///插入元素
if(!v.empty())///判断是否为空
{
v.pop_back();///3 出
v.pop_back();///1 出
v.pop_back();///2 出
}
///迭代器的用法
vector <int> :: iterator it;
for(it=v.begin();it != v.end(); it++)///遍历元素
{
cout<<*it<<endl;
}
v.insert(it,,);///vector 后面会输出 4个0
///插入的位置取决于指针的位置
for(it=v.begin();it != v.end(); it++)///遍历元素
{
cout<<*it<<endl;
}
}

2、set和multiset

set顾名思义就是集合,里面没有重复的元素;但multiset可以有重复的元素,并且能够自动的从小到大排序

常用操作如下:

  • 大小、判空
    • s.size()  返回元素个数
    • s.empty()  判断是否为空
  • 增加、删除函数
    • s.insert()  向集合内插入元素
    • s.erase()  删除集合内有确定值的元素
  • 迭代器
    • iterator insert(iterator it,x):在迭代器it处插入元素x
    • iterator erase(iterator it):删除迭代器指针it处元素
    • iterator erase(iterator first,iterator last):删除[first, last)之间元素
    • iterator begin():返回首元素的迭代器指针
    • iterator end():返回尾元素的迭代器指针   
    • reverse_iterator rbegin():返回尾元素的逆向迭代器指针 (即最后一个)  
    • reverse_iterator rend():返回首元素前一个位置的迭代器指针

示例

为了更好的展示STL中的这个功能,我打算在这里放一道题

UVa 11136  

题目大意:超市抽奖,找到每天消费最多的和消费最少的,拿出来给他们奖励,奖励就是消费之差。

下面是代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
long long maxx,minn,sum; ///根据题目要求要用long long
int k,p,q;
multiset<int >s;
int n;
while(scanf("%d",&n) && n)
{
sum=;
s.clear();///在一次开始之前需要清空multiset
cin>>k;
while(k--)
{
cin>>p;
for(int i=;i<p;i++)
{
cin>>q;
s.insert(q);///multiset的插入操作
}
///multiset 自动排序
minn=*(s.begin()); ///找到最小的(可以重复)
maxx=*(s.rbegin()); ///反序查找第一个,也就是最后一个
///s.end() 表示的是最后一个的下一个 sum+= maxx-minn; s.erase(s.find(maxx)); ///s.erase() 括号里面若是值,会把所有相同重复的都删掉
s.erase(s.find(minn)); ///s.find () 若有,只返回一个值
}
cout<<sum<<endl;
}
}
上一篇:布局 android


下一篇:编程算法 - 推断二叉树是不是平衡树 代码(C)