C# List<T>.Contains()の罠（間抜けなだけです）

# はじめに
プログラミングテスト（競技プログラミングみたいなやつ）を解いているときにList\<T>.Contains()を使うと明らかに要素を持っているはずなのにFalseと結果が返ってきた。
なんで？？
今回はList\<T>.Contains()について調査したことをまとめました。

そもそも、List\<T>.Contains()ってなに？
例を紹介します。
```c#
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class ContainsCheck : MonoBehaviour
{
    void Start()
    {
        var list = new List<int>();
        int n = 1;
        list.Add(1);
        list.Add(2);
        list.Add(3);
        Debug.Log(list.Contains(1));
        Debug.Log(list.Contains(n));
        list.Add(n);
        Debug.Log(list.Contains(n));
    }
}

/*
Result
True
True
True
*/
```
このようにList\<T>(可変長配列)にContains()の引数と**同じ要素**がList\<T>に入っていればTrue、入っていない場合はFalseが出力される。この同じ要素という言葉は覚えておいてください。

## 実機環境について
```:実機環境
MacOS  : Monterey 12.2.1
MacBook Air(M1, 2020)
チップ  : Apple M1
Unity : 2021.3.10f1
```
# 結論
値型と参照型の違いです。。。
（**追記：参照型でも問題ないケースもありました下で書き加えました**）
大学に入って卒業して院に進んで長いことプログラミングやってきたつもりがこれかぁ。
まぁ今思い出せてよかったです。
値型と参照型の違いは調べるとたくさん文献が出てきますので調べてみてください。
簡単にいうと値を保持するのが値型で、値を保存しているアドレスを保持するのが参照型です。
（厳密に言うと突っ込まれそうだけど大まかにはこの理解でいいと思う）
では自分が具体的にどんな状況で引っ掛かったのかまとめと検証をしていきます。

# 具体的なケースと検証
問題的に座標を所持しておきたかったのでPositionクラスを作成しました。
ここで「**クラスをわざわざ作らず、タプルを持たせるとかstructにすればいいやん**」って思ったそこのあなた！やめてください！それ以上はやめてください。。。
```c#
using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class ContainsPosition : MonoBehaviour
{
    void Start()
    {
        var list = new List<Position>();
        var pos = new Position(0, 0);
        list.Add(new Position(0, 0));
        list.Add(new Position(3, 0));
        list.Add(new Position(5, 0));

        foreach(var p in list)
            Debug.Log("(" + p.X + ", " + p.Y + ")");

        Debug.Log(list.Contains(pos));
        Debug.Log(list.Contains(new Position(0, 0)));

        list.Add(pos);
        Debug.Log(list.Contains(pos));
        Debug.Log(list.Contains(new Position(0, 0)));
    }
}
public class Position
{
    public int X { get; private set; }
    public int Y { get; private set; }
    public Position(int x, int y)
    {
        X = x;
        Y = y;
    }
}
/* Result
 * (0, 0)
 * (3, 0)
 * (5, 0)
 * False
 * False
 * True
 * False
 */
```
ここでResultを見ると、今リストはlist = {(x, y)=(0, 0), (3, 0), (5, 0)}の３つの要素を持っていることがわかります。
1. 変数posに(0, 0)を代入して、この変数posと同じ要素をリストが持っているか確認します。リストの中身を見るとpos = (0, 0)と同じ値を保持していることは明らかなのでTrueとなるでしょう。
しかし、答えはFalseです。
2. 変数を介さずに引数に直接インスタンスを作るとどうなるか確認します。こちらも(0, 0)を直接代入するのでTrueとなるでしょう。
答えはFalseです。
3. 新たに先ほど作った変数posをリストに加えてリストが変数posを持っているか確認します。この時リストが持つ要素は次のようになっています。list = {(x, y)=(0, 0), (3, 0), (5, 0), (0, 0)}
答えはTrueとなります。
やっとTrueになった。
4. 2と同様にインスタンスを直接引数に代入したら次はTrueとなるのか確認します
答えはFalseです。


## 原因と解決方法
原因は結論で話した通りクラスが参照型なためです。
（しかし、参照型でも問題ないケースもありました！）
1と2,4でなぜFalseになったのか、それはContainsが(x, y)の値を持っているかを判定しているのではなく、同じオブジェクト（アドレス）を保持しているか判定しているからです。
クラスというのはそのクラス(設計図)をもとにnewを用いてインスタンス（実態/実物）のオブジェクトを作り出します。
クラスを用いて作られたものは参照型となります。
リストに加えたnew Position(0, 0)をオブジェクトA（アドレスは0x0001）。
2で判定しているnew Position(0, 0)はオブジェクトB(アドレス0x0002)。
（x, y）の数値は同じですが、参照型なため判定する際に確認するのはオブジェクトのアドレス（0x0001と0x0002）となりFalseです。

グダグダ書きましたが、解決法は
1. list.Add(new Position(x,y))したオブジェクトを別のどこかに控えておく。
Containsで判定するときはその控えたオブジェクトを用いて判定する。
2. クラス内で値型を比較する関数を実装する。
3. そもそもクラスを使わない。
structは値型なのでこれにすれば今の運用でも問題ない。
4. クラスやstructをわざわざ作らずにタプルを利用する。
例を下に記述します。

```cs
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class ContainsCheck : MonoBehaviour
{
    void Start()
    {
        var list = new List<(int, int)>();
        var t = (0, 0);
        list.Add((0, 0));
        list.Add((3, 0));
        list.Add((5, 0));
        Debug.Log(list.Contains(t));
        Debug.Log(list.Contains((0, 0)));
        list.Add(t);
        Debug.Log(list.Contains(t));
    }
}
/* Result
 * True
 * True
 * True
 */
```

5. (**追記**)record型を利用する。
recordはC#9.0で追加された型です。こちらはclassと同じ参照型でありながらContainsが機能します！（すごい！）例を下に記述します。
（**注意**：unityのversionが古いとrecord型が対応していない場合があります）
```cs
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class SampleRecord : MonoBehaviour
{
    void Start()
    {
        var list1 = new List<RecordPosition>();
        list1.Add(new RecordPosition(0, 0));
        Debug.Log("recordPosition: " + list1.Contains(new RecordPosition(0, 0)));

        var list2 = new List<ClassPosition>();
        list2.Add(new ClassPosition(0, 0));
        Debug.Log("classPosition: " + list2.Contains(new ClassPosition(0, 0)));
        Debug.Log("classPositionEquals: " + list2[0].Equals(new ClassPosition(0, 0)));
    }
}
public record RecordPosition(int X, int Y);

public class ClassPosition
{
    public int X { get; private set; }
    public int Y { get; private set; }
    public ClassPosition(int x, int y)
    {
        X = x;
        Y = y;
    }
    public bool Equals(ClassPosition p)
    {
        return X == p.X && Y == p.Y;
    }
}
namespace System.Runtime.CompilerServices
{
    internal static class IsExternalInit { }
}
/*Results
 * recordPosition: True
 * classPosition: False
 * classPositionEquals: True
 */
```
\<**解説**>
classでContainsを判定させるには
1. Addしたオブジェクトを別で保持しておく
2. クラス内に値型を比較する関数を作成する

が挙げられます。
record型では2の比較部分を含んだ型となっています。

またクラスのデータ中心に作られた型なため、recordの定義1行でClassPosition以上の機能を生成してくれます。（詳細は下に記述しました）
Resultsから分かるようにrecord型を使うことでContainsが機能しています。
詳しくは[record型](https://ufcpp.net/study/csharp/datatype/record/)を参照してください。

他にもやりようはいくらでもあると思いますが、ここでは割愛します。

## record型について（補足）
record型を１行定義するだけで次のような機能があります。
```cs
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class SampleRecord : MonoBehaviour
{
    void Start()
    {
        var a = new RecordPosition(0, 0);
        var b = a;
        b = b with { Y = 2 };
        Debug.Log(a + ", " + b);
    }
}
public record RecordPosition(int X, int Y);
namespace System.Runtime.CompilerServices
{
    internal static class IsExternalInit { }
}
 /*Results
 * RecordPosition { X = 0, Y = 0 }, RecordPosition { X = 0, Y = 2 }
 */
```
recordはコンパイルすることでToStringを利用したDebug周りの機能も実装されており、
classであればオブジェクト名(RecordPosition)しか出力されないものが自動的にaやbのデータの中身を出力してくれます。
```cs
namespace System.Runtime.CompilerServices
{
    internal static class IsExternalInit { }
}
```
この部分はrecordを１行で記述する上でのおまじないになり、
recordはこの`public record RecordPosition(int X, int Y);`1行の記述が基本的な運用となるようです。

# まとめ
これを書きながら正直これをまとめる価値はあるのか？と思いました。
プログラミングの初歩ですし、この記事が初学者に向けてとても丁寧にまとめた感じでもないですし。
まぁこれをまとめることで自分への戒めとしたいと思い、まとめました。
うん、２度とこんなミスはしない（）
record便利！

## 余談
リストが長くなるとContainsの判定にかかる計算量も大きくなるため、用途に応じて[PriorityQueue](https://learn.microsoft.com/ja-jp/dotnet/api/system.collections.generic.priorityqueue-2?view=net-7.0)など他のデータ構造も利用しましょう。

この記事内に嘘っぱちの記述、誤りがあった場合はご指摘頂けると幸いです。

# 参考文献
1. [record型](https://ufcpp.net/study/csharp/datatype/record/)　（最終閲覧：2022/02/21）
1. [UnityとC#のversion](https://yotiky.hatenablog.com/entry/2020/06/18/unitycsharp)（最終閲覧：2022/02/21）
3. [【Unity/C#】Predefined type ‘System.Runtime.CompilerServices.IsExternalInit’ is not defined or imported が出たとき](https://shirokurohitsuji.studio/2022/01/12/%E3%80%90unity-c%E3%80%91predefined-type-system-runtime-compilerservices-isexternalinit-is-not-defined-or-imported-%E3%81%8C%E5%87%BA%E3%81%9F%E3%81%A8%E3%81%8D/)(最終閲覧：2022/02/23)