异构采集

Question

在新版本的C++中，您可以检查项目是否在unordered_set ( HashSet)中，即使该项与unordered_set的类型不同，同时保持O(1)时间复杂性。

，我想找出如何在Swift.中完成这个任务

下面是C++示例：

struct First {
    int data;
    std::string otherData;

    First(int data, std::string otherData) : data(data), otherData(otherData) { }
};
struct Second {
    int data;
    int otherData;

    Second(int data, int otherData) : data(data), otherData(otherData) { }
};

假设我想创建一个unordered_set of First，但是我想检查Second对象是否在Set中，比较它的data字段。你可以这样做：

struct Equal {
    using is_transparent = void;

    template<class F, class S>
    bool operator()(const F& lhs, const S& rhs) const {
        return lhs.data == rhs.data;
    }
};

struct Hash {
    using is_transparent = void;

    template<class T>
    size_t operator()(const T& t) const {
        return std::hash<int>{}(t.data);
    }
};

int main()
{
    std::unordered_set<First, Hash, Equal> set;
    set.insert(First(100, "test"));

    std::cout << set.contains(First(100, "bla")) << "\n"; // true
    std::cout << set.contains(Second(100, 1000)) << "\n"; // true
}

而且这个效果很好。但是，我不知道你如何在Swift中实现这一点。在Swift中，Set和unordered_set是一样的，但是它的contains方法只接受特定的元素(没有重载)。

您可以遍历所有元素，但会丢失O(1) HashSet时间复杂度。

我在想，这在斯威夫特有可能吗？

Answer 1

为了满足基本需求(部分匹配)，可以使用contains(where:)和谓词来比较元素的哈希值和目标的哈希值。

class First:Hashable {
    var data:Int;
    var otherData:String;

    static func == (lhs:First, rhs:First) -> Bool {
        return lhs.data == rhs.data;
    }
    
    init(data:Int, otherData:String) {
        self.data = data;
        self.otherData = otherData;
    }

    func hash(into hasher: inout Hasher) {
        hasher.combine(data)
    }
};

class Second:Hashable {
    var data:Int;
    var otherData:Int;

    static func == (lhs:Second, rhs:Second) -> Bool {
        return lhs.data == rhs.data;
    }

    init(data:Int, otherData:Int) {
        self.data = data;
        self.otherData = otherData;
    }

    func hash(into hasher: inout Hasher) {
        hasher.combine(data)
    }
};

var set: Set = [First(data: 100, otherData: "test")];
print(set.contains(First(data: 100, otherData: "bla")));

var hasher = Hasher();
Second(data: 100, otherData: 1000).hash(into:&hasher);
var target = hasher.finalize();

print(set.contains(where: {(candidate:First) -> Bool in
                       var hasher = Hasher();
                       candidate.hash(into:&hasher);
                       return hasher.finalize() == target;
                   }));

为了满足性能要求，有两个选项(至少)：将hashable数据重构为一个公共基类，或者编写一个扩展方法，该扩展方法使用哈斯可访问数据创建适当类型的临时元素。

将可访问的数据移动到基类是最直接的，尽管生成的Set只在基类中是同质的。此外，如果您无法控制元素类的源，则无法实现此方法。

一旦定义了类，Set.contains(_:)将按需要工作。

class Zeroth:Hashable {
    var data:Int;

    static func == (lhs:Zeroth, rhs:Zeroth) -> Bool {
        return lhs.data == rhs.data;
    }
    
    init(_ data:Int) {
        self.data = data;
    }

    func hash(into hasher: inout Hasher) {
        hasher.combine(data)
    }
};

class First:Zeroth {
    var otherData:String;

    init(data:Int, otherData:String) {
        self.otherData = otherData;
        super.init(data)
    }
};

class Second:Zeroth {
    var otherData:Int;

    init(data:Int, otherData:Int) {
        self.otherData = otherData;
        super.init(data)
    }
};

var test = First(data: 100, otherData: "test");
var bla = First(data: 100, otherData: "bla");

var set: Set<Zeroth> = [test];
print(set.contains(bla));


var member = Second(data: 100, otherData: 1000);

print(set.contains(member));

扩展方法最接近C++接口。使用协议，以便将扩展方法限制为仅散列部分数据的类。下面使用的协议还添加了一个方法partialCopy(from:)，它处理类之间的转换。

protocol DataElement {
    var data:Int {get}
    init(_ data:Int)
    static func partialCopy<Other:DataElement>(from other:Other) -> Self;
}

extension DataElement {
    static func partialCopy<Other:DataElement>(from other:Other) -> Self {
        return Self(other.data);
    }
}

class First:Hashable, DataElement {
    var data:Int;
    var otherData:String = "";

    static func == (lhs:First, rhs:First) -> Bool {
        return lhs.data == rhs.data;
    }

    required init(_ data:Int) {
        self.data = data;
    }
    
    init(data:Int, otherData:String) {
        self.data = data;
        self.otherData = otherData;
    }

    func hash(into hasher: inout Hasher) {
        hasher.combine(data)
    }
};

class Second:Hashable, DataElement {
    var data:Int;
    var otherData:Int = 0;

    static func == (lhs:Second, rhs:Second) -> Bool {
        return lhs.data == rhs.data;
    }

    required init(_ data:Int) {
        self.data = data;
    }
    
    init(data:Int, otherData:Int) {
        self.data = data;
        self.otherData = otherData;
    }

    func hash(into hasher: inout Hasher) {
        hasher.combine(data)
    }
};

var test = First(data: 100, otherData: "test");
var bla = First(data: 100, otherData: "bla");

var set: Set<First> = [test];
print(set.contains(bla));


extension Set where Element:DataElement {
    func contains<Other:DataElement>(matching member:Other) -> Bool {
        let matching : Element = Element.partialCopy(from:member); //Element(member.data);
        return self.contains(matching);
    }
}

var other = Second(data: 100, otherData: 1000);
print(set.contains(matching:other));

Answer 2

方法1

您可以使用枚举将First和Second存储在同一个集合中。您将有一个First的案例和一个Second的案例。

在枚举的Hashable一致性中，您应该散列两个结构之间相同的数据。Equatable一致性只是确保如果散列相等，则它们是等价的，即使枚举大小写不同。

示例：

enum Both: Hashable {
    case first(First)
    case second(Second)

    func hash(into hasher: inout Hasher) {
        switch self {
        case .first(let first):
            hasher.combine(first.data)
        case .second(let second):
            hasher.combine(second.data)
        }
    }

    static func == (lhs: Both, rhs: Both) -> Bool {
        lhs.hashValue == rhs.hashValue
    }
}

struct First {
    let data: Int
    let otherData: String
}

struct Second {
    let data: Int
    let otherData: Int
}

let set: Set<Both> = [.first(First(data: 100, otherData: "test"))]

let first = First(data: 100, otherData: "bla")
print(set.contains(.first(first))) // true

let second = Second(data: 100, otherData: 1000)
print(set.contains(.second(second))) // true

方法2

如果First和Second必须是一个结构，这可能是不可能的。但是，如果它们不这样做，您可以拥有一个执行Hashable一致性的超类。

示例：

class Superclass: Hashable {
    let data: Int

    init(data: Int) {
        self.data = data
    }

    func hash(into hasher: inout Hasher) {
        hasher.combine(data)
    }

    static func == (lhs: Superclass, rhs: Superclass) -> Bool {
        lhs.data == rhs.data
    }
}

class First: Superclass {
    let otherData: String

    init(data: Int, otherData: String) {
        self.otherData = otherData
        super.init(data: data)
    }
}

class Second: Superclass {
    let otherData: Int

    init(data: Int, otherData: Int) {
        self.otherData = otherData
        super.init(data: data)
    }
}

let set: Set<Superclass> = [First(data: 100, otherData: "test")]

let first = First(data: 100, otherData: "bla")
print(set.contains(first)) // true

let second = Second(data: 100, otherData: 1000)
print(set.contains(second)) // true