Thread: creating new sets

  1. #1
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572

    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

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  2. #2
    Senior Member joshdick's Avatar
    Join Date
    Nov 2002
    Location
    Phildelphia, PA
    Posts
    1,146
    The STL has classes for both vectors and sets. Sounds like you could use a vector full of sets.
    FAQ

    "The computer programmer is a creator of universes for which he alone is responsible. Universes of virtually unlimited complexity can be created in the form of computer programs." -- Joseph Weizenbaum.

    "If you cannot grok the overall structure of a program while taking a shower, you are not ready to code it." -- Richard Pattis.

  3. #3
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    easier said then done, huh joshdick? unfortunately I can only use vectors from the stl.

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  4. #4
    Veni Vidi Vice
    Join Date
    Aug 2001
    Posts
    343
    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
    01000111011011110110111101100100 011101000110100001101001011011100110011101110011 01100100011011110110111001110100 01100011011011110110110101100101 01100101011000010111100101110011 0110100101101110 01101100011010010110011001100101
    Good things donīt come easy in life!!!

  5. #5
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    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.

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  6. #6
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972
    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...
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

  7. #7
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,090
    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.

  8. #8
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    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?

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem aligning floating point numbers
    By esbo in forum C Programming
    Replies: 4
    Last Post: 01-05-2009, 08:09 PM
  2. Profiler Valgrind
    By afflictedd2 in forum C++ Programming
    Replies: 4
    Last Post: 07-18-2008, 09:38 AM
  3. creating an application
    By Cpro in forum C++ Programming
    Replies: 21
    Last Post: 05-30-2008, 12:21 AM
  4. Major Problems with GetSaveFileName() and GetOpenFileName()
    By CodeHacker in forum Windows Programming
    Replies: 8
    Last Post: 07-12-2004, 11:05 AM
  5. Just one Question?
    By Irish-Slasher in forum C++ Programming
    Replies: 6
    Last Post: 02-12-2002, 10:19 AM