关于如何在 std::set 中插入自定义对象的介绍

• 下载源代码 - 1.27 KB

引言

本文介绍如何将许多自定义对象（当然，这些对象可以通过某种方式进行比较）插入到关联容器中，特别是 set 和 multiset。

背景

熟悉 STL 的人知道 set 和 multiset 的代码定义如下所示

namespace std{
    template <class T,
    class Compare = less<T>,
    class Allocator = allocator<T> > class set;
    template <class T,
    class Compare = less<T>,
    class Allocator = allocator<T> > class multiset;
}

set 和 multiset 的区别在于，multiset 允许重复元素，而 set 不允许。更重要的是，set 和 multiset 都保持元素存储的顺序。简而言之，set 和 multiset 都使用红黑树（一种高级的平衡二叉树）来存储元素，因此您需要一个元素插入的顺序。

set 或 multiset 的元素可以是任何可赋值、可复制且根据某种排序标准可比较的类型 T。可选的第二个参数代表此基于比较的操作。如果在声明 set 和/或 multiset 时没有传递特殊的排序标准，则容器将使用默认的 std::less<>。

那么，如果您需要插入一堆自定义对象（您自己类的对象），如何设计您的类以便它们可以包含在 set/multiset 中呢？

正如我前面所说：“set/multiset 的元素可以是任何类型 T，即

• 可赋值的（也就是说，您必须有一个重载的赋值运算符，或者默认的赋值运算符——如果它足以完成这项工作）
• 可复制的（也就是说，您必须有一个复制构造函数，或者默认的复制构造函数——如果它足以完成这项工作）
• 可比较的：这是最重要的一部分。您必须加入某种决策分支，该分支将根据某些比较标准比较两个自定义对象。这里您有两种选择

1. 您可以在类本身中重载“<”运算符。
2. 您可以创建一个仿函数来完成比较工作。

另一件重要的事情是，排序标准必须定义“弱排序”。严格弱排序由以下三个属性定义

1. 它必须是反对称的，即如果 x<y 为真，则 y<x 为假。
2. 它必须是传递的：即，如果 x<y 为真且 y<z 为真，则 x<z 也为真。
3. 它必须是反自反的：即 x<x 总是假。

Using the Code

如果您解压源代码，您会发现三个名为以下的文件

1. MyType.hpp - 此类定义了自定义类型以及重载的 < 运算符。
2. MyComparator.hpp - 此类定义了一个自定义仿函数，用于执行比较工作。
3. newmain.cpp - 主文件。

首先让我们分析 MyType.hpp 文件

/* 
 * File:   MyType.hpp
 * Author: Tushar
 *
 * Created on May 6, 2009, 5:10 PM
 */

#ifndef _MYTYPE_HPP
#define	_MYTYPE_HPP

namespace Tushar{
template <typename T>
class MyType{
private:
    T value;
public:
    MyType(){
        value = T();
    }
    MyType(T val):value(val){
    }
    MyType(const MyType& other){
        value = other.value;
    }
    MyType& operator=(MyType const& other){
        if((void*)this == (void*)&other)
            return *this;
        value = other.getValue();
        return *this;
    }

    bool operator< (const MyType& other) const{
        return value<other.getValue();
    }
    T getValue() const{
        return value;
    }
};
}

#endif	/* _MYTYPE_HPP */

这里，一切都非常简单。只需浏览一下。

现在，让我们看看 MyComparator.hpp。

/* 
 * File:   MyComparator.hpp
 * Author: Tushar
 *
 * Created on May 6, 2009, 5:11 PM
 */

#ifndef _MYCOMPARATOR_HPP
#define    _MYCOMPARATOR_HPP
#include "MyType.hpp"
template <typename T>
class MyComparator{
public:
    bool operator() (const T& t1, const T& t2) const{
        return t1.getValue()<t2.getValue();
    }
};
#endif    /* _MYCOMPARATOR_HPP */

这里的想法是重载 () 运算符（这是一个真正的仿函数），它接受两个模板参数（我们将实际传递两个自定义对象），它使用 < 运算符比较这两个对象。

现在让我们看看驱动程序文件

#include <iostream>
#include <set>
#include "myType.hpp"
#include "MyComparator.hpp"

int main()
{  
    Tushar::MyType<int> m1(100);
    Tushar::MyType<int> m2(200);       
    typedef std::set<Tushar::MyType<int>, MyComparator<Tushar::MyType<int> > > CustomSet;
    CustomSet mySet;
    mySet.insert(m1);
    mySet.insert(m2);
    CustomSet::const_iterator it(mySet.begin());
    for(;it!=mySet.end();++it){
        std::cout<<"Element is: "<<it->getValue()<<std::endl;
    }
    return 0;
}

这里的自定义 typedef 行是最重要的行，请仔细查看声明，我们在这里声明一个 std::set，它将保存我们的自定义类型，并将根据我们拥有的仿函数进行比较。同样，std::set 声明中的 MyComparator 声明也需要保存我们自定义类的类型定义，因为我们的仿函数也是模板化的。

当然，您也可以直接使用……

typedef std::set<Tushar::MyType<int> > CustomSet;

……程序将正常工作。

但是，建议使用仿函数。

历史

• 2009 年 5 月 6 日：初始发布