logo标签列表

在std::map中使用模板作为键

c++templatesdictionary
6
我想知道是否可以将模板作为Map的键。例如:
std::map< <T> , Node> nodes;

实质上，我想做的是能够拥有一堆节点，这些节点包含任意类型的数据，并且以该数据作为键。我认为我可以通过将所述数据转换为二进制并以此作为键来实现，但这样很混乱，我想避免这种情况。
为了澄清，我想能够使用任何类型的变量作为键。例如，如果我有两个节点，一个包含 int 作为其数据，另一个包含 Foo 作为其数据，我想能够使用它们的数据将它们放入同一个映射中。也许映射不是我想要的，我不确定...
你有什么想法吗？ 谢谢！
3
为了实例化该类，您需要选择一个特定类型。然而，您可以查看Boost Any：http://www.boost.org/doc/libs/1_61_0/doc/html/any.html。 - Jim Vargo
你正在尝试做什么还不清楚。 - Slava
运行时还是编译时？如果是编译时，您是否正在寻找template<typename T> constexpr ...？如果是运行时，则使用下面的typeid。 - lorro
虽然对于大量可能的类型来说并不美观，但 Boost.Variant 是一个选项。 - SirGuy
1
同时考虑是否真正需要 std::map，或者 std::unordered_map 是否足够，这将避免为不同类型定义小于比较。 - SirGuy
5个回答
5
如果您没有显式禁用RTTI，请参考nogard的答案。标准类型ID在整个程序中跨DLL是保证唯一的。对于函数的地址则不是这样。
我通常会这样做：
template<typename T>
void type_id(){}

using type_id_t = void(*)();

然后，我像这样使用它：
std::map<type_id_t, Node> nodes;

nodes[type_id<AType>] = Node{...};
nodes[type_id<BType>] = Node{...};

当然，可以使用C++14中的可变模板来增强这个功能。

抱歉，我刚刚重新阅读了问题，现在我更好地理解了它。
你想要的是 std::any，但它只适用于 C++17。你可以使用 boost::any 代替。
代码如下：
std::map<std::any, Node> nodes;

nodes.emplace("string as key", Node{});
nodes.emplace(23, Node{});

只要地图能够以某种方式对std::any的实例进行排序，它就应该可以工作。如果不能，则可以使用哈希映射代替：
std::unordered_map<std::any, Node> nodes;

只要映射表能够散列到任意位置，它就可以工作。
1
@vtleavs 是一种能够保存任何类型值的类型。文档 - Revolver_Ocelot
1
我在这里创建了一个指向标准库文档的链接。如果你需要的话，我可以再次把它粘贴在这里：std::any - Guillaume Racicot
1
@RichardHodges 这就是我提到unordered_map的原因。对any进行哈希可能是可行的。 - Guillaume Racicot
@GuillaumeRacicot 你会如何测试相等性？我已经发布了一个答案，适用于所有的映射和集合类型。 - Richard Hodges
2

我认为在这种情况下，使用std::type_info更容易处理类型：

std::map<std::type_info, std::string> m;
m[typeid(int)] = "integer";

但这真的取决于您想要实现什么，对我来说还不太清楚。希望这有所帮助。
如果不清楚问题是什么，你怎么能回答呢？ - Slava
@HolyBlackCat：实际上，我的gcc 5可以编译它，也许你正在使用旧的编译器？此外，文档明确说明要使用std::type_info，在这里。 - nogard
type_index使用类型作为键吗，还是使用任何类型的键？我希望能够将任何类型的数据用作键，而不是类型本身。 - vtleavs
1
如果我理解你的意思，简短的回答是不行。
映射中的键必须有序--也就是说，对于任何一对键A和B，您必须定义一个有序关系，其中要么A小于B，要么B小于A，要么两个键相等。
给定两个完全不同类型的键，没有定义比较它们的方式。因此，您不能将它们用作映射中的键。
为了得到接近的结果，您需要定义一些特定类型的集合，以支持您想要支持的所有类型（粗略地）。但仅凭这些还不够--您还需要定义排序。根据您想要实现的功能，您可能会在每个对象中都有一个ID，并按ID对其进行排序。或者，您可以定义对象之间的排序，例如，每个“人”都排在每个“狗”之前，每个“梦”之前，依此类推。然后，您必须像通常一样定义每种类型内的排序。

然而，我要警告的是，这通常需要相当多的额外工作，而且提供的回报很少。我认为，在我看到人们（试图）这样做的时间中，超过90%的情况下，这都是一个错误，最好的结果也不如意。如果可能的话，我会尝试找到其他方法来解决你正在尝试解决的问题。

我在考虑是否可能通过它们的二进制值来比较数据，但我不确定能否这样做。 - vtleavs
@vtleavs：不，没有什么实际意义。就举个例子来说，它无法正确处理浮点数值——它们既有负零又有正零，它们应该相互比较相等，但如果你查看位，它们会不同。 - Jerry Coffin
1

您可以创建一个类似于poly_key的类，它将接受任何类型，只要它是：

  • 可复制或可移动（本演示需要可复制）

  • 可比较相等（如果在无序映射中使用）

  • 可比较小于（如果在映射中使用）

  • 可哈希（如果在有序映射中使用）

  • 可输出到流（本演示需要）

如下所示：

#include <iostream>
#include <string>
#include <memory>
#include <unordered_map>
#include <map>
#include <typeinfo>

/// a non-polymorphic container for a polymorphic key type
struct poly_key
{
    /// concept defines the key's capabilities
    struct concept {

        virtual bool equal(const void* other) = 0;
        virtual bool less(const void* other) = 0;
        virtual const void* address() const = 0;
        virtual const std::type_info& type() const = 0;
        virtual std::size_t hash() const = 0;
        virtual std::ostream& emit(std::ostream&) const = 0;
        virtual std::unique_ptr<concept> clone() const = 0;
        virtual ~concept() = default;
    };

    using ptr_type = std::unique_ptr<concept>;

    /// model<> models the concept for any key which supports the required operations
    template<class T>
    struct model : concept {
        model(T&& t) : _t(std::move(t)) {}

        bool equal(const void* other) override {
            return _t == (*reinterpret_cast<const T*>(other));
        }

        bool less(const void* other) override {
            return _t < (*reinterpret_cast<const T*>(other));
        }

        const void* address() const override {
            return std::addressof(_t);
        }
        const std::type_info& type() const override {
            return typeid(_t);
        }

        std::size_t hash() const override {
            return std::hash<T>()(_t);
        }

        std::ostream& emit(std::ostream& os) const override
        {
            return os << _t;
        }

        virtual std::unique_ptr<concept> clone() const override
        {
            return std::make_unique<model>(*this);
        }


        T _t;
    };

    template<class T>
    poly_key(T t) : _impl(std::make_unique<model<T>>(std::move(t))) {}

    std::size_t hash() const {
        return _impl->hash();
    }

    bool operator==(const poly_key& r) const {
        return _impl->type() == r._impl->type()
        && _impl->equal(r._impl->address());
    }

    bool operator<(const poly_key& r) const {
        auto& lt = _impl->type();
        auto& rt = r._impl->type();

        if (lt.before(rt)) {
            return true;
        }
        else if (rt.before(lt)) {
            return false;
        }
        else {
            return _impl->less(r._impl->address());
        }
    }

    poly_key(const poly_key& r)
    : _impl(r._impl->clone())
    {

    }

    poly_key(poly_key&& r)
    : _impl(std::move(r._impl))
    {

    }

    friend std::ostream& operator<<(std::ostream& os, const poly_key& k)
    {
        return k._impl->emit(os);
    }

    ptr_type _impl;
};

/// make it hashable
namespace std {
    template<> struct hash<::poly_key> {
        bool operator()(const ::poly_key& r) const {
            return r.hash();
        }
    };
}

//
// test
//
int main()
{
    std::unordered_map<poly_key, std::string> m;

    m.emplace(poly_key(std::string("key 1")), "Hello");
    m.emplace(poly_key(2), "World");

    std::cout << "unordered:\n";
    for (auto& e : m) {
        std::cout << e.first << " : " << e.second << std::endl;
    }

    std::cout << "\nordered:\n";
    std::map<poly_key, std::string> m2 (m.begin(), m.end());
    for (auto& e : m2) {
        std::cout << e.first << " : " << e.second << std::endl;
    }   
}

示例输出（顺序可能因工具集而异）：

unordered:
2 : World
key 1 : Hello

ordered:
key 1 : Hello
2 : World
0

为你的类型取一个名称，并在地图中使用它：

#include<map>
#include<cassert>

struct B { static int cnt; };
int B::cnt = 0;

template<typename T>
struct D: B { static const int type; };

template<typename T>
const int D<T>::type = B::cnt++;

std::map<int, int> values;

template<typename T>
void set(int value) { values[D<T>::type] = value; }

template<typename T>
int get() { return values[D<T>::type]; }

struct T1 { };
struct T2 { };

int main() {
    set<T1>(42);
    set<T2>(0);
    assert(get<T1>() == 42);
    assert(get<T2>() == 0);
    set<T2>(3);
    assert(get<T2>() == 3);
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接