How to find if a 2D vector contains a duplicate row?

Question

I want an elegant way to check if

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

etc..I know this isn't how you compare values with an if statement... I figured storing variables into a vector would be the fastest way to properly compare the values as there is a lot of variables that must not equal each other

Edit: Maybe I'm not being that clear, basically I want [x][0],[x][1] to never match [y][0],[y][1]...if either [0] or [1] is different, then it's fine but if ANY of the two pairings match up, then return false.

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

is ok, thus passes the duplicate test

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

failed because there is two pairs of 0,0

The reason so, is because the first row will have values between 2-14 and the second will have values between 0-3. These values represent a 52 card deck and I do not want cards to repeat

Answer 1

Here's a benchmark of a simple solution using a std::vector vs std::map (in another answer here). You can see here that the vector solution is 6x faster(for a small data set):

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);

Changing the code to use std::unordered_map makes it even worse -- a 10x slowdown over std::vector: http://quick-bench.com/aSKrpaW4cZoL2mYJFjy6x1dEvDo

(though I may be hashing poorly)

There may be some optimizing that could be done on the map solution, but it still won't make the map solution faster with this size data set.

The two algorithms seem to even out at around 250 pairs, but there are also further optimizations that can be done on the vector solution to make it scale better.

Answer 2

Use map. It will take O(N) space and O(LogN) to search an element if it is present in the map or not. map.find() helps to find element if present in the map in LogN time. In your case, the element can be a pair.

Here's a sample code:

#include <iostream>
#include <map>
using namespace std;
int main() {
    int i,j,n=3,m=2;
    for(i=0;i<n;i++)
    {
       for(j=0;j<m;j++)
            cin>>a[i][j];
    }
    map< pair<int,int>,bool>m;        // Map key can be a pair and value can be boolean 
    bool unique = true;
    for(i=0;i<n;i++)
    {
        if(m.find(make_pair(a[i][0],a[i][1]))==m.end())    // if pair is not already present in array insert the element in map
            m[make_pair(a[i][0],a[i][1])]=true;
        else        
        {
            unique=false;    // else pair was already present in array
            break;           // break the loop
        }
    }
    if(unique)
        cout<<"true";
    else cout<<"false";
    return 0;
}

Input:
0 0
1 1
0 1
Output:
true

Input:
0 0
1 1 
0 0
Output:
false

Answer 3

Since you are representing a deck of cards, have you considered using enums with bit sets? With that, you can store a combination of cards into a single number and easily compare them. In case of large sets that exceed the precision of int (int has 32 bits), use a std::bitset<N>, where N is the number of items in the set.

#include <iostream>

enum Deck
{
    Jack =  2 << 0,
    Queen = 2 << 1,
    King  = 2 << 2,
    Ace   = 2 << 3
};

void compare_hands(const int hand1, const int hand2)
{
    if (hand1 == hand2)
        std::cout << "Same hand" << std::endl;
    else
        std::cout << "Different hand" << std::endl;
}

int main()
{
    int hand1 = Jack  | Queen;
    int hand2 = King  | Ace;
    int hand3 = Queen | Jack;

    compare_hands(hand1, hand2);
    compare_hands(hand1, hand3);
    compare_hands(hand2, hand3);

    return 0;
}