c++学习笔记(二)

STL (Standard Template Library) 标准模版库

• 包含一些常用的算法和数据结构

• 使用STL要 #include

一、sort

• 用法1： sort（数组名+n1，数组名+n2）

  • 能够将该数组 [n1,n2) 范围内的元素从小到大排序（左开右闭区间）

  int a[7] = {15,4,3,5,9,7,0};
  sort(a,a+6);//a[0]到a[5]进行排序
    //结果 3 4 5 7 9 15 0

• 用法2: sort(数组名+n1,数组名+n2,greater() ) 其中T是元素类型

  • 能够将该数组 [n1,n2) 范围内的元素从大到小排序（左开右闭区间）

  int a[7] = {15,4,3,5,9,7,0};
  sort(a+1,a+7,greater<int>());//a[1]到a[6]进行排序
    //结果 15 9 7 5 4 3 0

• 用法3: sort(数组名+n1,数组名+n2, 排序规则结构名() )

  struct 结构名 //用于规定哪个元素排在前哪个元素排在后
  {
    bool operator()(const T & a1,const T & a2) //T是要排序的类型
    {
      //自定义规则  返回true表示a1排前面，否则a2排前面
    }
  }

  • 例子

  struct Student
  {
      char name[20];
      int score;
  };
  
  struct Rule1 //分数从高到低
  {
      bool operator()(const Student &a1,const Student &a2)
      {
          return a1.score > a2.score;
      }
  };
  struct Rule2 //名字按字典序
  {
      bool operator()(const Student &a1,const Student &a2)
      {
          if(strcmp(a1.name,a2.name) < 0)
              return true;
          else
              return false;
      }
  };
  int main()
  {
      Student a[4] ={ {"Alier",78},{"Mestry",66},{"Jane",87},{"Hebe",93}};
      sort(a,a+4,Rule1());//不要忘记Rule1后面的括号 
        //结果 {"Hebe",93},{"Jane",87},{"Alier",78},{"Mestry",66}
      sort(a+1,a+4,Rule2()); 
        //结果{"Hebe",93},{"Alier",78},{"Jane",87},{"Mestry",66}
      return 0;
  }

二、二分查找

1.binary_search

• 用法1: binary_search(数组名+n1,数组名+n2, a) //a是要查找的值

  • 在从小到大排好序的数组中二分查找等于a的元素，查找范围是[n1,n2)。找到返回true，否则返回false

• 用法2: binary_search(数组名+n1,数组名+n2, a, name() ) //a是要查找的值 name是排序规则结构名

  • 在用自定义排序规则排好序的数组中二分查找等于a的元素，查找范围是[n1,n2)。找到返回true，否则返回false
  • 查找时所用的排序规则，必须和该数组所用的排序规则一样（即先用该规则排序 然后用该规则查找）
  • 注意：“等于”的含义并不是==，而是根据排序规则的“等于”

  struct Rule
  {
    bool operator()(const int &a1,const int&a2)
    {
      return a1%10 > a2%10; //按照个位数从大到小排序
    }
  };
  int main()
  {
    int a[6] = {15,6,12,98,7,3};
    sort(a,a+6,Rule());
    cout << binary_search(a,a+6,8,Rule()) << endl; //输出1 
  }

2.lower_bound查找下界

• 用法1： T* lower_bound(数组名+n1,数组名+n2, a )

  • 在从小到大排好序的元素类型为T的数组中查找大于等于a的下标最小的元素，如果找到则返回指向该元素的指针，否则返回指向下标为n2的指针

• 用法2: T* lower_bound(数组名+n1,数组名+n2, a ,name() )

  • 在用自定义排序规则排序好元素类型为T的数组中的查找能够排在a后面的下标最小的元素，如果找到则返回指向该元素的指针，否则返回指向下标为n2的指针

  • 对比记忆： 默认方法是对于从小到大排好序的数组，所以用法2的““能够”排在a后面”相当于用法1的“大于等于”

3.upper_bound查找上界

• 用法1: T* upper_bound(数组名+n1,数组名+n2, a )
  • 在从小到大排好序的元素类型为T的数组中查找大于a的下标最小的元素，如果找到则返回指向该元素的指针，否则返回指向下标为n2的指针
• 用法2: T* lower_bound(数组名+n1,数组名+n2, a ,name() )
  • 在用自定义排序规则排序好元素类型为T的数组中的查找排在a后面的下标最小的元素，如果找到则返回指向该元素的指针，否则返回指向下标为n2的指针

struct Rule
{
  bool operator()(const int &a1,const int&a2)
  {
    return a1%10 < a2%10; //按照个位数从小到大排序
  }
};
int main()
{
  int a[7] = {12,5,3,5,98,21,7};
  sort(a,a+7,Rule()); //排序后 21 12 3 5 5 7 98
  cout << *lower_bound(a,a+7,16,Rule()) << endl;  //输出7 
  cout << lower_bound(a,a+7,15,Rule()) - a << endl; //输出3  第一个5的下标是3 
  if(upper_bound(a,a+7,18,Rule()))
    cout << "can't found" << endl; //上界是98后面，所以找不到该数
  cout << *upper_bound(a,a+7,5,Rule()) << endl //输出7
  return 0;
}

• 筛法求素数

/*
原理：用数组a[i]表示i是不是素数，值为1则是素数，为0则不是。
    首先从2开始，先划去n以内2的所有整数倍（通过置为0），然后再从剩下的数（必然是素数）开始做相同的事,最后剩下的都是素数
*/


#include <iostream>
using namespace std;
#define MAX_NUM 10000000
char isPrime[MAX_NUM + 10]; //要判断MAX_NUM是不是素数还得有isPrime[MAX_NUM] 所以加1
//用char比int省空间
int main()
{
  int i,j;
  for(i = 2;i <= MAX_NUM;i++)
  {
    isPrime[i] = 1;
    }
  for(i = 2;i <= MAX_NUM;i++)
  {
    if(isPrime[i])
    {
      for(j = 2*i;j <= MAX_NUM;j += i)
      {
        isPrime[j] = 0;
      }
        }
    }
  for(i = 2;i <=MAX_NUM;i++)
  {
    if(isPrime[i])
    {
      cout << i<<" ";
        }
    }
  return 0;
}

c++学习笔记(二)

原文：https://www.cnblogs.com/ganguan/p/12250707.html