c++ - 如何查找二维 vector 是否包含重复行？

Question

我想要一种优雅的方式来检查是否

(myvector[0][1] != myvector[1][1] != myvector[2][1]) && (myvector[0][0] != myvector[1][0] != myvector[2][0])

等..我知道这不是你用 if 语句比较值的方式......我认为将变量存储到 vector 中是正确比较值的最快方法，因为有很多变量不能彼此平等

编辑:也许我没说清楚，基本上我希望 [x][0]、[x][1] 永远不匹配 [y][0]、[y][1]...如果[0] 或 [1] 不同，则没关系，但如果两个配对中的任何一个匹配，则返回 false。

{0,0},
{1,1},
{0,1}

没问题，因此通过重复测试

{0,0}, 
{1,1},
{0,0}

失败因为有两对0,0

之所以如此，是因为第一行的值介于 2-14 之间，第二行的值介于 0-3 之间。这些值代表一副 52 张卡片，我不希望卡片重复

Answer 1

这是使用 std::vector 与 std::map 的简单解决方案的基准(在此处的另一个答案中)。你可以在这里看到 vector 解决方案快 6 倍(对于小数据集):

http://quick-bench.com/-fOG_uDO6HRPKqOMgxqchqUXHbo

#include <iostream>
#include <algorithm>
#include <benchmark/benchmark.h>
#include <memory>
#include <vector>

constexpr int width=2;
constexpr int height=16;

static void vector(benchmark::State& state) {
    std::vector<std::vector<int>> data;

    int count = 0;
    for(int i = 0; i < height; i++) {
    data.emplace_back(std::vector<int>());
    for (int j = 0; j < width; j++) {
        data[i].push_back(count++);
    }
    }
    while (state.KeepRunning()) {

    std::vector< std::pair<int,int>>m;        // Map key can be a pair and value can be boolean
    m.reserve(height);
    bool unique = true;
    for(int i=0;i<height;i++)
        {
        if(std::find(m.begin(), m.end(), std::make_pair(data[i][0],data[i][1]))==m.end())    // if pair is not already present in array insert the element in map
            m.emplace_back(std::make_pair(data[i][0],data[i][1])); // nothing to do here
        else
            {
            unique=false;    // else pair was already present in array
            break;           // break the loop
            }
        }
    if(!unique) {
        std::cout<<"unexpected match found";
    }

    }

}
BENCHMARK(vector);

static void set(benchmark::State& state) {
    std::vector<std::vector<int>> data;

    int count = 0;
    for(int i = 0; i < height; i++) {
    data.emplace_back(std::vector<int>());
    for (int j = 0; j < width; j++) {
        data[i].push_back(count++);
    }
    }

    while (state.KeepRunning()) {

    std::map< std::pair<int,int>,bool>m;        // Map key can be a pair and value can be boolean
    bool unique = true;
    for(int i=0;i<height;i++)
        {
        if(m.find(std::make_pair(data[i][0],data[i][1]))==m.end()) {    // if pair is not already present in array insert the element in map
            m[std::make_pair(data[i][0],data[i][1])]=true;
        } else {
            unique=false;    // else pair was already present in array
            break;           // break the loop
        }
        }
    if(!unique) {
        std::cout<<"unexpected duplicate found";
    }
    }
}
BENCHMARK(set);

更改代码以使用 std::unordered_map 会使情况变得更糟——比 std::vector 慢 10 倍:http://quick-bench.com/aSKrpaW4cZoL2mYJFjy6x1dEvDo

(虽然我可能散列得不好)

可能可以对 map 解决方案进行一些优化，但对于这种大小的数据集，它仍然不会使 map 解决方案更快。

这两种算法在大约 250 对时似乎持平，但还可以对 vector 解决方案进行进一步优化，以使其更好地扩展。