列出vector中各函数时间复杂度

以下是常见 vector 函数的时间复杂度：

1. push_back()：平均时间复杂度 O(1)，最坏时间复杂度 O(n)。

2. pop_back()：平均时间复杂度 O(1)，最坏时间复杂度 O(n)。

3. insert()：平均时间复杂度 O(n)，最坏时间复杂度 O(n)。

4. erase()：平均时间复杂度 O(n)，最坏时间复杂度 O(n)。

5. clear()：线性时间复杂度 O(n)。

6. resize()：线性时间复杂度 O(n)。

7. reserve()：线性时间复杂度 O(n)。

8. operator[]：常数时间复杂度 O(1)。

9. front()：常数时间复杂度 O(1)。

10. back()：常数时间复杂度 O(1)。

11. empty()：常数时间复杂度 O(1)。

注意，以上时间复杂度仅为参考，实际执行效率还受到多种因素的影响，如硬件性能、编译器优化等。

相关问题

VectorCAST如何查看圈复杂度

VectorCAST提供了一个称为“Test Coverage”的功能，可以帮助您查看程序中的圈复杂度。在VectorCAST中，您可以使用以下步骤查看圈复杂度：

1. 在VectorCAST工具栏中，选择“Test Coverage”选项。
2. 在“Test Coverage”窗口中，选择您要分析的项目和测试集。
3. 点击“Cyclomatic Complexity”选项卡。
4. 在这个选项卡下，您将看到一个名为“Cyclomatic Complexity Summary”的表格，其中列出了每个函数的圈复杂度。
5. 您可以根据需要对结果进行排序、筛选和导出。

除了查看圈复杂度，VectorCAST还可以帮助您分析代码覆盖率、路径覆盖率等测试覆盖率指标，以帮助您更好地理解测试质量和代码质量。

c++实现：问题2：找到石头对。有N个石头，标号为[0，N-1]。我们知道每个石头的重量，不一定为整数。我们想要找到一对石头，即2个石头，它们的重量差为D。 问题A：正式描述问题，明确定义问题，避免歧义。例如：编写一个函数F，函数的输入是...，函数的输出是...。这个问题可能比你想象的要难，请仔细思考。 问题B： 编写你在问题A中描述的函数。 你的算法的空间复杂度是多少？时间复杂度是多少？ 你能够同时实现O（N）的时间复杂度和空间复杂度吗？如果可以，请实现它。 编写一个测试程序来测试你的函数。 a. 请列出你想测试的所有边界情况。 b. 如何验证函数能够正确处理这些边界情况？你能以更系统化的方式做到吗？ 问题C（可选）：与原问题B相同，但这次我们想找到所有重量差为D的石头对。请注意，对(1,4)和对(4,1)被认为是同一对，因此只需要返回一个。你的算法的时间复杂度应该为O(max(R, N))，其中R是结果对数，N是石头数。

问题A：给定N个石头的重量，要求找到一对石头，它们的重量差为D。定义函数findStonePair，输入参数为石头重量数组stones和石头个数N，输出为一对满足条件的石头的下标，如果不存在这样的一对石头，则返回{-1,-1}。

问题B：以下是C++代码实现，时间复杂度为O(NlogN)，空间复杂度为O(1)。

#include <vector>
#include <algorithm>

using namespace std;

vector<int> findStonePair(double* stones, int N, double D)
{
    sort(stones, stones + N);
    for (int i = 0; i < N; i++)
    {
        int j = lower_bound(stones + i + 1, stones + N, stones[i] + D) - stones;
        if (j < N && stones[j] == stones[i] + D)
            return {i, j};
    }
    return {-1, -1};
}

时间复杂度为O(N)，空间复杂度为O(N)的算法：

#include <unordered_set>
#include <vector>

using namespace std;

vector<int> findStonePair(double* stones, int N, double D)
{
    unordered_set<double> st;
    for (int i = 0; i < N; i++)
    {
        if (st.count(stones[i] - D))
            return {i, distance(st.find(stones[i] - D), st.end()) - 1};
        st.insert(stones[i]);
    }
    return {-1, -1};
}

问题C：以下是C++代码实现，时间复杂度为O(max(R, N))，空间复杂度为O(N)。

#include <unordered_set>
#include <unordered_map>
#include <vector>

using namespace std;

vector<vector<int>> findAllStonePairs(double* stones, int N, double D)
{
    unordered_map<double, int> mp;
    for (int i = 0; i < N; i++)
        mp[stones[i]] = i;

    unordered_set<int> visited;
    vector<vector<int>> res;
    for (int i = 0; i < N; i++)
    {
        if (visited.count(i))
            continue;
        visited.insert(i);
        if (mp.count(stones[i] + D))
        {
            int j = mp[stones[i] + D];
            visited.insert(j);
            res.push_back({i, j});
        }
        else if (mp.count(stones[i] - D))
        {
            int j = mp[stones[i] - D];
            visited.insert(j);
            res.push_back({i, j});
        }
    }
    return res;
}

测试程序：

#include <iostream>

int main()
{
    double stones[] = {1.2, 3.4, 5.6, 7.8};
    vector<int> res = findStonePair(stones, 4, 2.2);
    cout << res[0] << " " << res[1] << endl;

    vector<vector<int>> res2 = findAllStonePairs(stones, 4, 2.2);
    for (auto& pair : res2)
        cout << pair[0] << " " << pair[1] << endl;

    return 0;
}

边界情况测试：

1. N=0或N=1，函数返回{-1,-1}，不需要验证。
2. 存在多个满足条件的石头对，测试函数能否正确返回任意一对石头的下标。
3. 所有石头都相同，函数返回{-1,-1}，验证函数是否能够正确处理。
4. D为0，函数能否正确返回一对重量相同的石头的下标。
5. 所有石头均为正数或负数，函数能否正确处理。
6. 所有石头均为0，函数能否正确处理。