[toc]

vector

C++ STL 提供了vector类模板，其对象就是动态数组（或者向量）。如果在插入元素时超过了空间大小会自动分配更大的空间（通常按2倍大小扩容），不会出现上溢出，这就是动态数组的主要优点。

定义

1
2
3
4
5
vector<int>v1; //定义元素为int类型的向量v1
vector<int>v2(10); //指定向量v2的初始大小为10个int元素
vector<double>v3(10,1.25); //指定v3的10个初始元素的初值为1.25
vector<vector<int>>v4; //定义一个元素类型为向量的向量v4
vector<vector<int>>v5(3,vector<int>(5,0)); //定义一个初始化为3行5列且元素为0的二维向量

主要成员函数

• capacity（）：返回向量容器所能容纳的元素的个数。
• resize（n）：调整向量的容器，使其恰好容纳n个元素，增加部分用默认值填充。
• empty（）：判断向量容器是否为空。
• size（）：返回向量的长度。
• [i]：返回向量中下标为i的元素。
• front（）：返回向量的首元素。
• back（）：返回向量的尾元素。
• push_back（）：在向量的尾部添加一个元素。
• insert（pos，e）：在向量的pos位置插入元素e。
• erase（）：删除向量中某个迭代器或者迭代器区间指定的元素。
• clear（）：删除向量中的所有元素。
• begin（）/end（）：用于正向遍历，返回向量中首元素的位置/尾元素的后一个位置。
• rbegin（）/rend（）：用于反向遍历，返回向量中尾元素的位置/首元素的前一个位置。

vector<int>a; //定义一个向量(初始为空),即a=[]
a.resize(3); //a=[0,0,0],容量为3,长度为3
a[1]=2; //a=[0,2,0],容量为3,长度为3
a.push_back(3); //a=[0,2,0,3],容量变为6,长度为4
a.insert(a.begin(),1); //a=[1,0,2,0,3],容量为6,长度为5
a.push_back(4); //a=[1,0,2,0,3,4],容量为6,长度为6
for(auto it=a.begin();it!=a.end();it++)
	printf(＂%d＂, * it); //输出:1 0 2 0 3 4

sort排序函数

内置数据类型的排序

对于内置数据类型的数据，sort（）默认以less（即小于关系函数）作为关系比较函数实现递增排序，为了实现递减排序，需要调用大于关系函数greater。

1
2
3
4
5
6
7
8
9
10
vector<int>v={2,1,5,4,3}; //v={2,1,5,4,3}
sort(v.begin(),v.end(),less<int>()); //指定递增排序
sort(v.begin(),v.end()); //不指定less<int>时默认递增排序
sort(v.begin(),v.end(),greater<int>()); //指定递减排序

//a和b按自定义代码进行比较，如果返回的是true，则a排在b前面；否则a排在b后面
bool cmp(vector<int>& a,vector<int>& b){
    return a<b;
}
sort(a,b,cmp);

自定义数据类型的排序

对于自定义数据类型（如结构体或者类），同样默认以less（即小于关系函数）作为关系比较函数，但需要重载该函数，用户也可以自定义关系函数。在这些重载函数或者关系函数中指定数据的排序顺序（按哪些结构体成员排序，是递增还是递减）。归纳起来，实现排序主要有以下两种方式。

• 方式1

  在声明结构体类型或者类中重载<运算符，以实现按指定成员的递增或者递减排序。

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  struct Stud{
      int no; //学号
      string name; //姓名
      Stud(int n,string na):no(n),name(na){} //构造函数
      bool operator<(const Stud&s)const{ //重载比较函数
          return no<s.no; //用于按no递增排序
      }
  };
    
  int main(){
      Stud a[]={Stud(3,"Marry"),Stud(1,"Smith"),Stud(2,"John")};
      int n=sizeof(a)/sizeof(a[0]);
      //用一对迭代器 [first, last)指定源序列，复制该区间内的元素到新创建的vector中。对于数组，数组名可当作指向首元素的指针，配合指针算术形成区间。等价写法还有使用容器迭代器，如 vector<int> v2(v1.begin(), v1.end());
      vector<Stud>v(a,a+n);
      sort(v.begin(),v.end()); //默认使用<运算符,按no递增排序
      for(auto it=v.begin();it!=v.end();it++)
          cout<<"["<<it->no<<","<<it->name<<"]";
      return 0;
  }
  

• 方式2

  在结构体或类中重载函数调用运算符（），以实现按指定成员递增或者递减排序。

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  struct Stud{
      int no; //学号
      string name; //姓名
      Stud(int n,string na):no(n),name(na){} //构造函数
  };
  struct Cmp{ //方式2:定义关系函数
      bool operator()(const Stud&s,const Stud&t)const{
      	return s.name>t.name; //用于按name递减排序
      }
  };
  int main(){
      Stud a[]={Stud(3,"Mary"),Stud(1,"Smith"),Stud(2,"John")};
      int n=sizeof(a)/sizeof(a[0]);
      vector<Stud>v(a,a+n);
      sort(v.begin(),v.end(),Cmp()); //使用Cmp中的()运算符,按name递减排序
      for(auto it=v.begin();it!=v.end();it++)
      	cout<<"["<<it->no<<","<<it->name<<"]";
      return 0;
  }
  

• 方式3

  C++11及以上版本中可使用lambda表达式方便地指定排序中的比较方式

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  #include <iostream>
  #include <vector>
  #include <algorithm>
  using namespace std;
    
  struct Stud {
      int no;
      string name;
      Stud(int n, string na) : no(n), name(na) {}
  };
    
  int main() {
      Stud a[] = {Stud(3, "Mary"), Stud(1, "Smith"), Stud(2, "John")};
      int n = sizeof(a) / sizeof(a[0]);
      vector<Stud> v(a, a + n);
    
      // 使用 lambda 按 no 升序
      sort(v.begin(), v.end(), [](const Stud& x, const Stud& y) {
          return x.no < y.no;
      });
    
      for (auto it = v.begin(); it != v.end(); ++it)
          cout << "[" << it->no << "," << it->name << "]";
      return 0;
  }
  

  tuple

  tuple 是 C++11 引入的标准库聚合类型（定义在 <tuple> 头文件），可以理解为「通用的匿名结构体」—— 它能存储多个不同类型（也可以是相同类型）的值，无需手动定义 struct，是 C++ 中处理多值聚合的便捷工具。

  核心特性：

  1. 模板参数：tuple<T1, T2, ..., Tn> 中，T1/T2/Tn 是每个元素的类型（本例中都是 int）；

  2. 元素访问：可通过 std::get<索引>(tuple对象) 访问（索引从 0 开始），C++17 后也支持结构化绑定（代码中 auto [_, i, j] = pq.top() 就是这种用法）；

     priority_queue<tuple<int, int, int>> pq;
     int sum_neg = std::get<0>(pq.top());
     int i = std::get<1>(pq.top());
     int j = std::get<2>(pq.top());
     

  3. 比较规则：tuple 支持默认的比较运算符（</> 等），规则是按元素顺序依次比较：先比第 0 个元素，若相等再比第 1 个，依此类推（这对 priority_queue 至关重要）。

优先队列（最大堆）priority_queue

重载结构体的比较运算函数来实现最小堆

// 等价的自定义结构体写法
struct PairInfo {
    int sum_neg;
    int i;
    int j;
    // 重载 < 以适配小顶堆
    bool operator<(const PairInfo& other) const {
        return sum_neg > other.sum_neg; // 小顶堆按 sum_neg 升序
    }
};
priority_queue<PairInfo> pq;

emplace方法会原地构造对象，避免拷贝

priority_queue<tuple<int, int, int>> pq;
pq.emplace(-nums1[0] - nums2[0], 0, 0); // 取相反数变成小顶堆

等价于

pq.push(std::make_tuple(-nums1[0] - nums2[0], 0, 0));

lower_bound和upper_bound

lower_bound 详解

• 定义

​ 在有序区间 [first, last) 中，找到第一个不小于（≥）value 的元素的迭代器；若所有元素都小于 value，返回 last。

• 核心逻辑

  • 升序场景：找「第一个 ≥ value」的位置；

  • 降序场景（需传 greater<T>()）：找「第一个 ≤ value」的位置。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> vec = {1, 2, 3, 3, 3, 4, 5}; // 升序
    int value = 3;

    // 找第一个 >= 3 的元素
    auto it = lower_bound(vec.begin(), vec.end(), value);
    
    cout << "下标：" << it - vec.begin() << endl; // 输出 2（对应第一个3）
    cout << "值：" << *it << endl;               // 输出 3

    // 找 value=6（所有元素都小于6）
    auto it2 = lower_bound(vec.begin(), vec.end(), 6);
    cout << (it2 == vec.end() ? "到达末尾" : "存在") << endl; // 输出 到达末尾
    
    // lower_bound：找第一个 <= 3 的元素（降序下 >= 等价于 <=）
    auto it_lower = lower_bound(vec.begin(), vec.end(), value, greater<int>());
    cout << "lower_bound 下标：" << it_lower - vec.begin() << endl; // 输出 2（第一个3）
    
    return 0;
}

upper_bound 详解

• 定义

​ 在有序区间 [first, last) 中，找到第一个大于（>）value 的元素的迭代器；若所有元素都小于等于 value，返回 last。

• 核心逻辑

  • 升序场景：找「第一个 > value」的位置；

  • 降序场景（需传 greater<T>()）：找「第一个 < value」的位置。

int main() {
    vector<int> vec = {1, 2, 3, 3, 3, 4, 5}; // 升序
    int value = 3;

    // 找第一个 > 3 的元素
    auto it = upper_bound(vec.begin(), vec.end(), value);
    
    cout << "下标：" << it - vec.begin() << endl; // 输出 5（对应4）
    cout << "值：" << *it << endl;               // 输出 4

    // 找 value=5（所有元素都<=5）
    auto it2 = upper_bound(vec.begin(), vec.end(), 5);
    cout << (it2 == vec.end() ? "到达末尾" : "存在") << endl; // 输出 到达末尾
    
    // upper_bound：找第一个 < 3 的元素
    auto it_upper = upper_bound(vec.begin(), vec.end(), value, greater<int>());
    cout << "upper_bound 下标：" << it_upper - vec.begin() << endl; // 输出 5（对应2）
    
    return 0;
}

• Previous
  《衍生证券教程》chapter5 蒙特卡洛方法和二叉树模型介绍
• Next
  python常用库函数小摘