Checking unique elements with a specific criteria in vector

Question

I have a vector of dataItems structure, in which I need to check unique elements, condition 'id' should be different even though all the elements(a, b, c) can be same, then it is unique. Each time after an element added to the vector I need to check uniqueness based on the id(means except 'id' all the other parameters can be same, then true is returned or else false).

#include <iostream>
#include <vector>

struct dataItems
{
    int a, b, c;
    unsigned int id;
};

bool isDataUnique(std::vector<dataItems> &dataList)
{
    bool ret = true;
    for(size_t i = 0; i < dataList.size(); ++i)
    {
        for(size_t j = 0; j < dataList.size(); ++j)
        {
            if(i != j)
            {
                if((dataList.at(i).a == dataList.at(j).a) &&
                    (dataList.at(i).b == dataList.at(j).b) &&
                    (dataList.at(i).a == dataList.at(j).a))
                    {
                        if(dataList.at(i).id == dataList.at(j).id)
                        {
                            ret = false;
                            break;
                        }
                    }
            }
        }
    }
    return ret;
}

 int main()
{
    std::vector<dataItems> v;
    dataItems obj1 = {0}, obj2 = {0};

    obj1.a = obj2.a = 2;
    obj1.b = obj2.b = 3;
    obj1.c = obj2.c = 4;
    //obj1.id = obj2.id = 1; // data is not unique
    obj1.id = 1;
    obj2.id = 2; // as id's are different data is unique

    v.push_back(obj1);
    v.push_back(obj2);

    std::cout << std::boolalpha << isDataUnique(v) << '\n';


    return 0;
}

In c++14, is it possible to optimize as I feel my algorithm is not optimized?

Answer 1

You may be making this a bit harder on yourself than need be. You have a struct and you need to create a collection of the struct with the only constraint that each record have a unique ID. The remaining values may, or may not, be the same, and for logic purposes is irrelevant to your code.

After declaring your struct (and creating a convenient typedef it would make sense to create either a struct or class to hold and manage your data collection.

If a class is used, you can simply declare a private vector holding your data collection, and a private member function to check whether any data added contains a unique ID. For example, you could declare your class and vector of struct similar to:

class items_t {
    std::vector<dataitems_t> data;
    bool unique (dataitems_t d) {
        for (auto& i : data)
            if (i.id == d.id)
                return false;
        return true;
    }
  public:
    ...

Here the unique function checks, prior to the struct holding the proposed new data being made part of your data collection whether the IDs are unique. You can use this in your adddata member functions to check uniqueness. For example if you wanted to prompt for data, you could do something like the following:

    void adddata() {
        dataitems_t tmp;
        std::cout << "enter unique ID for data: ";
        std::cin >> tmp.id;
        if (!unique (tmp)) {
            std::cerr << "error: ID (" << tmp.id << ") is not unique.\n";
        }
        else {
            std::cout << "enter the values for a, b & c: ";
            std::cin >> tmp.a >> tmp.b >> tmp.c;
            data.push_back (tmp);
        }
    }

If you wanted to be able to submit records for inclusion without user interaction, you could do the following:

    void adddata(unsigned id, int a, int b, int c) {
        dataitems_t tmp = { a, b, c, id };
        if (!unique (tmp)) {
            std::cerr << "error: ID(" << tmp.id << ") is not unique.\n";
        }
        else
            data.push_back (tmp);
    }

That would insure that only data with a unique ID ever became part of your collection. You could put it altogether with a short test program similar to:

#include <iostream>
#include <iomanip>
#include <vector>

typedef struct dataItems {
    int a, b, c;
    unsigned int id;
} dataitems_t;

class items_t {
    std::vector<dataitems_t> data;
    bool unique (dataitems_t d) {
        for (auto& i : data)
            if (i.id == d.id)
                return false;
        return true;
    }
  public:
    void adddata() {
        dataitems_t tmp;
        std::cout << "enter unique ID for data: ";
        std::cin >> tmp.id;
        if (!unique (tmp)) {
            std::cerr << "error: ID (" << tmp.id << ") is not unique.\n";
        }
        else {
            std::cout << "enter the values for a, b & c: ";
            std::cin >> tmp.a >> tmp.b >> tmp.c;
            data.push_back (tmp);
        }
    }
    void adddata(unsigned id, int a, int b, int c) {
        dataitems_t tmp = { a, b, c, id };
        if (!unique (tmp)) {
            std::cerr << "error: ID(" << tmp.id << ") is not unique.\n";
        }
        else
            data.push_back (tmp);
    }
    void prndata() {
        std::cout << "\n" << std::setw(8) << std::left << "ID" <<
                    std::setw(8) << std::right << "A" <<
                    std::setw(8) << std::right << "B" <<
                    std::setw(8) << std::right << "C\n\n";
        for (auto& i : data)
            std::cout << std::setw(8) << std::left << i.id <<
                        std::setw(8) << std::right << i.a <<
                        std::setw(8) << std::right << i.b <<
                        std::setw(8) << std::right << i.c << "\n";
    }
};

int main (void) {

    items_t items;

    items.adddata (0, 20, 23, 41);
    items.adddata (1, 20, 31, 99);
    items.adddata (2, 30, 49, 58);
    items.adddata (3,  1, 27, 18);
    items.adddata ();

    items.prndata();

}

Example Use/Output

$ ./bin/vector_data_unique_id
enter unique ID for data: 22
enter the values for a, b & c: 23 06 90

ID             A       B     C

0             20      23      41
1             20      31      99
2             30      49      58
3              1      27      18
22            23       6      90

Now an example where a non-unique ID is entered:

$ ./bin/vector_data_unique_id
enter unique ID for data: 3
error: ID (3) is not unique.

ID             A       B     C

0             20      23      41
1             20      31      99
2             30      49      58
3              1      27      18

Since the ID was non-unique, there was no need to prompt for further a, b, c values as that data was summarily discarded.

Look things over and let me know if you have any further questions.

Answer 2

Sort the list using id as key and then check only adjacent elements for uniqueness (or use std::unique) in O(N)

 sort(begin(dataList), end(dataList), [](const auto &lhs, const auto &rhs) { return lhs.id < rhs.id });

This does not work well with insertions, which would be O(N) now.

Alternatively, you can use std::set with a custom comparator, which you keep additionally to the std::vector, thus checking for duplicate in O(N logN) and inserting in O(logN).

struct comparator {
    bool operator()(const dataItems& lhs, const dataItems& rhs) const {
        return lhs.id < rhs.id;
    }
};
std::set<dataItems, comparator> s;

Answer 3

I may be missing something but if you only need the id to be unique then why check all the elements?

    bool isDataUnique(std::vector<dataItems> &dataList)
    {
        for(size_t i = 0; i < dataList.size(); ++i)
        {
            for(size_t j = i+1; j < dataList.size(); ++j)
            {

              if(dataList.at(i).id == dataList.at(j).id)
               {
                    return false; 
                }
            }
         }
         return true;
     }

As far as efficiency if you are checking for uniqueness only when inserting an item you need only check if the new item you are inserting is not unique. This can be done with one for loop in O(n) time instead of O(n^2) time like you have here. If you keep the list sorted then you could even reduce this to O(logn) time