C++笔记打卡第23天（STL常用算法）

1.常用排序算法

• sort：对容器内元素进行排序

  class Myprint
  {
  public:
      void operator()(int val)
      {
          cout << val << " ";
      }
  };
  
  // 查自定义数据类型
  void test01()
  {
      vector<int> v;
      v.push_back(10);
      v.push_back(20);
      v.push_back(15);
      v.push_back(25);
      v.push_back(0);
      // 利用sort算法升序
      sort(v.begin(), v.end());
      for_each(v.begin(), v.end(), Myprint());
      cout << endl;
  
      // 降序
      sort(v.begin(), v.end(), greater<int>());
      for_each(v.begin(), v.end(), Myprint());
      cout << endl;
  }
  

• random_shuffle：随机调整顺序

  #include<algorithm>
  
  void test01()
  {
      srand((unsigned int)time(NULL));
      vector<int> v;
      for(int i=0; i<10; i++)
      {
          v.push_back(i);
      }
      random_shuffle(v.begin(), v.end());
      for_each(v.begin(), v.end(), Myprint());
      cout << endl;
  }
  

• merge：有序的两个容器元素合并，并存储到另一个容器中，输出仍然是有序的

  void test01()
  {
      vector<int> v1;
      vector<int> v2;
      for(int i=0; i<10; i++)
      {
          v1.push_back(i);
          v2.push_back(i+1);
      }
      vector<int> v3;
      v3.resize(v1.size() + v2.size());
      merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
      // 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10
  }
  

• reverse：反转指定范围的元素

  void test01()
  {
      vector<int> v1;
      for(int i=0; i<10; i++)
      {
          v1.push_back(i);
      }
  
      reverse(v1.begin(), v1.end());  // 9 8 7 6 5 4 3 2 1 0
  }
  

2.常用拷贝和替换算法

• copy：容器内指定范围的元素拷贝到另一容器中

  void test01()
  {
      vector<int> v1;
      for(int i=0; i<10; i++)
      {
          v1.push_back(i);
      }
  
      vector<int> v2;
      v2.resize(v1.size());
      copy(v1.begin(), v1.end(), v2.begin()); // 0 1 2 3 4 5 6 7 8 9
  }
  

• replace：将容器内指定范围的旧元素修改为新元素

  void test01()
  {
      vector<int> v1;
      for(int i=0; i<10; i++)
      {
          v1.push_back(i);
      }
      // 将容器内所有的1替换为11
      replace(v1.begin(), v1.end(), 1, 11);
  }
  

• replace_if：容器内指定范围满足条件的元素替换为新元素

  class Myprint
  {
  public:
      void operator()(int val)
      {
          cout << val << " ";
      }
  };
  
  class MyCompare
  {
  public:
      bool operator()(int val)
      {
          return val > 7;
      }
  };
  
  void test01()
  {
      vector<int> v1;
      for(int i=0; i<10; i++)
      {
          v1.push_back(i);
      }
      // 将大于等于7的替换为100
      replace_if(v1.begin(), v1.end(), MyCompare(), 100);
  }
  

• swap：交换两个同种类型的容器内的元素

  void test01()
  {
      vector<int> v1;
      vector<int> v2;
      for(int i=0; i<10; i++)
      {
          v1.push_back(i);
          v2.push_back(i+100);
      }
  
      swap(v1, v2);
  }
  

3.常用算术生成算法

• 算术生成算法属于小型算法，使用时包含的头文件为 #include<numeric>

• accumulate：计算容器元素累计总和

  #include<numeric>
  
  void test01()
  {
      vector<int> v1;
      for(int i=0; i<=100; i++)
      {
          v1.push_back(i);
      }
      // 从0开始将所有元素加起来
      int total = accumulate(v1.begin(), v1.end(), 0);
      cout << total << endl;
  }
  

• fill：向容器中添加元素

  void test01()
  {
      vector<int> v1;
      v1.resize(10); // 10个0
      // 后期重新填充, 将范围内的值全改为100
      fill(v1.begin(), v1.end(), 100);
      for_each(v1.begin(),v1.end(), Myprint());
      cout << endl;
  }
  

4.常用集合算法

• set_intersection：求两个容器的交集

  void test01()
  {
      vector<int> v1;
      vector<int> v2;
      for(int i=0; i<10; i++)
      {
          v1.push_back(i);
          v2.push_back(i+2);
      }
      vector<int> v3;
      // 极限情况：一个容器是另一个容器的子集
      v3.resize(min(v1.size(), v2.size()));
      // 获取交集，返回末尾的迭代器
      vector<int>::iterator itEnd = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
      for_each(v3.begin(), itEnd, Myprint());
      cout << endl;
  }
  

• set_union：求两个容器的并集**（两个集合必须是有序的序列）**

  void test01()
  {
      vector<int> v1;
      vector<int> v2;
      for(int i=0; i<10; i++)
      {
          v1.push_back(i);
          v2.push_back(i+2);
      }
      vector<int> v3;
      // 极限情况：两个容器没有交集
      v3.resize(v1.size()+v2.size());
      // 获取交集，返回并集中最后一个元素的位置
      vector<int>::iterator itEnd = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
      for_each(v3.begin(), itEnd, Myprint());
      cout << endl;
  }
  

• set_difference：求两个容器的差集

  void test01()
  {
      vector<int> v1;
      vector<int> v2;
      for(int i=0; i<10; i++)
      {
          v1.push_back(i);
          v2.push_back(i+5);
      }
      vector<int> v3;
      v3.resize(max(v1.size(),v2.size()));
      cout << "v1和v2的差集为:" << endl;
      vector<int>::iterator itEnd = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
      for_each(v3.begin(), itEnd, Myprint());
      cout << endl;
      
      cout << "v2和v1的差集为:" << endl;
      vector<int>::iterator itEnd2 = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), v3.begin());
      for_each(v3.begin(), itEnd2, Myprint());
      cout << endl;
  }