Linked List Subtraction

This is a discussion on Linked List Subtraction within the C++ Programming forums, part of the General Programming Boards category; I'm trying to overload the - and -= operators for use on a linked list. I need to be able ...

  1. #1
    Registered User
    Join Date
    Oct 2011
    Posts
    15

    Linked List Subtraction

    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
    Code:
    {2,2,2,3,2,2,1} - {2,2,3}
    I would get
    Code:
    {2,2,2,1}
    as a result.

    So far I have this as a non-member function:
    Code:
    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?

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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})?
    Last edited by anon; 10-10-2011 at 03:08 PM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Registered User
    Join Date
    Oct 2011
    Posts
    15
    Quote Originally Posted by anon View Post
    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
    Code:
    {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.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    Quote Originally Posted by anon View Post
    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
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,639
    Quote Originally Posted by iMalc
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,546
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  7. #7
    Registered User
    Join Date
    Oct 2011
    Posts
    15
    Code:
    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?

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 05-01-2010, 10:19 PM
  2. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  3. Replies: 5
    Last Post: 11-04-2006, 05:39 PM
  4. singly linked list to doubly linked list
    By t48j in forum C Programming
    Replies: 3
    Last Post: 03-23-2005, 05:37 PM
  5. Replies: 6
    Last Post: 03-02-2005, 01:45 AM

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