CODEWITHSUNDEEP
c++
Snerd
Snerd

Reputation: 1553

union of 2 sets; return simple object - C++

What is the best way to implement the following? I am trying to find the union of 2 sets. I am creating 2 objects (one called set1 and one called set2). I aim to create a 3rd object that is a UNION of the two without having to use a copy constructor. Using dynmanic memory allocation and pointers and/or references is a must. Thanks to anyone to solves this dilemma and any pointers (no pun intended) would help.

Thanks coders.

THE HEADER file

                #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

THE MAIN file

            #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;
            }

THE IMPLEMENTATION FILE

            #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;
            }

Upvotes: 2

Views: 2653

Answers (2)

Matthieu M.
Matthieu M.

Reputation: 299810

Using standard facilities...

  • std::vector is better than a hand-rolled array
  • std::sort and std::unique are goodness

Therefore:

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

Upvotes: 1

Zeta
Zeta

Reputation: 105886

Random morning rant

What you try to create is more a std::bitset than a std::set. A set is usually "a collection of well defined distinct objects" (Cantor's definition is a little bit more complex, but lets stick to this). As such, a set could contain several pairwise unrelated objects.

Now, after this has been said, have a look at std::bitset. Note that its size is fixed by the template parameter N. std::bitset::set is almost equivalent to your IntegerSet::insertElement, except that it throws std::out_of_range. This I recommend you to check your index for valid position:

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

However, std::bitset doesn't support unions, so it's time to address your meain conern.

IntegerSet::unionofSets

Have a look at those lines.

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

The first line initializes obj3 with a pointer which contains the memory for a newly created IntegerSet with an internal set of size 11. And in the next line, your throw that pointer away. So you're throwing away resources and create a memory leak.

If you were to create a new IntegerSet your solution would be quite simple:

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;
}

But your implementation changes the object it has been called from, so it isn't const and a little bit different:

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;
}

This should be sufficient. Keep in mind that you must not use new IntegerSet in order to create a union:

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;

If you don't want to create this behaviour use the first version with the temporary.

Also, please check whether std::set<int> is sufficient for you, as you can use std::set_union from <algorithm>.

EDIT

  1. Provide a unionOfSets member function that creates a third IntegerSet that is the union of two existing IntegerSet instances (so the third set created by this function contains all the members in the two sets used to create it – so if one or both of the sets the union is performed on has an element in it, the third set will have that element)

In this case forget about IntegerSet * IntegerSet::unionOfSets(const IntegerSet&) and use IntegerSet IntegerSet::unionOfSets(const IntegerSet&) const (the first variant with a returned object instead of a returned pointer).

EDIT2

As you didn't follow the rule of three, the memory in the returned IntegerSet will be invalid. You would either have to implement a copy constructor/assignment operator in order to fix this, or provide a new object with dynamic storage duration (new). For this you would just have to adjust the method a little bit:

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;
}

Upvotes: 4

Related Questions