C++ 的复杂模板参数类型STL集

Question

我正在实现一个具有复杂模板参数类型的 STL 集。插入到集合中时，我希望集合使用我为我的类型定义的小于运算符。我还希望最大限度地减少我的类型的对象实例化的数量。看来我不能两者兼得。

下面有两个最小的示例，每个示例都使用相同的 C++ 类。

#include <iostream>
#include <set>

using namespace std;

class Foo {
    public:
        Foo(int z);
        Foo(const Foo &z);
        bool operator<(const Foo &rhs) const;
        int a;
};

Foo::Foo(int z)
{
    cout << "cons" << endl;
    a = z;
}

Foo::Foo(const Foo &z)
{
    cout << "copy cons" << endl;
    a = z.a;
}

bool
Foo::operator<(const Foo &rhs) const
{
    cout << "less than" << endl;
    return a < rhs.a;
}

这是我的第一个 main()：

int
main(void)
{
    set<Foo> s;

    s.insert(*new Foo(1));
    s.insert(*new Foo(2));
    s.insert(*new Foo(1));

    cout << "size: " << s.size() << endl;

    return 0;
}

这很好，因为它使用了我为类定义的小于号，因此集合的大小正确为 2。但这很糟糕，因为每次插入集合都需要实例化两个对象（构造函数、复制构造函数）。

$ ./a.out
cons
copy cons
cons
less than
less than
less than
copy cons
cons
less than
less than
less than
size: 2

这是我的第二个 main()：

int
main(void)
{
    set<Foo *> s;

    s.insert(new Foo(1));
    s.insert(new Foo(2));
    s.insert(new Foo(1));

    cout << "size: " << s.size() << endl;

    return 0;
}

这很好，因为插入只需要一个对象实例化。但这很糟糕，因为它实际上是一组指针，因此就我的类型而言，集合成员的唯一性消失了。

$ ./a.out
cons
cons
cons
size: 3

我希望我遗漏了一些信息。我是否可以同时拥有最少的对象实例化和适当的排序？

Answer 1

您将从以下位置获取副本：*new Foo(1)。

创建此结构：

template<typename T>
struct PtrLess
{
    bool operator()(const T *a, const T *b) const
    {
        return *a < *b;
    }
};

使地图看起来像 set>; s; 然后添加 Foo，如 s.insert(new Foo(1));
注意 *

否则，当映射为 Foo 项创建容器时，由于它是在 foo 容器定义内分配的，因此映射必须将提供的值复制到其内部 Foo 对象中。

Answer 2

标准容器存储添加的项目的副本。如果您希望 set 存储对象，而不是指针，您应该简单地执行以下操作，否则就会造成内存泄漏，因为通过 new 分配的对象永远不会通过相应的删除释放。

int main()
{
    set<Foo> s;

    s.insert(Foo(1));
    s.insert(Foo(2));
    s.insert(Foo(1));

    cout << "size: " << s.size() << endl;

    return 0;
}

如果您想最大限度地减少实例化的临时对象的数量，只需使用单个临时对象：

int main()
{
    set<Foo> s;

    Foo temp(1);
    s.insert(temp);
    temp.a = 2;
    s.insert(temp);
    temp.a = 1;
    s.insert(temp);

    cout << "size: " << s.size() << endl;

    return 0;
}

此代码段的输出（通过 ideone）是：

cons
copy cons 
less than
less than
less than
copy cons
less than
less than
less than
size: 2

一般来说，我更愿意将实际对象存储在 set 而不是指向 set 中对象的指针，因为对象所有权不会有问题（谁/何时new 和删除需要调用），分配的内存总量较小（对于 N 项，您需要 N*sizeof(Foo) 而不是 N*(sizeof( Foo) + sizeof(Foo*)) 字节）和数据访问通常预计会更快（因为没有额外的指针间接寻址）。

希望这有帮助。

Answer 3

这是 @Mranz 的答案的扩展。不处理原始指针，而是将指针放入 std::unique_ptr

#include <memory>

using namespace std;

template<typename T>
struct PtrLess
{
    bool operator()(const T& a, const T& b) const
    {
        return *a < *b;
    }
};


int
main(void)
{
    set<unique_ptr<Foo>, PtrLess<unique_ptr<Foo>>> s;

    s.insert(unique_ptr<Foo>(new Foo(1)));
    s.insert(unique_ptr<Foo>(new Foo(2)));
    s.insert(unique_ptr<Foo>(new Foo(1)));

    cout << "size: " << s.size() << endl;

    return 0;
}