效率：std::array 对比 std::vector

Question

我在这一行中使用 std::vector：

std::vector<bool> visited(length);

解决a LeetCode problem:

Given an array of integers arr, you are initially positioned at the first index of the array.

In one step you can jump from index i to index:

i + 1 where: i + 1 < arr.length.

i - 1 where: i - 1 >= 0.

j where: arr[i] == arr[j] and i != j.

Return the minimum number of steps to reach the last index of the array.

Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9.

Note that index 9 is the last index of the array.

Constraints:

1 <= arr.length <= 5 * 10^4 -10^8 <= arr[i] <= 10^8

#include <vector>
#include <unordered_map>
#include <queue>

class Solution {
public:
    int minJumps(const std::vector<int>& nums) {
        int length = nums.size();
        std::unordered_map<int, std::vector<int>> value_indices;

        for (int index = 0; index < length; index++) {
            value_indices[nums[index]].push_back(index);
        }

        std::vector<bool> visited(length);
        visited[0] = true;
        std::queue<int> queue;
        queue.push(0);
        int min_steps = 0;

        while (!queue.empty()) {
            for (int size = queue.size(); size > 0; size--) {
                int index = queue.front();
                queue.pop();

                if (index == length - 1) {
                    return min_steps;
                }

                std::vector<int>& next_jumps = value_indices[nums[index]];
                next_jumps.push_back(index - 1);
                next_jumps.push_back(index + 1);

                for (int jump : next_jumps) {
                    if (jump > -1 && jump < length && !visited[jump]) {
                        visited[jump] = true;
                        queue.push(jump);
                    }
                }

                next_jumps.clear();
            }

            min_steps++;
        }

        return 0;
    }
};

似乎 std::array 可能更有效率，但我不确定。我应该使用 std::array 吗？您建议如何使用？还有什么可以使这个解决方案更有效率吗？

Answer 1

a std::array 只是一个奇特的 C++ 对象包装器，与普通 C 数组相同。就像 C 数组一样，需要事先知道大小。如果一个数组在函数中分配，它就像 C 数组一样进入堆栈。如果它是作为 class 的一部分分配的，则数组的存储是从 class.

开始的简单偏移量

出于这个原因，如果您需要访问数组内存中的单元格，因为它很接近，因此很可能在缓存中。

a std::vector 具有动态存储，这意味着存储是在堆上分配的（使用 new 或类似的）。因此，如果您在堆栈上工作，则存储可能很远并且很可能不在缓存中，因此从这个意义上讲可能会更慢。

另一方面，您不需要知道 std::vector 有多大。当向量用完之前分配的存储空间时添加到向量中，它会将数据移动到更大的存储位置。所以在添加时，为了避免不断调整大小，您可以预先 reserve space 来加快速度。

由于存储是非本地的，std::vector 比 std::array 移动得更好。 std::array 和 std::vector 将始终在内存中连续存储数据，因此可以在 O(1) 时间内获取第 n 个元素。

效率：std::array 对比 std::vector

Efficiency: std::array vs. std::vector

c++

arrays

vector

std

Example 1:

Note that index 9 is the last index of the array.

Constraints: