質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.59%

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

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 983

penguinshunya

score 161

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});
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

check解決した方法

0

自己解決しました。

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

こんにちは。

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/10/27 14:02

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

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

    キャンセル

  • 2018/10/27 14:06

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

    キャンセル

  • 2018/10/27 14:38

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.59%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る