2

执行以下操作的最佳方法是什么？我正在尝试找到 2 组的并集。我正在创建 2 个对象（一个称为 set1，一个称为 set2）。我的目标是创建第三个对象，它是两者的 UNION，而不必使用复制构造函数。必须使用动态内存分配和指针和/或引用。感谢任何人解决这个困境，任何指针（没有双关语）都会有所帮助。

感谢码农。

头文件

                #ifndef INTEGERSET_H_
                #define INTEGERSET_H_

                class IntegerSet
                {
                private:
                    int * set;
                    int set_size;
                public:
                    IntegerSet(int size);    //default constructor
                    ~IntegerSet();           //destructor
                    IntegerSet * unionOfSets(const IntegerSet & set2);      
                    void insertElement(int k) const;
                    void printSet(int size) const;
                };
                #endif

主要文件

            #include <iostream>
            #include "integerset.h"

            using std::cout;
            using std::endl;

            int main()
            {
                IntegerSet set1(11);

                //testing below
                set1.insertElement(3);
                set1.insertElement(4);
                set1.insertElement(6);
                set1.insertElement(10);

                set1.printSet(11);
                cout << endl;

                IntegerSet set2(8);
                set2.insertElement(3);
                set2.insertElement(6);
                set2.insertElement(7);

                set2.printSet(11);
                cout << endl;



                IntegerSet * obj3 = new IntegerSet(11);
                obj3 =  set1.unionOfSets(set2);                    
                obj3->printSet(11);

            //  system("pause");
                return 0;
            }

实施文件

            #include "integerset.h"
            #include <iostream>

            IntegerSet::IntegerSet(int size)
            {
                set = new int[size];
                set_size = size;                    
                for (int i = 0; i < size; i++)
                    set[i] = 0;
            }

            IntegerSet::~IntegerSet()
            {
                delete [] set;
            }

            void IntegerSet::insertElement(int k) const
            {
                (*this).set[k] = 1;
            }

            void IntegerSet::printSet(int size) const
            {
                int temp = 0;
                for (int i = 0; i < size; i++)
                {
                    if (set[i] == 1)
                    {
                        std::cout << i << " ";
                        temp++;
                    }
                }
                if (temp == 0)
                    std::cout << "----";
             }


            IntegerSet * IntegerSet::unionOfSets(const IntegerSet & set2) //make this return the union of 2 sets; THIS and the passed ARG reference; return address
            {


                   return this;
            }
4

2 回答 2

4

随机的早晨咆哮

您尝试创建的std::bitset不仅仅是 a std::set。集合通常是“定义明确的不同对象的集合”（康托尔的定义有点复杂，但让我们坚持这一点）。因此，一个集合可以包含几个成对的不相关对象。

现在，说了这么多，看看std::bitset。请注意，它的大小由模板参数固定N。std::bitset::set几乎等同于你的IntegerSet::insertElement，除了它抛出std::out_of_range. 我建议您检查索引是否有有效位置：

void IntegerSet::insertElement(int k) const
{
    if( k < 0 || k >= set_size)
        throw std::out_of_range; 
    else
        this->set[k] = 1;
}

但是，std::bitset不支持工会，所以是时候解决你的问题了。

IntegerSet::unionofSets

看看那些线。

IntegerSet * obj3 = new IntegerSet(11);
obj3 =  set1.unionOfSets(set2);

第一行obj3用一个指针初始化，该指针包含一个新创建的 IntegerSet 的内存，其内部集大小为 11。在下一行，你扔掉那个指针。因此，您正在丢弃资源并造成内存泄漏。

如果您要创建一个新的IntegerSet，您的解决方案将非常简单：

IntegerSet IntegerSet::unionOfSets(const IntegerSet & set2) const
{
    IntegerSet tmp (std::max(set2.set_size, this->set_size));

    for(int i = 0; i < set_size; ++i)
        tmp.set[i] = this->set[i];

    for(int i = 0; i < set2.set_size; ++i)
        tmp.set[i] |= set2.set[i];

    return tmp;
}

但是你的实现改变了它被调用的对象，所以它并没有const什么不同：

IntegerSet * IntegerSet::unionOfSets(const IntegerSet & set2) // not const!
{
    if(set2.set_size > set_size){
        // the resulting set is bigger, we need new memory
        int * newset = new int[set2.set_size];

        // copy old values
        for(int i = 0; i < this->set_size; ++i)
            newset[i] = this->set[i];

        // replace old size
        this->set_size = set2.set_size;
        delete[] this->set; // remove old data
        this->set = newset; // replace pointer
    }

    for(int i = 0; i < set2.set_size; ++i)
        this->set[i] |= set2.set[i];

    return this;
}

这应该足够了。请记住，您不得使用new IntegerSet以下命令创建联合：

IntegerSet * obj3 = new IntegerSet(11); // new memory, lets say obj3 = 0x500a
obj3 = set1.unionOfSets(set2); // new memory gone forever

if(obj3 == &set1)
    std::cout << "obj3 is a pointer to set1, changes to obj3 will affect set1" << std::endl;

如果您不想创建此行为，请使用临时版本的第一个版本。

另外，请检查是否std::set<int>足够，因为您可以使用std::set_unionfrom <algorithm>。

编辑

  1. 提供一个 unionOfSets 成员函数，该函数创建第三个 IntegerSet，它是两个现有 IntegerSet 实例的并集（因此，此函数创建的第三个集合包含用于创建它的两个集合中的所有成员——因此，如果其中一个或两个集合union 执行时有一个元素，第三组将有该元素）

在这种情况下，忘记IntegerSet * IntegerSet::unionOfSets(const IntegerSet&)并使用IntegerSet IntegerSet::unionOfSets(const IntegerSet&) const（第一个变体带有返回的对象而不是返回的指针）。

编辑2

由于您没有遵循三规则，因此返回的内存IntegerSet将无效。您要么必须实现复制构造函数/赋值运算符才能解决此问题，要么提供具有动态存储持续时间的新对象 ( new)。为此，您只需稍微调整方法：

IntegerSet * IntegerSet::unionOfSets(const IntegerSet & set2) const
{
    IntegerSet * tmp  = new IntegerSet( set2.set_size > this->set_size ? set2.set_size : this->set_size);

    for(int i = 0; i < set_size; ++i)
        tmp->set[i] = this->set[i];

    for(int i = 0; i < set2.set_size; ++i)
        tmp->set[i] |= set2.set[i];

    return tmp;
}
于 2012-10-05T05:25:33.113 回答
1

使用标准设施...

  • std::vector比手卷阵列好
  • std::sortstd::unique是善良

所以：

std::vector<int> set1;
set1.push_back(1); // ... and others

std::sort(set1.begin(), set1.end());   // sorts
std::unique(set1.begin(), set1.end()); // removes duplicates


// same with set2


std::vector<int> set3(set1);
set3.insert(set3.end(), set2.begin(), set2.end());

std::sort(set1.begin(), set1.end());   // sorts
std::unique(set1.begin(), set1.end()); // removes duplicates
于 2012-10-05T07:44:26.877 回答