以下是针对GESP C++等级考试中vector相关题目的备考教程，结合考试常见题型和解题技巧整理而成：

一、基础操作强化

1. 初始化与基本操作

• 构造方法：

  vector<int> v1; // 空vector
  vector<int> v2(5, 10); // 5个元素，值为10
  vector<int> v3 = {1, 2, 3}; // 初始化列表
  vector<int> v4(v3.begin(), v3.end()); // 迭代器拷贝
  

• 访问元素：

  cout << v[0] << endl; // 通过下标访问（不检查越界）
  cout << v.at(0) << endl; // 安全访问，越界抛异常
  

2. 增删查改

• 添加元素：

  v.push_back(4); // 尾部添加
  v.insert(v.begin() + 1, 5); // 在索引1处插入5
  

• 删除元素：

  v.pop_back(); // 删除尾部元素
  v.erase(v.begin() + 2); // 删除索引2的元素
  v.erase(v.begin() + 1, v.begin() + 3); // 删除区间[1,3)
  

• 修改元素：

  v[0] = 100; // 直接修改
  v.front() = 200; // 修改首元素
  v.back() = 300; // 修改尾元素
  

3. 遍历方法

• 传统循环：

  for (size_t i = 0; i < v.size(); ++i) { /* ... */ }
  

• 迭代器：

  for (auto it = v.begin(); it != v.end(); ++it) { /* ... */ }
  

• 范围for循环：

  for (int num : v) { /* ... */ }
  

二、进阶技巧

1. 排序与查找

• 排序：

  sort(v.begin(), v.end()); // 升序
  sort(v.rbegin(), v.rend()); // 降序
  

• 查找：

  auto it = find(v.begin(), v.end(), target); // 查找第一个匹配元素
  auto pos = distance(v.begin(), it); // 转换为索引
  

  • 二分查找（需有序）：

    bool exists = binary_search(v.begin(), v.end(), target);
    auto lower = lower_bound(v.begin(), v.end(), target); // 第一个≥target的位置
    

2. 高效操作

• 预留空间：

  v.reserve(100); // 预先分配100个元素空间，减少动态扩容次数
  

• 调整大小：

  v.resize(20); // 调整大小为20，超出部分默认补0
  v.resize(20, 5); // 超出部分补5
  

3. 结合算法库

• 统计元素出现次数：

  int count = count(v.begin(), v.end(), target);
  

• 条件查找：

  auto it = find_if(v.begin(), v.end(), [](int x) { return x > 100; });
  

三、典型题型解析

1. 区间查询（GESP八级）

题目：给定数组，查询区间[l, r]内元素x的出现次数。
思路：用map<int, vector<int>>存储每个元素的所有出现位置，再用二分查找快速计算区间内的数量。
代码：

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

map<int, vector<int>> mp;
// 预处理存储元素位置
for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    mp[x].push_back(i);
}
// 查询
int l, r, x;
auto left = lower_bound(mp[x].begin(), mp[x].end(), l);
auto right = upper_bound(mp[x].begin(), mp[x].end(), r);
cout << distance(left, right) << endl;

2. 删除有序数组中的重复项

题目：原地删除有序数组中的重复项，返回新长度。
思路：双指针法，快指针遍历，慢指针记录不重复元素的位置。
代码：

int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) return 0;
    int slow = 0, fast = 1;
    while (fast < nums.size()) {
        if (nums[fast] != nums[slow]) {
            nums[++slow] = nums[fast];
        }
        fast++;
    }
    return slow + 1;
}

3. 子数组最大和

题目：给定数组，求连续子数组的最大和。
思路：动态规划，dp[i]表示以nums[i]结尾的最大子数组和。
代码：

int maxSubArray(vector<int>& nums) {
    int max_sum = nums[0], current = nums[0];
    for (int i = 1; i < nums.size(); ++i) {
        current = max(nums[i], current + nums[i]);
        max_sum = max(max_sum, current);
    }
    return max_sum;
}

四、备考建议

1. 熟悉考试大纲：明确不同等级（如五级、八级）的vector考察范围，重点练习对应难度的题目。
2. 注重代码规范：使用vector时避免越界访问，优先用at()代替[]进行安全检查。
3. 掌握算法效率：对于大规模数据，优先使用二分查找、双指针等高效方法，避免暴力遍历。
4. 模拟真题：通过GESP样题（如P10288）练习，熟悉考试题型和时间限制。

通过以上练习，可系统掌握vector在GESP考试中的应用，提升解题能力和效率。

在 C++ 里，std::vector 本身没有专门用于查找元素的成员函数，但可以借助标准库中的一些算法或者手动编写循环来实现查找功能。下面为你介绍几种常见的查找元素的方法。

1. 手动编写循环查找

方法说明

通过遍历 vector 中的每一个元素，逐个与目标元素进行比较，若找到匹配的元素则返回其位置（索引），若未找到则返回一个特定值（如 -1）。

示例代码

#include <iostream>
#include <vector>

// 查找元素的函数
int findElement(const std::vector<int>& vec, int target) {
    for (size_t i = 0; i < vec.size(); ++i) {
        if (vec[i] == target) {
            return static_cast<int>(i);
        }
    }
    return -1;
}

int main() {
    std::vector<int> vec = {10, 20, 30, 40, 50};
    int target = 30;
    int index = findElement(vec, target);
    if (index != -1) {
        std::cout << "元素 " << target << " 的索引是: " << index << std::endl;
    } else {
        std::cout << "未找到元素 " << target << std::endl;
    }
    return 0;
}

2. 使用 std::find 算法

方法说明

std::find 是 <algorithm> 头文件中的一个标准算法，它用于在指定的范围内查找第一个与目标元素相等的元素。若找到，返回指向该元素的迭代器；若未找到，返回范围的末尾迭代器。

示例代码

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {10, 20, 30, 40, 50};
    int target = 30;
    auto it = std::find(vec.begin(), vec.end(), target);
    if (it != vec.end()) {
        std::cout << "找到元素 " << target << "，索引是: " << std::distance(vec.begin(), it) << std::endl;
    } else {
        std::cout << "未找到元素 " << target << std::endl;
    }
    return 0;
}

3. 使用 std::find_if 算法

方法说明

std::find_if 同样来自 <algorithm> 头文件，它可以根据自定义的条件查找元素。需要传入一个谓词（可以是函数、函数对象或 Lambda 表达式），算法会在指定范围内查找第一个使谓词返回 true 的元素。

示例代码

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {10, 20, 30, 40, 50};
    // 查找第一个大于 25 的元素
    auto it = std::find_if(vec.begin(), vec.end(), [](int num) {
        return num > 25;
    });
    if (it != vec.end()) {
        std::cout << "找到第一个大于 25 的元素: " << *it << "，索引是: " << std::distance(vec.begin(), it) << std::endl;
    } else {
        std::cout << "未找到大于 25 的元素" << std::endl;
    }
    return 0;
}

4. 使用二分查找（前提是 vector 有序）

方法说明

若 vector 中的元素已经按升序排列，可以使用 std::binary_search 或 std::lower_bound、std::upper_bound 进行高效查找。std::binary_search 用于判断元素是否存在，返回 bool 类型；std::lower_bound 返回第一个不小于目标元素的迭代器；std::upper_bound 返回第一个大于目标元素的迭代器。

示例代码

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {10, 20, 30, 40, 50};
    int target = 30;
    // 使用 std::binary_search 判断元素是否存在
    if (std::binary_search(vec.begin(), vec.end(), target)) {
        std::cout << "元素 " << target << " 存在于 vector 中" << std::endl;
    } else {
        std::cout << "元素 " << target << " 不存在于 vector 中" << std::endl;
    }

    // 使用 std::lower_bound 查找第一个不小于目标元素的位置
    auto lower = std::lower_bound(vec.begin(), vec.end(), target);
    if (lower != vec.end()) {
        std::cout << "第一个不小于 " << target << " 的元素是: " << *lower << "，索引是: " << std::distance(vec.begin(), lower) << std::endl;
    }

    return 0;
}

综上所述，你可以根据具体需求和 vector 的特点选择合适的查找方法。手动循环查找简单直接，适用于小规模数据；std::find 是通用的查找方法；std::find_if 可根据自定义条件查找；二分查找则在有序数据下效率更高。

在 C++ 的 std::vector 中，有多种删除元素的方法，下面为你详细介绍这些方法及其使用场景、示例代码。

1. pop_back() 方法

• 功能：该方法用于移除 vector 的最后一个元素。其时间复杂度为 $O(1)$，因为只需要调整 vector 的大小，不需要移动其他元素。
• 示例代码：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    // 使用 pop_back() 删除最后一个元素
    vec.pop_back();
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

2. erase() 方法

• 功能：erase() 方法可以删除 vector 中指定位置或指定范围的元素。删除单个元素时，时间复杂度为 $O(n)$，因为删除元素后，其后的元素都需要向前移动；删除一个范围的元素时，时间复杂度同样为 $O(n)$。
• 示例代码：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // 删除单个元素
    auto it = vec.begin() + 2;
    vec.erase(it);
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 删除一个范围的元素
    auto start = vec.begin();
    auto end = vec.begin() + 2;
    vec.erase(start, end);
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

3. clear() 方法

• 功能：clear() 方法用于删除 vector 中的所有元素，使 vector 变为空。调用该方法后，vector 的大小变为 0，但容量不变。其时间复杂度为 $O(n)$，因为需要遍历 vector 并销毁所有元素。
• 示例代码：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    // 使用 clear() 删除所有元素
    vec.clear();
    std::cout << "Vector size after clear: " << vec.size() << std::endl;
    return 0;
}

4. resize() 方法

• 功能：resize() 方法可以调整 vector 的大小。如果新的大小小于当前大小，超出部分的元素会被删除。其时间复杂度为 $O(m)$，其中 $m$ 是需要删除的元素数量。
• 示例代码：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    // 使用 resize() 删除部分元素
    vec.resize(3);
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

5. 使用 remove() 和 erase() 组合删除特定值的元素

• 功能：std::remove() 是 <algorithm> 头文件中的一个函数，它会将指定值的元素移动到 vector 的末尾，并返回一个指向新的逻辑末尾的迭代器。结合 erase() 方法可以真正删除这些元素。这种方法的时间复杂度为 $O(n)$。
• 示例代码：

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {1, 2, 3, 2, 4, 2, 5};
    // 使用 remove() 和 erase() 删除所有值为 2 的元素
    auto newEnd = std::remove(vec.begin(), vec.end(), 2);
    vec.erase(newEnd, vec.end());
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

综上所述，根据不同的删除需求，可以选择合适的方法。如果只是删除最后一个元素，使用 pop_back()；若要删除指定位置或范围的元素，使用 erase()；删除所有元素用 clear()；调整大小并删除超出部分元素用 resize()；删除特定值的元素则使用 remove() 和 erase() 组合。

在 C++ 的 std::vector 中，有多种添加元素的方法，下面为你详细介绍这些方法及其使用场景和示例代码。

1. push_back() 方法

• 功能：该方法用于在 vector 的末尾添加一个元素。它是最常用的添加元素的方法，时间复杂度为 $O(1)$，不过在 vector 容量不足时，可能需要重新分配内存，这时的时间复杂度会变为 $O(n)$。
• 示例代码：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec;
    // 使用 push_back() 添加元素
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);

    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

2. emplace_back() 方法

• 功能：emplace_back() 同样是在 vector 的末尾添加元素，但它与 push_back() 的区别在于，emplace_back() 可以直接在 vector 的内存位置上构造对象，避免了不必要的拷贝或移动操作，从而提高了性能，尤其是对于需要复杂构造的对象。时间复杂度在不需要重新分配内存时为 $O(1)$。
• 示例代码：

#include <iostream>
#include <vector>
#include <string>

class MyClass {
public:
    MyClass(int value, const std::string& str) : data(value), message(str) {
        std::cout << "Constructed MyClass" << std::endl;
    }
private:
    int data;
    std::string message;
};

int main() {
    std::vector<MyClass> vec;
    // 使用 emplace_back() 直接构造对象
    vec.emplace_back(1, "Hello");
    return 0;
}

3. insert() 方法

• 功能：insert() 方法可以在 vector 的指定位置插入一个或多个元素。该方法的时间复杂度为 $O(n)$，因为插入元素后，其后的元素都需要向后移动。
• 示例代码：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 3, 4};
    // 在指定位置插入一个元素
    auto it = vec.begin() + 2;
    vec.insert(it, 10);

    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 插入多个相同元素
    vec.insert(vec.begin(), 2, 20);

    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 插入另一个 vector 的元素
    std::vector<int> anotherVec = {50, 60};
    vec.insert(vec.end(), anotherVec.begin(), anotherVec.end());

    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

4. emplace() 方法

• 功能：emplace() 方法结合了 insert() 和 emplace_back() 的特点，它可以在指定位置直接构造并插入元素，避免了不必要的拷贝或移动操作，时间复杂度为 $O(n)$。
• 示例代码：

#include <iostream>
#include <vector>
#include <string>

class MyClass {
public:
    MyClass(int value, const std::string& str) : data(value), message(str) {
        std::cout << "Constructed MyClass" << std::endl;
    }
private:
    int data;
    std::string message;
};

int main() {
    std::vector<MyClass> vec;
    // 使用 emplace() 在指定位置构造并插入对象
    auto it = vec.begin();
    vec.emplace(it, 1, "Hello");
    return 0;
}

综上所述，如果你只是简单地在 vector 末尾添加元素，push_back() 和 emplace_back() 是不错的选择；若需要在指定位置插入元素，可使用 insert() 或 emplace() 方法。在处理复杂对象时，优先考虑使用 emplace_back() 和 emplace() 以提高性能。