C++ vector 使用

2022年6月8日 365点热度 0人点赞 0条评论

引入文件头

#include <vector>
using namespace std;

函数概览

push_back                    // 在数组的最后添加一个数据
pop_back                     // 去掉数组的最后一个数据
at                           // 得到编号位置的数据
begin                        // 得到数组头的指针
end                          // 得到数组的最后一个单元+1 的指针
front                        // 得到数组头的引用
back                         // 得到数组的最后一个单元的引用
max_size                     // 得到 vector 最大可以是多大
capacity                     // 当前 vector 分配的大小
size                         // 当前使用数据的大小
resize                       // 改变当前使用数据的大小, 如果它比当前使用的大, 者填充默认值
reserve                      // 改变当前 vecotr 所分配空间的大小
erase                        // 删除指针指向的数据项
clear                        // 清空当前的 vector
rbegin                       // 将 vector 反转后的开始指针返回 (其实就是原来的 end-1)
rend                         // 将 vector 反转构的结束指针返回 (其实就是原来的 begin-1)
empty                        // 判断 vector 是否为空
swap                         // 与另一个 vector 交换数据

构造函数

vector():                        // 创建一个空 vector
vector(int nSize):               // 创建一个 vector, 元素个数为 nSize
vector(int nSize, const t& t)    // 创建一个 vector, 元素个数为 nSize, 且值均为 t
vector(const vector&)            // 复制构造函数
vector(begin, end):              // 复制 [begin, end) 区间内另一个数组的元素到 vector 中

插入函数

void push_back(const T& x)                       // 向量尾部增加一个元素 X
iterator insert(iterator it, const T& x)         // 向量中迭代器指向元素前增加一个元素 x
iterator insert(iterator it, int n, const T& x)  // 向量中迭代器指向元素前增加 n 个相同的元素 x

// 向量中迭代器指向元素前插入另一个相同类型向量的 [first, last) 间的数据
iterator insert(iterator it, const_iterator first, const_iterator last)

// 将 v2 所有的元素追加到 v1 的末尾
v1.insert(v1.end(), v2.begin(), v2.end());

删除函数

iterator erase(iterator it)                    // 删除向量中迭代器指向元素
iterator erase(iterator first, iterator last)  // 删除向量中[first, last) 中元素
void pop_back()                                // 删除向量中最后一个元素
void clear()                                   // 清空向量中所有元素

遍历函数

reference at(int pos)                          // 返回 pos 位置元素的引用
reference front()                              // 返回首元素的引用
reference back()                               // 返回尾元素的引用
iterator begin()                               // 返回向量头指针, 指向第一个元素
iterator end()                                 // 返回向量尾指针, 指向向量最后一个元素的下一个位置
reverse_iterator rbegin()                      // 反向迭代器, 指向最后一个元素
reverse_iterator rend()                        // 反向迭代器, 指向第一个元素之前的位置

查找/搜索函数

template <class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val);

template <class ForwardIterator, class T>
bool binary_search (ForwardIterator first, ForwardIterator last, const T& val)

template <class ForwardIterator, class T>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);

template <class ForwardIterator, class T>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);

判断函数

bool empty() const               // 判断向量是否为空, 若为空, 则向量中无元素

大小函数

int size() const                 // 返回向量中元素的个数
int capacity() const             // 返回当前向量张红所能容纳的最大元素值
int max_size() const             // 返回最大可允许的 vector 元素数量值

其他函数

void swap(vector&)               // 交换两个同类型向量的数据
void assign(int n, const T& x)   // 设置向量中第 n 个元素的值为 x

void assign(const_iterator first, const_iterator last) // 向量中 [first, last) 中元素设置成当前向量元素

代码片段

初始化

  • 默认初始化, 最常用.
    vector<int> test1;  // 默认初始化, 最常用; 构造一个空的 vector 容器.
  • 拷贝复制.
    vector<int> list2(list1);
    vector<int> list2 = list1;

    通过 list1 建立 list2, 两者内容完全相同.

  • 直接赋值构造.
    vector<int> list = {1, 2, 3, 4, 5, 6, 7.0};

    注: c++98 不可以这样构造
    通过列表中元素的构造, 但是需要注意, 列表中元素的类型必须与 list 的元素类型相同, 否则会进行类型转换.

  • 通过数组构造.
    int a[] ={1, 2, 3, 4, 5};
    vector<int> list3(a, a+5);

    通过数组初始化向量: 区间为左闭右开, 即 (a, a+5)–>a[0]-a[4].
    list3 的值为: {1, 2, 3, 4, 5}.

  • 通过赋值初始化元素
    vector<int> list(7, 3);

    初始化 list 时在 list 中压入 7 个值为 3 的元素, 若 $3$ 的部分缺省, 则会在 list 中压入 7 个 0.

嵌套 vector 初始化

注: C++11 支持, g++ test.cpp -std=c++11

vector<vector<char>> board2 = {
                                  {'X', '.', '.', 'X'},
                                  {'.', '.', 'X', 'X'},
                                  {'X', 'X', '.', '.'}
                              };

二维 vector 的定义

二维数组两种定义方法 (结果一样)

#include <algorithm>
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;

int main() {
  int N = 5, M = 6;
  //定义二维动态数组大小 5 行
  vector<vector<int>> obj(N);
  //动态二维数组为 5 行 6 列, 值全为 0
  for (int i = 0; i < obj.size(); i++) {
    obj[i].resize(M);
  }
  //输出二维动态数组
  for (int i = 0; i < obj.size(); i++) {
    for (int j = 0; j < obj[i].size(); j++) {
      cout << obj[i][j] << " ";
    }
    cout << "\n";
  }
  return 0;
}
#include <algorithm>
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;

int main() {
  int N = 5, M = 6;
  //定义二维动态数组 5 行 6 列
  vector<vector<int>> obj(N, vector<int>(M));
  //输出二维动态数组
  for (int i = 0; i < obj.size(); i++) {
    for (int j = 0; j < obj[i].size(); j++) {
      cout << obj[i][j] << " ";
    }
    cout << "\n";
  }
  return 0;
}

如果想要初始化为 0 还可以这么干:

vector<vector<int> > myvec(n, vector<int>(n, 0));

C 语言中的二维数组初始化为 0:

int myvec[n][n];
memset(myvec, 0, sizeof(myvec));

线性查找

template<class InputIterator, class T> InputIterator
find (InputIterator first, InputIterator last, const T& val) {
  while (first!=last) {
    if (*first==val) return first;
    ++first;
  }
  return last;
}

这个他妈的有点坑, 居然不是二分查找.

二分搜索

在 C++ STL 中的二分搜搜函数有 binary_search, lower_boundupper_bound. 二分搜索只在容器中的元素是排序的时候才能起作用.

template <class ForwardIterator, class T>
bool binary_search (ForwardIterator first, ForwardIterator last, const T& val)

如果元素存在于容器中, 则 binary_search 返回 true, 否则返回 false.

// 这个例子演示了 binary_search 这个函数的使用
#include<bits/stdc++.h>
using namespace std;

int main() {
    // 初始化 vector
    vector<int> arr = {10, 15, 20, 25, 30, 35};

    // 使用 binary_search 检查 15 是否存在
    if (binary_search(arr.begin(), arr.end(), 15))
       cout << "15 exists in vector";
    else
       cout << "15 does not exist";

    cout << endl;

    // 使用 binary_search 检查 23 是否存在
    if (binary_search(arr.begin(), arr.end(), 23))
         cout << "23 exists in vector";
    else
         cout << "23 does not exist";

    cout << endl;
}

输出:

15 exists in vector
23 does not exist

查询下界的元素.

lower_bound(start_ptr, end_ptr, num)

Returns pointer to "position of num" if container contains 1 occurrence of num. Returns pointer to "first position of num" if container contains multiple occurrence of num. Returns pointer to "position of just lower number than num" if container does not contain occurrence of num. Subtracting the pointer to 1st position i.e "vect.begin()" returns the actual index.

// C++ code to demonstrate the working of lower_bound()
#include<bits/stdc++.h>
using namespace std;

int main() {
    // 初始化整型的 vector
    // 比较的值在 vector 中出现了每次
    vector<int> arr1 = {10, 15, 20, 25, 30, 35};

    // 初始化整型的 vector
    // 比较的值在 vector 中出现了多次
    vector<int> arr2 = {10, 15, 20, 20, 25, 30, 35};

    // 初始化整型的 vector
    // 比较的值在 vector 中一次也没有出现
    vector<int> arr3 = {10, 15, 25, 30, 35};

    // 使用 lowner_bound 检查 20 是否存在
    // 只出现了一次
    // 打印结果为 2
    cout << "The position of 20 using lower_bound (in single occurrence case) : ";
    cout << lower_bound(arr1.begin(), arr1.end(), 20) - arr1.begin();

    cout << endl;

    // 使用 lowner_bound 检查 20 是否存在
    // 20 出现了多次
    // 打印结果为 2
    cout << "The position of 20 using lower_bound (in multiple occurrence case) : ";
    cout << lower_bound(arr2.begin(), arr2.end(), 20) - arr2.begin();

    cout << endl;

    // 使用 lowner_bound 检查 20 是否存在
    // 20 一次也没有出现
    // 打印结果为 2
    cout << "The position of 20 using lower_bound (in no occurrence case) : ";
    cout << lower_bound(arr3.begin(), arr3.end(), 20) - arr3.begin();

    cout << endl;
}

输出:

The position of 20 using lower_bound (in single occurrence case) : 2
The position of 20 using lower_bound (in multiple occurrence case) : 2
The position of 20 using lower_bound (in no occurrence case) : 2

查询上界元素.

upper_bound(start_ptr, end_ptr, num)

Returns pointer to "position of next higher number than num" if container contains 1 occurrence of num. Returns pointer to "first position of next higher number than last occurrence of num" if container contains multiple occurrence of num. Returns pointer to "position of next higher number than num" if container does not contain occurrence of num. Subtracting the pointer to 1st position i.e "vect.begin()" returns the actual index.

Binary search is the most efficient search algorithm.

// C++ code to demonstrate the working of upper_bound()
#include<bits/stdc++.h>
using namespace std;

int main() {
    // initializing vector of integers
    // for single occurrence
    vector<int> arr1 = {10, 15, 20, 25, 30, 35};

    // initializing vector of integers
    // for multiple occurrences
    vector<int> arr2 = {10, 15, 20, 20, 25, 30, 35};

    // initializing vector of integers
    // for no occurrence
    vector<int> arr3 = {10, 15, 25, 30, 35};

    // using upper_bound() to check if 20 exists
    // single occurrence
    // prints 3
    cout << "The position of 20 using upper_bound (in single occurrence case) : ";
    cout << upper_bound(arr1.begin(), arr1.end(), 20) - arr1.begin();

    cout << endl;

    // using upper_bound() to check if 20 exists
    // multiple occurrence
    // prints 4
    cout << "The position of 20 using upper_bound (in multiple occurrence case) : ";
    cout << upper_bound(arr2.begin(), arr2.end(), 20) - arr2.begin();

    cout << endl;

    // using upper_bound() to check if 20 exists
    // no occurrence
    // prints 2 ( index of next higher)
    cout << "The position of 20 using upper_bound (in no occurrence case) : ";
    cout << upper_bound(arr3.begin(), arr3.end(), 20) - arr3.begin();

    cout << endl;
}

Output:

The position of 20 using upper_bound (in single occurrence case) : 3
The position of 20 using upper_bound (in multiple occurrence case) : 4
The position of 20 using upper_bound (in no occurrence case) : 2

二分搜索的时间复杂度为: O(logN), 其中 N 是数组中的元素个数.

排序

#include <algorithm>
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;

int main() {
  vector<int> obj;

  obj.push_back(1);
  obj.push_back(3);
  obj.push_back(0);

  sort(obj.begin(), obj.end());

  cout << " 从小到大:" << endl;
  for (int i = 0; i < obj.size(); i++) {
    cout << obj[i] << ",";
  }

  cout << "\n" << endl;

  cout << " 从大到小:" << endl;

  reverse(obj.begin(), obj.end());
  for (int i = 0; i < obj.size(); i++) {
    cout << obj[i] << ",";
  }

  cout << endl;
  return 0;
}

自定义排序

  • 注意 sort 需要头文件 #include <algorithm>
  • 如果想 sort 来降序, 可重写 comp 这个函数
  • 另外重写排序规则这里有坑的, 比较函数中最好都不要用等于号
// 定义比较函数
bool compare(int a, int b) {
  // 升序排列, 如果改为 return a>b, 则为降序
  return a < b;
}

// 调用
sort(a, a + 20, compare);

遍历

  • 索引遍历
    for (int i = 0; i < 10; i++) {
        cout << obj[i] << " ";
    }
  • 迭代器遍历
    // 声明一个迭代器, 来访问 vector 容器, 作用: 遍历或者指向 vector 容器的元素
    vector<int>::iterator it;
    for (it = obj.begin(); it != obj.end(); it++) {
        cout << *it << " ";
    }
  • STL 函数

    void print(int i) {
      cout << i << endl;
    }
    
    int main() {
    
      vector<int> vec = {1, 3, 5, 7, 9};
    
      // lambda 表达式
      for_each(vec.begin(), vec.end(), [](int item) { cout << item << endl; });
      cout << "======== 分隔线 =======" << endl;
      // 传入自定义的处理函数
      for_each(vec.begin(), vec.end(), print);
    }
  • 增强 for 循环 (C++11 增加), T t, T& t, T&& t 都可以
    vector<int> vec = {1, 3, 5, 7, 9};
    for(auto&& i : vec) {
      cout << i << endl;
    }

vector 转 set

vector 转 set

unordered_set<int> set(vec.begin(), vec.end());    // 通过 unordered_set 的构造方法即可获得

使用 vector 的 rbegin()rend() 反向迭代器可以得到升序结果

unordered_set<int> set(vec.rbegin(), vec.rend());

set 转 vector

set 转 vector

vec.assign(set.begin(), set.end());    // 通过 assign() 函数来进行分配

注意: set 没有 rbegin()rend() 反向迭代器

参考

rainbow

没什么大用的码农; 贴图怪; bug制造者; 只会电脑开关机的开发;

文章评论