NOIP复赛复习10STL容器与字符串模板.doc

《NOIP复赛复习10STL容器与字符串模板.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、NOIP复赛复习10STL容器与字符串模板STL容器STL 容器是一些模板类，提供了多种组织数据的常用方法。常用的STL容器包括pair（组合）、list（列表，类似于链表）、vector（向量，类似于数组）、priority_queue（优先队列）、set（集合）、map（映射）、stack（栈）等，通过模板的参数我们可以指定容器中的元素类型。1、pair相当于一个Struct，访问方式举个例子：pairp; 那么第一个成员便是p.first、第二个p.second，pair使

2、用起来很方便，简单快速高效，可以当做一个二元struct使用，而且它定义了比较的方法，先根据第一个成员比较，在根据第二个，所以如果你的比较运算符是这样，那么你就不需要定义比较函数了，而struct是不能直接进行比较的，构造pair的方法：make_pair。例：#include   #include   #include   #include   #include   using namespace 

3、std;  const int N = 1010;  typedef pair p;  p a[N];  int main() {      int k = 0;      a[k++] = p(3, 4);      a[k++] = p(3, 100);      a[k++] = p(1, 2);      a[k++] = p(4, 10);      sort(a, a+k, greater

());      for (int i = 0; i < k; i++

4、) printf("%d %d", a[i].first, a[i].second);      return 0;  }  2、Listlist是一个循环链表。这个容器的特点：快速插入和删除。作用和vector差不多，但内部是用链表实现。这个容器不支持随机访问，你不能[]或者利用通用算法操作，比如说要排序的话你只能利用成员函数比如list.sort()，而且很重要的一点，list的size()函数是线性的，因为是以遍历函数distance实现的。例：HDU5127#include 

5、io>  #include   #include   #include   #include   using namespace std;  typedef long long LL;  typedef pair p;  list

 l;  int main() {      int n;      while (scanf("%d", &n), n) {          l.clear();       

6、   for (int i = 0; i < n; i++) {              LL a, b;              int t;              scanf("%d %I64d %I64d", &t, &a, &b);              if (t == 1) l.push_back(p(a, b));              else if (t == -1) l.erase(find(l.begin(), l.end(), p(a, b)));     

7、         else {                  list

::iterator i = l.begin();                  LL ans = i->first * a + i->second * b;                  for (++i; i != l.end(); i++) ans = max(ans, i->first * a + i->second * b);                  printf("%I64d", an

8、s);              }          }      }      return 0;  }   3、vector相当于一个不定长数组，利用这个你可以添加任意多的元素，容器以连续数组的方式存储元素序列，可以将vector 看作是以顺序结构实现的线性表。当我们在程序中需要使用动态数组时，vector将是一个理想的选择。这个完全相当于把一个数组当成一个元素来进行使用了，可以直接相等，赋值操作等。比较经典的使用包括：a、利用vector防止递归爆栈。b、利用vector来