Самый быстрый способ найти, если же структура существует в векторе

Question

Давайте предположим, что у меня есть человек Struct:

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

Я хотел бы узнать самый быстрый способ поиска и найти, если другая структура с теми же значениями (одно имя, одна и та же фамилия, одинаковый возраст) уже существуют в векторе.

Пожалуйста, имейте в виду, что у меня есть миллион в векторе.

Благодаря

Answer 1

Вот возможность:

#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 
     } 
    } 
} 

К вашему комментарию, вы можете отсортировать вектор по этому пути:

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

Answer 2

на основе замечаний в вопросе, в частности,

Нет, я имею в виду набор, который описывает, что 10 был дубликатом 2, 12, 54, и т.д., или 2 был дубликатом до 10, 12, 54

это звучит как структуры данных, вы на самом деле хотите это std::multimap (или std::unordered_multimap, если у вас есть C++ 11 и не заботятся о порядке). Multimaps позаботится о бухгалтерском учете, который вам придется делать самостоятельно с помощью решения M M. (что хорошо в целом, за исключением того, что вам нужно поддерживать дополнительный контейнер с дублирующимся описанием). std::multimap делает дополнительную бухгалтерию для вас.

#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; 
     // ... 
    } 
    } 
} 

Я использую много C++ 11 синтаксиса (как auto) для краткости, но эта идея работает так же хорошо для C++ 03. Поскольку вы, вероятно, еще не слышали о мультифайлах (или, по крайней мере, не знакомы с интерфейсом STL), обязательно проверьте, например, some documentation о том, что вы можете с ним сделать и как.