1

私が人の構造体を持っているとしましょう：

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

同じ値 (同じ名前、同じ姓、同じ年齢) を持つ別の構造体がベクトルに既に存在するかどうかを検索して見つける最速の方法を見つけたいと思います。

ベクトルには何百万ものものが含まれていることに注意してください。

ありがとう

4

2 に答える 2

2

ここに可能性があります：

#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
于 2013-03-15T22:49:08.797 に答える
0

質問のコメントに基づいて、具体的には

いいえ、10 が 2、12、54 などに複製された、または 2 が 10、12、54 に複製されたことを説明するセットを意味します

実際に必要なデータ構造のように聞こえますstd::multimap（またはstd::unordered_multimap、C++ 11を使用していて順序を気にしない場合）。Multimaps は、MM のソリューションで自分で行う必要がある簿記を処理します (これは、重複した説明を持つ追加のコンテナーを維持する必要があることを除けば、全体的には素晴らしいことです)。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 インターフェイスに慣れていない) ので、マルチマップで何ができるか、どのようにできるかについてのドキュメントなどを確認してください。

于 2013-03-16T05:47:02.503 に答える