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

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!

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

---

is there a method without using pointers?

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)
{






}

---

>> 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.

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

---

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?

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.

Are you sure about that? Josuttis even uses duplicates in his example of set_intersection.

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

Quote:

---

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.