时间戳

首页 > 解决方案 > 你如何：填充和排序新填充的向量？

c++ - 你如何：填充和排序新填充的向量？

问题描述

我想用出现两次或多次的随机元素填充一个向量，然后对所述向量进行排序。为了尝试解释我所说的这个问题的含义，我将为您提供一个此类向量的示例：

vector<int> myVec = {1, 1, 4, 4, 8, 8, 11, 13, 13}

  1. 用随机元素填充它（例如 1、4、8、11、13）看起来很随机
  2. 使除一个之外的每个元素出现两次（所以看看如何只有一个 11 的“迭代”）
  3. 从小到大排序

我已经设法以这种方式完成了第 3 步：

sort(myVec.begin(), myVec.end());
for(int i = 0; i < 9; ++i) {
    printf("%d", myVec[i]);
}

您将如何执行步骤 1 和 2？某种我想不出的 myVec.insert 或 myVec.push_back 诡计，还是有完全不同的方法？

我最初在考虑myVec.push_back和两个for循环 (int i = 0; i < nr of elements; ++i) 和其中的另一个循环 (int k = 0; k <= i; ++k) 但是我一定搞砸了（我想这样我就可以完成重复的部分，不确定）。

标签： c++vector

解决方案

由于您想首先生成值，因此我们可以更高效地使用插入排序而不是最后的排序。

#include <algorithm>
#include <random>
#include <vector>

// Constant to make the code flexible. Doesn't need to be constexpr.
constexpr int num_values = 10;

// First, create the source of randomness.
std::random_device rand_device;
// Then, build an engine for generating the random values.
std::mt19937 mersenne_engine{rand_device()};
// Finally, specify the distribution of values to generate.
std::uniform_int_distribution<int> value_dist{1, 50};

// Now we're finally ready to fill the vector!
std::vector<int> myVec;
// Reserve the space required for all of the values.
const int capacity = (num_values * 2) - 1;
// NOTE: Actual capacity not guaranteed to be equal, might be greater.
myVec.reserve(capacity);
// Pick the random unique value to place into the vector.
myVec.push_back(value_dist(mersenne_engine));
// Loop until enough values are generated.
while (myVec.size() < capacity) {
    // Choose a random value.
    const int value = value_dist(mersenne_engine);
    // Find the insertion position of the new value.
    const auto it = std::lower_bound(myVec.begin(), myVec.end(), value);
    // Make sure the value doesn't exist yet.
    if (it == myVec.end() || *it != value) {
        // Then insert it twice.
        myVec.insert(it, value);
        myVec.insert(it, value);
    }
}

演示

请注意，如果值分布小于您要插入的元素数量，此策略将无限循环。希望代码足够清晰，您可以进行更改以处理这种情况。

推荐阅读