问题 模板化的递归数据类型


我有一个这样的递归数据类型:

template<typename T>
struct SomeType {
    std::map<T, SomeType<T>> mapping;
};

SomeType<int> foo;

这工作正常,但更换 std::map 同 std::unordered_map 由于类型不完整导致编译错误。我(或gcc)在某个地方犯了错误吗?或者这只是标准的一部分?

我还希望通过模板参数确定内部容器(比如 std::stack 和 std::queue),但我无法找到一种方法,因为这将需要已定义SomeType。

不完整的例子:

template<typename T, typename C = std::map<T, SomeType<[???]>>>
struct SomeType {
    C mapping;
};

SomeType<int, [???]> foo;

我知道这可以通过运行时间接完成,但这不是我正在寻找的。


2516
2018-03-25 13:30


起源

标准库容器模板要求您使用完整类型实例化它们;所有其他都是未定义的行为。你必须忍受这一点。但是,您可以使用pimpl解决方案来解决这个问题。 - Kerrek SB
@KerrekSB是这样的吗?该死的,我经常写n-ary树,其节点是按照实现的 std::vector<node> children。 - Konrad Rudolph
@KonradRudolph:嗯,你必须确保在实例化时类型完成。这可能是一个微妙的问题。 - Kerrek SB
好笑,它 是 所以。它恰好发生在典型的情况下 vector 实现适用于不完整类型而无需修改 - 你一直很幸运。 - Irfy


答案:


在决赛前的任何地方你的课程都是不完整 } 它的定义。所以 mapping 成员使用的是不完整类型 SomeType 在其类型的模板参数中。

该标准不允许这样做,并且它与一些STL容器一起运行是纯粹的运气。

你的第二个问题属于同一个答案 - 首先这样做是违法的。


7
2018-03-25 13:44



嗯。不幸的是,我不明白这篇文章关于原因的论点 std::map<K, V> 不完整类型原则上不能工作。这不是很像 std::vector<std::pair<K const, V>>, 哪一个 能够 原则上工作(std::pair<K const, V> 不完整)?其他容器也是如此。 - Konrad Rudolph
如果这需要解释,我建议打开一个聊天室,这并不难,只是不适合评论部分...现在,我如何明确地打开聊天室这个... - Irfy
我们在这里聊聊: chat.stackoverflow.com/rooms/9282/stl-with-incomplete-types - Irfy


出于显而易见的原因,您无法使用递归默认参数定义模板。您也无法在不完整类型上实例化标准库容器模板,因为标准会这样说(否则它是未定义的行为)。但是,通常的PIMPL习惯可能会有所帮助:

#include <map>
#include <memory>
template <typename T> class SomeType
{
    typedef std::map<T, SomeType<T>> map_type;
    typedef std::unique_ptr<map_type> map_ptr;
    map_ptr pimpl;
public:
    SomeType() : pimpl(new map_type) { }
};

4
2018-03-25 13:52



boost :: container库为大多数允许不完整类型的递归容器的STL类型提供了替代方法。它目前不提供unordered_map - mark
@mark:谢谢,很高兴知道! - Kerrek SB


虽然您不能将不完整的类型与容器一起使用,但您可以使用智能指针来完成。 虽然您无法使用未定义的类型参数创建模板类型,但您可以在此处使用一些技巧:

template<typename T, template <typename U, typename V, typename... Args> class Container = std::unordered_map >
struct SomeType {
    Container<T, std::unique_ptr<SomeType> > mapping;
};

3
2018-03-25 14:24



是否可以更改第一行,使Container的默认值为std :: vector? - Niels Lohmann
@NielsLohmann,技术上你可以写 template<typename T, template <typename U, typename... Args> class Container = std::vector >,但它会与之不一致 std::unordered_map 比。因为地图是 assosiative conrtainer和vector只是一个数组。 - Lol4t0