CODEWITHSUNDEEP
c++cvectorstruct
glarkou
glarkou

Reputation: 7101

Fastest way to find if same struct exist in a vector

Lets suppose that I have a persons struct:

struct Person {
    char name[100];
    char surname[100];
    unsigned int age;
};

I would like to find out the fastest way to search and find if another struct with the same values (same name, same surname, same age) already exist in a vector.

Please keep in mind that I have million of those in a vector.

Thanks

Upvotes: 1

Views: 1304

Answers (2)

Nicu Stiurca
Nicu Stiurca

Reputation: 8677

Based on the comments in the question, specifically

No, I mean a set which describes that 10 was duplicate to 2, 12, 54, etc or 2 was duplicate to 10, 12, 54

it sounds like the data structure you actually want is std::multimap (or std::unordered_multimap if you have C++11 and don't care about order). Multimaps will take care of the bookkeeping you would have to do on your own with M M.'s solution (which is nice overall, except that you have to maintain an additional container with duplicate description). std::multimap does the extra bookkeeping for you.

#include <map>     // or <unordered_map>
#include <string>
#include <tuple>   // std::tie()
#include <utility> // std::make_pair()

struct Person {
  std::string name;
  std::string surname;
  unsigned int age;

  bool operator<(const Person &x) const
  {
    return std::tie(name, surname, age) < std::tie(x.name, x.surname, x.age);
  }
};

extern bool tryReadNextPersonFromFile(Person &, size_t & record_id);

int main()
{
  std::multimap<Person, size_t> persons;
  Person p;
  size_t rid;

  while(tryReadNextPersonFromFile(p, rid)) {
    persons.insert(std::make_pair(p, rid));
  }

  // ...

  p = ...
  size_t howMany = persons.count(p);
  if(0 == howMany) { /* not found ... */ }
  else {
    auto eq_range = persons.equal_range(p);
    for(auto it=eq_range.first; it != eq_range.second; ++it) {
      size_t pRecordID = it->second;
      // ...
    }
  }
}

I'm using a lot of C++11 syntax (like auto) for brevity, but this idea works just as well for C++03. Since you probably haven't heard of multimaps before (or at least are unfamiliar with the STL interface), be sure to check out eg, some documentation on what you can do with it and how.

Upvotes: 0

masoud
masoud

Reputation: 56479

Here is a possibility:

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <tuple>

struct Person {
    std::string name;
    std::string surname;
    unsigned int age;

    bool operator<(const Person &x) const
    {
        return std::tie(name, surname, age) < std::tie(x.name, x.surname, x.age);
    }
};


int main()
{
    std::vector<Person> v;

    // ...

    std::set<Person> s;
    for (const auto &x : v)
    {
        auto i = s.insert(x);
        if (!i.second)
        {
            // x is duplicated
        }
    }
}

To your comment, you can sort your vector by this way:

std::sort(v.begin(), v.end()); // Operator < is overloaded

Upvotes: 2

Related Questions