有哪些类型的擦除技术，它们是如何工作的？

Question

^{（通过类型擦除，我指的是隐藏与类相关的一些或全部类型信息，有点像Boost.Any。）}
我想了解类型擦除技术，同时也想分享我所了解的技术。我希望能找到一些疯狂的技巧，这些技巧可能是某个人在最困难的时刻想出来的。:)

我所知道的第一种最明显、最常用的方法是使用虚函数。只需将类的实现隐藏在基于接口的类层次结构中。许多Boost库都使用这种方法，例如Boost.Any用于隐藏类型，Boost.Shared_ptr用于隐藏（释放）分配机制。

然后还有使用函数指针指向模板函数的选项，同时将实际对象保存在一个void*指针中，就像Boost.Function所做的那样，隐藏了函数对象的真实类型。示例实现可以在问题的末尾找到。

所以，针对我的实际问题：
你还知道其他的类型擦除技术吗？如果可能的话，请提供它们的示例代码、使用案例、你对它们的经验，以及进一步阅读的链接。

编辑 （由于我不确定是将此作为答案添加，还是只编辑问题，所以我选择更安全的方式。） 另一种很好的技巧是在不使用虚函数或void*操作的情况下隐藏某物的实际类型，这是GMan在这里使用的方法here，与my question有关，关于这个方法的工作原理。

---

示例代码：

#include <iostream>
#include <string>

// NOTE: The class name indicates the underlying type erasure technique

// this behaves like the Boost.Any type w.r.t. implementation details
class Any_Virtual{
        struct holder_base{
                virtual ~holder_base(){}
                virtual holder_base* clone() const = 0;
        };

        template<class T>
        struct holder : holder_base{
                holder()
                        : held_()
                {}

                holder(T const& t)
                        : held_(t)
                {}

                virtual ~holder(){
                }

                virtual holder_base* clone() const {
                        return new holder<T>(*this);
                }

                T held_;
        };

public:
        Any_Virtual()
                : storage_(0)
        {}

        Any_Virtual(Any_Virtual const& other)
                : storage_(other.storage_->clone())
        {}

        template<class T>
        Any_Virtual(T const& t)
                : storage_(new holder<T>(t))
        {}

        ~Any_Virtual(){
                Clear();
        }

        Any_Virtual& operator=(Any_Virtual const& other){
                Clear();
                storage_ = other.storage_->clone();
                return *this;
        }

        template<class T>
        Any_Virtual& operator=(T const& t){
                Clear();
                storage_ = new holder<T>(t);
                return *this;
        }

        void Clear(){
                if(storage_)
                        delete storage_;
        }

        template<class T>
        T& As(){
                return static_cast<holder<T>*>(storage_)->held_;
        }

private:
        holder_base* storage_;
};

// the following demonstrates the use of void pointers 
// and function pointers to templated operate functions
// to safely hide the type

enum Operation{
        CopyTag,
        DeleteTag
};

template<class T>
void Operate(void*const& in, void*& out, Operation op){
        switch(op){
        case CopyTag:
                out = new T(*static_cast<T*>(in));
                return;
        case DeleteTag:
                delete static_cast<T*>(out);
        }
}

class Any_VoidPtr{
public:
        Any_VoidPtr()
                : object_(0)
                , operate_(0)
        {}

        Any_VoidPtr(Any_VoidPtr const& other)
                : object_(0)
                , operate_(other.operate_)
        {
                if(other.object_)
                        operate_(other.object_, object_, CopyTag);
        }

        template<class T>
        Any_VoidPtr(T const& t)
                : object_(new T(t))
                , operate_(&Operate<T>)
        {}

        ~Any_VoidPtr(){
                Clear();
        }

        Any_VoidPtr& operator=(Any_VoidPtr const& other){
                Clear();
                operate_ = other.operate_;
                operate_(other.object_, object_, CopyTag);
                return *this;
        }

        template<class T>
        Any_VoidPtr& operator=(T const& t){
                Clear();
                object_ = new T(t);
                operate_ = &Operate<T>;
                return *this;
        }

        void Clear(){
                if(object_)
                        operate_(0,object_,DeleteTag);
                object_ = 0;
        }

        template<class T>
        T& As(){
                return *static_cast<T*>(object_);
        }

private:
        typedef void (*OperateFunc)(void*const&,void*&,Operation);

        void* object_;
        OperateFunc operate_;
};

int main(){
        Any_Virtual a = 6;
        std::cout << a.As<int>() << std::endl;

        a = std::string("oh hi!");
        std::cout << a.As<std::string>() << std::endl;

        Any_Virtual av2 = a;

        Any_VoidPtr a2 = 42;
        std::cout << a2.As<int>() << std::endl;

        Any_VoidPtr a3 = a.As<std::string>();
        a2 = a3;
        a2.As<std::string>() += " - again!";
        std::cout << "a2: " << a2.As<std::string>() << std::endl;
        std::cout << "a3: " << a3.As<std::string>() << std::endl;

        a3 = a;
        a3.As<Any_Virtual>().As<std::string>() += " - and yet again!!";
        std::cout << "a: " << a.As<std::string>() << std::endl;
        std::cout << "a3->a: " << a3.As<Any_Virtual>().As<std::string>() << std::endl;

        std::cin.get();
}

- Xeo

---

“类型擦除”这个术语，你是不是真的指的是“多态性”？我认为，“类型擦除”有一个比较具体的含义，通常与Java泛型等相关。 - Oliver Charlesworth

@Oli：类型擦除可以用多态实现，但这不是唯一的选择，我的第二个示例展示了这一点。而且，通过类型擦除，我指的是你的结构体不依赖于模板类型。Boost.Function 不在乎你传递给它一个函数对象、函数指针还是 lambda 表达式。Boost.Shared_Ptr 同样如此。你可以指定分配器和释放函数，但 shared_ptr 的实际类型不会反映这一点，它总是相同的，例如 shared_ptr<int>，不像标准容器。 - Xeo

@Matthieu：我认为第二个例子也是类型安全的。你总是知道你正在操作的确切类型。或者我有什么遗漏吗？ - Xeo

@Matthieu：你说得对。通常这样的As(s)函数不会以这种方式实现。就像我说的，绝不是安全使用的！ :) - Xeo

你是否从未使用过以下任何一个的boost或std版本：function，shared_ptr，any等？它们都采用类型抹除技术来为用户提供更加便利的使用体验。 - Xeo

Answer 1

C++中的所有类型擦除技术都是使用函数指针（用于行为）和void*（用于数据）实现的。 "不同"的方法只是在它们添加语义糖的方式上有所不同。例如，虚函数只是语义糖。

struct Class {
    struct vtable {
        void (*dtor)(Class*);
        void (*func)(Class*,double);
    } * vtbl
};

iow: 函数指针。

话虽如此，我特别喜欢一种技巧：使用 shared_ptr<void>，因为它让不知道可以这样做的人眼前一亮：你可以在一个 shared_ptr<void> 中存储任何数据，并且仍然可以在结尾处正确调用析构函数，因为 shared_ptr 的构造函数是一个函数模板，通常会使用传递的实际对象类型来创建删除器：

{
    const shared_ptr<void> sp( new A );
} // calls A::~A() here

当然，这只是通常的void*/函数指针类型擦除，但非常方便地打包在一起。

- Marc Mutz - mmutz

---

巧合的是，就在几天前我不得不向我的一个朋友解释shared_ptr<void>的行为，并给出了一个实现的例子。 :) 真的很酷。 - Xeo

好的回答；为了使它更加出色，一个关于如何为每个擦除类型静态创建伪vtable的草图非常有教育意义。请注意，伪vtable和函数指针实现可以为您提供已知内存大小的结构（与纯虚拟类型相比），这些结构可以轻松地本地存储，并且（容易）与它们正在虚拟化的数据分离。 - Yakk - Adam Nevraumont

所以，如果 shared_ptr 存储的是 Derived *，但 Base * 没有将析构函数声明为虚拟的，shared_ptr<void> 仍然按预期工作，因为它根本不知道有一个基类存在。很酷！ - TamaMcGlinn

@Apollys：是这样的，但 unique_ptr 不会对 deleter 进行 type-erase，所以如果您想将 unique_ptr<T> 分配给 unique_ptr<void>，则需要显式提供一个 deleter 参数，该 deleter 知道如何通过 void* 删除 T。 如果现在您也想分配一个 S，那么您需要一个 deleter，它知道如何通过 void* 删除 T 并通过 void* 删除 S，并且，在给定 void* 的情况下，知道 它是一个 T 还是一个 S。此时，您为 unique_ptr 编写了一个类型抹除的 deleter，然后它也适用于 unique_ptr。只是需要一些额外操作。 - Marc Mutz - mmutz

我觉得你回答的问题是“我该如何解决这个不适用于unique_ptr的问题？”对一些人有用，但并没有回答我的问题。我猜答案是因为shared pointers在标准库的开发中得到了更多的关注。我觉得这有点可悲，因为unique pointers更简单，所以应该更容易实现基本功能，并且它们更有效率，所以人们应该更多地使用它们。相反，我们却恰恰相反。 - Apollys supports Monica

Answer 2

从根本上说，你的选择是：虚函数或函数指针。

如何存储数据并将其与函数关联起来可以有所不同。例如，您可以存储一个指向基类的指针，并使派生类包含数据和虚函数实现，或者您可以将数据存储在其他地方（例如单独分配的缓冲区）并只让派生类提供虚函数实现，这些实现需要一个指向数据的void*指针。如果将数据存储在单独的缓冲区中，则可以使用函数指针而不是虚函数。

如果有多个操作要应用于您的类型擦除数据，存储指向基类的指针在这种情况下效果很好，即使数据是单独存储的。否则，您最终会得到多个函数指针（每个类型擦除函数一个），或者带有指定要执行的操作的参数的函数。

- Anthony Williams

---

换句话说，我在问题中提到的例子是这样的吗？不过，特别是关于虚函数和对类型擦除数据进行多个操作方面，感谢您将其写出来。 - Xeo

至少还有其他两个选项。我正在撰写答案。 - John Dibling

Answer 3

我也会考虑（类似于void*）使用“原始存储”：char buffer[N]。

在C++0x中，您可以使用std::aligned_storage<Size,Align> ::type来实现这一点。

只要对象足够小并且您正确处理了对齐，就可以将任何内容存储在其中。

- Matthieu M.

---

Boost.Function实际上使用了我之前提到的两个例子的组合。如果函数对象足够小，它会将其存储在functor_buffer内部。不过了解std::aligned_storage也是很好的，谢谢！ :) - Xeo

你也可以使用放置new来实现这个。 - rustyx

@RustyX：实际上，你必须这么做。 std::aligned_storage<...>::type只是一个原始缓冲区，它与char [sizeof(T)]不同，适当地对齐。然而，仅凭它本身，它是惰性的：它不初始化其内存，不构建对象，什么都不做。因此，一旦您拥有了这种类型的缓冲区，您必须手动在其中构造对象（使用放置new或分配器construct方法）并且您还必须手动销毁其中的对象（手动调用其析构函数或使用分配器的destroy方法）。 - Matthieu M.

Answer 4

在《C++程序设计语言（第四版）§25.3》中，Stroustrup提到：

使用单一的运行时表示来处理多种类型值，并依靠（静态）类型系统确保仅按其声明类型使用，这种技术的变体被称为类型擦除。

特别地，如果使用模板，执行类型擦除无需使用虚函数或函数指针。其中一个例子是，根据存储在std::shared_ptr<void>中的类型进行正确的析构函数调用。

Stroustrup书中提供了一个有趣的示例。

考虑实现template<class T> class Vector，一个类似于std::vector的容器。当您将其与许多不同的指针类型一起使用时，编译器会为每个指针类型生成不同的代码。

可以通过为void*指针定义Vector的特化版本，然后将此特化版用作所有其他类型T的Vector<T*>的共同基础实现，从而避免代码膨胀。

template<typename T>
class Vector<T*> : private Vector<void*>{
// all the dirty work is done once in the base class only 
public:
    // ...
    // static type system ensures that a reference of right type is returned
    T*& operator[](size_t i) { return reinterpret_cast<T*&>(Vector<void*>::operator[](i)); }
};

正如您所看到的，我们拥有一个强类型容器，但是 Vector<Animal*>, Vector<Dog*>, Vector<Cat*>, ...，将共享相同（C++ 和 二进制）的实现代码，它们的指针类型在 void* 后被 擦除。

- Paolo M

---

毫不亵渎的说：我更喜欢CRTP而不是Stroustrup提出的技术。 - davidhigh

可以通过使用一个CRTP基类template<typename Derived> VectorBase<Derived>并将其专门化为template<typename T> VectorBase<Vector<T*> >来获得相同的行为（具有不那么笨拙的语法）。此外，这种方法不仅适用于指针，而且适用于任何类型。 - davidhigh

请注意，良好的 C++ 链接器会合并相同的方法和函数：如 gold 链接器或 MSVC comdat 折叠。代码被生成后在链接过程中被丢弃。 - Yakk - Adam Nevraumont

@davidhigh，我正在努力理解您的评论，并想知道您是否可以给我一个链接或搜索模式的名称（不是CRTP，而是一种允许类型擦除而不使用虚函数或函数指针的技术名称）。敬礼，- Chris - Chris Chiasson

@Yakk: 他们是不被允许这样做的。在C++中，不同的函数必须有不同的地址，所以他们合法允许的唯一事情就是共享大部分的代码，并为每个原始函数创建一个小的跳板函数/头文件来保持它们在不同的地址上。但是，有些编译器/链接器确实会这样做。这会破坏用户的代码，例如Qt 5的新式connect。 - Marc Mutz - mmutz

Answer 5

请参阅此系列文章，其中列出了一些类型抹消技术，并讨论了其权衡之处：第I部分，第II部分，第III部分，第IV部分。我还没有看到提到的是Adobe.Poly和Boost.Variant，在一定程度上可以视为类型抹消。

- Andrzej

Answer 6

正如Marc所说，可以使用类型转换std::shared_ptr<void>。例如，在函数指针中存储类型，进行转换并存储在只有一个类型的函数对象中：

#include <iostream>
#include <memory>
#include <functional>

using voidFun = void(*)(std::shared_ptr<void>);

template<typename T>
void fun(std::shared_ptr<T> t)
{
    std::cout << *t << std::endl;
}

int main()
{
    std::function<void(std::shared_ptr<void>)> call;

    call = reinterpret_cast<voidFun>(fun<std::string>);
    call(std::make_shared<std::string>("Hi there!"));

    call = reinterpret_cast<voidFun>(fun<int>);
    call(std::make_shared<int>(33));

    call = reinterpret_cast<voidFun>(fun<char>);
    call(std::make_shared<int>(33));


    // Output:,
    // Hi there!
    // 33
    // !
}

- Janek Olszak