时间戳

首页 > 解决方案 > C++：程序在向量填充和搜索期间失败

c++ - C++：程序在向量填充和搜索期间失败

问题描述

我正在练习C++ vector，作为练习，我想用 1600 万个随机数填充一个向量，然后找到一个数字第一次出现的位置。到目前为止我实现的代码是这样的：

int getIndexOf(std::vector<int>& v, int num) {
    for(std::size_t i=0; i < v.size(); i++) {
        if(v.at(i) == num) {
            return i;
        }
    }
    return -1;
}

int main() {

    int searchedNumber = 42;
    int vectorSize = 16000000;
    std::vector<int> v(vectorSize);
    for(std::size_t i=0; i < v.size(); i++) {
        v.push_back(rand() % 10000000);
    }

    //Linear search
    auto start = std::chrono::high_resolution_clock::now();

    int position = getIndexOf(v, searchedNumber);

    auto stop = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::seconds>(stop - start);
    std::cout << "The linear search took: " << duration.count() << " seconds" << std::endl;
    std::cout << "The number " << searchedNumber << " occur first at position " << position << std::endl;

    return 0;
}

另外，我只是为一些统计数据测量时间。问题是程序因错误bad_alloc而崩溃，我将其与Running out of stack space链接。所以最初我认为当向量在堆栈上时用这么多数字填充向量将是崩溃的原因，我动态地创建了向量（指针）。但是，我仍然遇到同样的错误。这可能是什么原因？

标签： c++vector

解决方案

    int vectorSize = 16000000;
    std::vector<int> v(vectorSize);
    for(std::size_t i=0; i < v.size(); i++) {
        v.push_back(rand() % 10000000);
    }

这部分很糟糕。push_back()向向量添加一个元素，因此它增加size(). 因此，这个循环不会终止，直到发生不好的事情。

你应该这样做：

    int vectorSize = 16000000;
    std::vector<int> v;
    v.reserve(vectorSize); // allocate memory without actually adding elements
    for(int i=0; i < vectorSize; i++) { // use the known size
        v.push_back(rand() % 10000000);
    }

推荐阅读