vector<Edge>の配列とmap<int, set<Edge>>の違い

Question

AtCoder Beginner Contest 035 の D - トレジャーハント を解いているのですが、道の情報を保持するデータ構造の違いにより、通ったり通らなかったりします。

具体的には、道の情報をvector<Edge>の配列として持つとACなのですが、map<int, set<Edge>>として持つとWAになります（Edgeクラス内では、メンバ変数と<演算子の定義を行っています）。

その原因がどうしてもわからないため、質問いたしました。
vector<Edge>の配列とmap<int, set<Edge>>の違いを教えていただけると嬉しいです。

WAのソースコード
ACのソースコード

2つのソースコードのdiff

$ diff wa.cpp ac.cpp 
16c16
< map<int, set<Edge>> edge1, edge2;
---
> vector<Edge> edge1[100010], edge2[100010];
50,51c50,51
<     edge1[a].insert({a, b, c});
<     edge2[b].insert({b, a, c});
---
>     edge1[a].push_back({a, b, c});
>     edge2[b].push_back({b, a, c});

Answer 1

自己解決しました。

C++のsetでは、<演算子を使って重複排除が行われているようです。そして、a < bでもb < aでもない要素同士が同じ要素とみなされます（==演算子は使われないようです）。例えば、以下のコードを実行すると「1」が出力されます。

#include <bits/stdc++.h>

using namespace std;

class Person {
public:
  string name;
  int age;
  bool operator<(const Person &that) const {
    return age < that.age;
  }
};

int main() {
  set<Person> s;
  s.insert({"takaya", 29});
  s.insert({"shunya", 29});
  cout << s.size() << endl;
  return 0;
}

Personクラスの<演算子を次のように書き換えることで、想定外の重複排除は行われなくなりました。

bool operator<(const Person &that) const {
  if (age != that.age) {
    return age < that.age;
  } else {
    return name < that.name;
  }
}

Answer 2

こんにちは。

構造が全く異なりますよ。
vectorの方はpush_backで追加しているので、複数回同じインデックスへEdgeを登録するとそれらが全て登録されます。
mapの方はinsertで追加しているので、複数回同じインデックスへEdgeを登録すると最初のものだけが登録され、残りは無視されます。
恐らく、eget1[index]を枚挙する処理があると思いますが、vectorは登録されたものが全て枚挙され、mapの方は最初の１つだけが枚挙されます。

mapは「既に登録済だったら更にsetへinsertする」というようなコードが必要な筈です。

Comments

[penguinshunya]

こんにちは。回答ありがとうございます！

貼っていただいたリンクはmapのinsertですが、僕の実装のinsertはsetです。これはただのリンクの貼り間違いでしょうか？それとも回答の内容すべてが勘違いによる間違いと考えていいでしょうか？

[Chironian]

ああ、読み違えてました。確かに、setのinsertを呼び出してますね。
となると、その後の枚挙時にでてくる順序の相違でしょうか。
vectorは登録順、setは内部的にソートしている順だったはずです。

[penguinshunya]

列挙順以外は特に異なる点はないでしょうか？（構造の違いは置いておいて）