-
creating new sets
well, for now I decided to stick to my strtok() parser from the previous post. But now another question arises. I need to keep a running number of sets, and at the same time manipulate them...the max number of sets is 20, but with N number of members.
I made a class called Sets which will do all these manipulations for me as well as create and delete sets. I'm not sure what approach I should take in creating the new sets, should I use an array of pointers? but how can I dynamically allocate the space for the sets. Lets say that
Code:
array element | points to the set
------------------------------------------
0 {1 2 6 8}
1 {1 23}
2 { 1 through 100 }
3-19 empty
If I make a two dimensional array I have to declare it in the beginning but cant because the number of members is unkown.
Which ADT should I go with to keep this relatively simple?
here is the beginning of the sets class
Code:
//FILE: sets.h
class Sets
{
private:
int value1;
int value2;
public:
//declaring constructor
Sets();
//declaring set functions
void set( int );
void set( int, int );
//declaring get functions
int getVal1() { return value1; }
int getVal2() { return value2; }
};
//=========================
Sets::Sets()
{
}
//=========================
void Sets::set( int val1 )
{
value1 = val1;
}
//=========================
void Sets::set( int val1, int val2 )
{
value1 = val1;
value2 = val2;
}
thanks
-
The STL has classes for both vectors and sets. Sounds like you could use a vector full of sets.
-
easier said then done, huh joshdick? unfortunately I can only use vectors from the stl.
-
Sets are as easy to use as vectors ^^. Create a set and choose what datatype and sorting criterion to use
Code:
std::set<datatype, std::sortingcriteria<datatype> > identifier;
E.i a set with float that sort ascending
Code:
std::set<float, std::greater<float> > floatSet;
And to insert a float in the set
Code:
//Note that postfix f has to be inserted or else data might be lost due to conversion
floatSet.insert(3.1415f);
Also this might be helpful
-
Thanks ripper, unfortunately the assignemnet specifically asks not to use the set method from the stl. We have to come uo with some sort of ADT that does verious set manipulations with various running time constraints.
-
I'm not very familiar with sets, but if you don't want to use some sort of linked list method, you could have a pointer to a struct in your class:
Code:
typdef struct _SDATA
{
int* member;
} sData;
class Set
{
....
private:
sData* data;
};
Then allocate space for data and member...
-
I would make one class for a single set and then have your other class (Sets) manage the 20 single sets. You could use a vector (or an array I guess) in Sets, which would be pretty easy to do since you know there will be at most 20 sets.
As far as the indivual set class, that sounds like it is the bulk of the assignment. I would recommend identifying all of the operations that your assignment says must be supported by a single set, and add those to the public interface of your new class. To identify which ADT to use to hold the data in each set, you have to look at which operations are required. For example, does you assignment require the set to stay in some sort of sorted order (like the STL set)? If so, then maybe a binary tree of some sort. If not, (like MFC's CMap), you can use some sort of hash table. Will you have to be able to add and remove from the set quickly, or will you create the set once and then do read-only accessing the rest of the time? If you just fill the set once, and you need the data sorted, you can just put it into a vector and then sort it once after all the numbers have been entered.
Obviously, there are lots of possibilities of how to store the data, and it really depends on the usage requirements.
-
jawib: link list will not work here because operation using linked list will not meet the run time requirements.
jlou: thanks for the advice; thats exactly what I did now; I have a class holding one set, and another class that manipulates all 20. I used a stack to read in the members of the set into an array as in this particular assignment the order does not matter.
I'm working on the union and intersection parts of my program now. My professor said to use "bit vector" arrays...I'm not exactly sure what that means; I'm not familiar with the term. any ideas?