Implementation of set class in C++

This is a discussion on Implementation of set class in C++ within the C++ Programming forums, part of the General Programming Boards category; I have written a function that emulates set_intersection somewhat, with a few teething problems. Firstly, here is my main code: ...

  1. #1
    Registered User
    Join Date
    Sep 2006
    Posts
    9

    Question Implementation of set class in C++

    I have written a function that emulates set_intersection somewhat, with a few teething problems.
    Firstly, here is my main code:

    *******************************************
    Code:
    #include <cstdlib>
    #include <iomanip>
    #include <string>
    #include <iostream>
    #include <string>
    
    using namespace std;
    
    string stringSet = "ABC";
    string otherset = "AC";
    string commElmts;
    string result;
    
    void set_intersection(string , string );
    
    
    int main()
    {            
    set_intersection(stringSet, otherset);
    
      system("PAUSE"); 
    
    }
     
    void set_intersection(string stringSet, string otherset)
    {
     for(int i = 0; i < otherset.length(); i++)
            { 
           if( stringSet.find( otherset[i] ) != string::npos )
           result =result + otherset[i];
           commElmts = result;
           }
     cout<< commElmts<<endl;
    };
    *************************************
    My first problem arrises when say, stringSet = "ABC" and otherset =
    "AACD". My output is; "AAC". How do I ensure that a commom element is only outputted once? I think I must implement the class set, I must write the code myself, not use the STL library, which will allow me to store each character once. Is there anyway of modifying my code to do this or alternatively, how do i implement the set class?

    I appreciate your help,
    Ilan

  2. #2
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    Well, if you used find member function of string then I suggest something like this:
    Code:
    void set_intersection(string stringSet, string otherset)
    {
        for(int i = 0; i < otherset.length(); i++)
        { 
           if((stringSet.find( otherset[i] ) != string::npos) && 
                (result.find(otherset[i]) == string::npos))
           result =result + otherset[i];
           commElmts = result;
        }
     cout<< commElmts<<endl;
    };
    P.S.
    I wouldn't use global variables, but that is up to you!
    Last edited by Micko; 09-20-2006 at 11:27 PM.
    Gotta love the "please fix this for me, but I'm not going to tell you which functions we're allowed to use" posts.
    It's like teaching people to walk by first breaking their legs - muppet teachers! - Salem

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >How do I ensure that a commom element is only outputted once?
    You're faking the STL algorithm, right? What it does is a merge, where only matching items are copied to the destination. Your algorithm doesn't do the same thing, and you'll have a hard time emulating that functionality with string::find. The actual algorithm would be implemented something like this:
    Code:
    template<typename In1, typename In2, typename Out>
    Out set_intersection(In1 first1, In1 last1, In2 first2, In2 last2, Out dst)
    {
      while ( first1 != last1 && first2 != last2 ) {
        if ( *first1 < *first2 )
          ++first1;
        else if ( *first2 < *first1 )
          ++first2;
        else {
          *dst++ = *first1++;
          ++first2;
        }
      }
    
      return dst;
    }
    My best code is written with the delete key.

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    9
    is there a method without using pointers?

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    9

    Question Template of definition

    I am only passing is 2 strings and want to return a third string, that is the intersection of the 2 strings that were passed in.
    something like what i have below:


    Code:
    StringGroup StringGroup::set_intersection(StringGroup otherGroup)
    {
    
    
    
    
    
    
    }

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,319
    >> is there a method without using pointers?
    That doesn't use pointers, it uses templated types that can be pointers but are usually iterators.

    To fix your original code, you could modify the strings and remove the character that you find from each as you move through the loop. You won't affect the original strings because the function arguments are passed by value. Doing that is still a bit tricky, but you should be able to get it to work.

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    3
    What about this:
    Code:
    string set_intersection2(const string& set1, const string& set2)
    {
        // record chars that have already been found to intersect so that we don't
        // add them to result more than once
        int hits[256];
        memset(hits, 0, sizeof(hits));
               
        string result;
        char cur;
        for (unsigned int i = 0; i < set2.length(); i++) {
            cur = set2[i];
            // check if we already found char
            if (set1.find(cur) != string::npos) {
                if (hits[(int)cur] == 0) {
                    // found new char
                    hits[(int)cur] = 1;
                    result += cur;
                } else {
                    // already found char so don't add to result
                }
            }
        }
    
        return result;
    }

  8. #8
    Registered User
    Join Date
    Jan 2005
    Posts
    7,319
    But wouldn't the set intersection of "AABC" and "AACD" be "AAC"? In other words, if there are multiple instances of an element in both sets, the intersection should have multiple instances of that element, right?

  9. #9
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    The STL algorithm set_intersection requires the two input sequences to already conform to the STL concept of a set (not as in std::set). This concept requires that there are no duplicates in the source sequence in the first place, so the question ought to be moot.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  10. #10
    Registered User
    Join Date
    Jan 2005
    Posts
    7,319
    Are you sure about that? Josuttis even uses duplicates in his example of set_intersection.

  11. #11
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    I was sure. Now I'm no longer ...

    I'll look it up.


    Edit: I was wrong.
    http://www.sgi.com/tech/stl/set_intersection.html
    2). The general case is more complicated, because the input ranges may contain duplicate elements. The generalization is that if a value appears m times in [first1, last1) and n times in [first2, last2) (where m or n may be zero), then it appears min(m,n) times in the output range.
    It's actually even more complicated, as explained in a footnote, but that complication does not apply to integers, characters, or even strings.
    Last edited by CornedBee; 09-21-2006 at 03:38 PM.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Getting an error with OpenGL: collect2: ld returned 1 exit status
    By Lorgon Jortle in forum C++ Programming
    Replies: 6
    Last Post: 05-08-2009, 08:18 PM
  2. matrix class
    By shuo in forum C++ Programming
    Replies: 2
    Last Post: 07-13-2007, 01:03 AM
  3. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 02:39 PM
  4. Message class ** Need help befor 12am tonight**
    By TransformedBG in forum C++ Programming
    Replies: 1
    Last Post: 11-29-2006, 10:03 PM
  5. My Window Class
    By Epo in forum Game Programming
    Replies: 2
    Last Post: 07-10-2005, 02:33 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21