Linked List Subtraction

[Linell Bonnette]

I'm trying to overload the - and -= operators for use on a linked list. I need to be able to subtract two linked lists. So if, as an example, I had

{2,2,2,3,2,2,1} - {2,2,3}

I would get

{2,2,2,1}

as a result.

So far I have this as a non-member function:

bag operator -(const bag& b1, const bag& b2)
    {
        bag answer;
        
        answer -= b1; 
        answer -= b2;
        return answer;
    }

However, I am missing the member function -=. I have the += function, but I'm not sure how to do it backwards.

How should I go about doing this?

[anon]

The semantics of the binary operator is wrong. It should create a list of items in b2, except those found in b1. Instead you remove the values of both operands from a default (empty?) bag.

As to implementing -=, simplest would be to find each item and erase it from the left-hand collection.

(Actually what it should do is not entirely clear. What if b2 contains items not found in b1? Does the order of items in b2 matter (is {2,2,2,3,2,2,1} - {1,2,3} {2,2,2,2} or {2, 2, 2, 2, 1})?

[Linell Bonnette]

The semantics of the binary operator is wrong. It should create a list of items in b2, except those found in b1. Instead you remove the values of both operands from a default (empty?) bag.

As to implementing -=, simplest would be to find each item and erase it from the left-hand collection.

(Actually what it should do is not entirely clear. What if b2 contains items not found in b1? Does the order of items in b2 matter (is

{2,2,2,3,2,2,1} - {1,2,3} {2,2,2,2} or {2, 2, 2, 2, 1}

)?

Sorry for the confusion. The order does not matter, it simply seeks to remove any matching element. If there are items found in b2 that aren't found in b1, then it shouldn't be found in b3-which is where they will be stored.

[iMalc]

Does the order of items in b2 matter?

FYI, a 'bag' (as per the name of the class with the operator overload shown above) is a mathematical term for a container that has no ordering, allows duplicates, and is formerly written using curly brackets as the OP did here.

Implementing a bag internally as a linked-list is not the ideal situation as it doesn't allow for the most performant operations on larger datasets, but it will do for basic examples. As adak suggests, you simply need to search for and delete one occurrence of each element in the bag provided in the argument, from the items in the bag of the current object. You could make a function to delete a specified element it you like and then loop over the input bag and call the delete helper function for each item.

More info about Sets, Bags, and Sequences: Mathematical Background

[laserlight]

a 'bag' (...) is a mathematical term for a container that has no ordering, allows duplicates

Or in terms of the C++ standard library, a std::multiset or std::unordered_multiset.

[Elysia]

Yes, this souds more like a set, and '-' sounds more like the exclusion operator (what is it called again?) '\'.
I don't think you should attempt this on a linked list.

[Linell Bonnette]

void bag::operator -=(const bag& sub)
        // Library facilities used: cstdlib, node1.h
    {
        node *cursor;
        for (cursor = sub.head_ptr; cursor != NULL; cursor = cursor-> link() ) {
            if (<#condition#>) {
                <#statements#>
            }
        }
    }

I have to implement it by using a linked list.

How would I go about using the code here to make it delete the items in another bag. That's the main problem I'm having. I'm not sure how I can access the elements of another bag by using the function here.
I want bag1 -= bag2 to make bag1 become all of the elements of bag1 except those found in bag two.

By stepping through all of the elements of bag2, I should be able to find the elements that appear in this. How can I find them in bag1 to delete?

[iMalc]

Try making a function that searches for an item in the bag and deletes it if it was found, else does nothing.
Then just call this function for each item in bag2.
This was actually my suggestion earlier, and it should make this easier, avoiding the need to write nested loops and you wont need "if (<#condition#>)" then either.