STL :: Set operations on sorted structures

Discussion in 'C++' started by Generic Usenet Account, Nov 23, 2005.

  1. I have a need for a set operation (actually multi-set operation) on
    sorted structures that is not in the STL library. I call it the
    set_retain operation. It's kinda similar to the set_intersection
    operation. Let me explain with an example:
    S1: {1, 1, 5, 7, 8, 8, 9, 15, 17, 18, 23, 26, 26, 33, 39, 43, 48}
    S2: {1, 7, 9, 18, 26, 33}

    The output of this operation is {1, 1, 7, 9, 18, 26, 26, 33}

    In other words, S1 retains all the elements that are in S2, and deletes
    all the others. The STL set_intersection operation would have yielded
    just {1, 7, 9, 18, 26, 33}

    I have written the following sample code to realize this operation. It
    seems to work, but I am having trouble trying to describe the operation
    using the signature for set operations on sorted structures, as
    described in the STL standard

    This is what I would like the signature to be:
    template <class InputIterator1, class InputIterator2, class
    OutputIterator>
    void
    set_retain(InputIterator1& first1, InputIterator1& last1,
    InputIterator2& first2, InputIterator2& last2,
    OutputIterator result)
    {
    ....
    }


    I get many cryptic compiler errors. Any pointers would be appreciated.

    Thanks,
    Gus



    My "half-a**" implementation follows...

    ////////////////////////////////////////////////////////
    template <typename T>
    void
    set_retain(vector<T>& first, vector<T>& second)
    {
    typename vector<T>::iterator resumePos = first.begin();
    typename vector<T>::iterator itor, itor2, endOfIntxn = second.end();

    bool trailElem = false;
    for(itor = second.begin(); itor != endOfIntxn; itor++)
    {
    trailElem = false;
    for(itor2 = resumePos; itor2 != first.end();)
    {
    if(*itor == *itor2)
    {
    itor2++;
    continue;
    }
    else
    if(*itor < *itor2)
    {
    trailElem = true;
    resumePos = itor2;
    itor2++;
    break;
    }
    else // *itor > *itor2
    {
    first.erase(itor2);
    }
    }
    }

    if(trailElem)
    first.erase(resumePos, first.end());

    #ifdef DEBUG
    cout << "Retained-too collection\n";
    copy(first.begin(), first.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
    #endif
    }
     
    Generic Usenet Account, Nov 23, 2005
    #1
    1. Advertising

  2. Generic Usenet Account

    Mark P Guest

    Generic Usenet Account wrote:
    > I have a need for a set operation (actually multi-set operation) on
    > sorted structures that is not in the STL library. I call it the
    > set_retain operation. It's kinda similar to the set_intersection
    > operation. Let me explain with an example:
    > S1: {1, 1, 5, 7, 8, 8, 9, 15, 17, 18, 23, 26, 26, 33, 39, 43, 48}
    > S2: {1, 7, 9, 18, 26, 33}
    >
    > The output of this operation is {1, 1, 7, 9, 18, 26, 26, 33}
    >
    > In other words, S1 retains all the elements that are in S2, and deletes
    > all the others. The STL set_intersection operation would have yielded
    > just {1, 7, 9, 18, 26, 33}
    >
    > I have written the following sample code to realize this operation. It
    > seems to work, but I am having trouble trying to describe the operation
    > using the signature for set operations on sorted structures, as
    > described in the STL standard
    >
    > This is what I would like the signature to be:
    > template <class InputIterator1, class InputIterator2, class
    > OutputIterator>
    > void
    > set_retain(InputIterator1& first1, InputIterator1& last1,
    > InputIterator2& first2, InputIterator2& last2,
    > OutputIterator result)
    > {
    > ...
    > }
    >
    >
    > I get many cryptic compiler errors. Any pointers would be appreciated.
    >
    > Thanks,
    > Gus
    >
    >


    I'm assuming both input containers are sorted with the same comparison
    function. How about something like the following?

    // note: untested code-- use at your own risk :)

    InputIterator1 it1 = first1;
    InputIterator2 it2 = first2;

    while (it1 != last1 && it2 != last2)
    {
    if (*it1 < *it2)
    ++it1;
    else if (*it2 < *it1)
    ++it2;
    else // *it1 == *it2
    {
    *result = *it1;
    ++result;
    ++it1;
    }
    }


    --Mark
     
    Mark P, Nov 23, 2005
    #2
    1. Advertising

  3. Generic Usenet Account

    Old Wolf Guest

    Generic Usenet Account wrote:

    > I have a need for a set operation (actually multi-set operation) on
    > sorted structures that is not in the STL library. I call it the
    > set_retain operation. It's kinda similar to the set_intersection
    > operation.
    >
    > This is what I would like the signature to be:
    > template <class InputIterator1, class InputIterator2, class
    > OutputIterator>
    > void
    > set_retain(InputIterator1& first1, InputIterator1& last1,
    > InputIterator2& first2, InputIterator2& last2,
    > OutputIterator result)
    > {
    > ...
    > }


    Iterators should be passed by value.
     
    Old Wolf, Nov 23, 2005
    #3
  4. In message <>, Old
    Wolf <> writes
    >Generic Usenet Account wrote:
    >
    >> I have a need for a set operation (actually multi-set operation) on
    >> sorted structures that is not in the STL library. I call it the
    >> set_retain operation. It's kinda similar to the set_intersection
    >> operation.
    >>
    >> This is what I would like the signature to be:
    >> template <class InputIterator1, class InputIterator2, class
    >> OutputIterator>
    >> void
    >> set_retain(InputIterator1& first1, InputIterator1& last1,
    >> InputIterator2& first2, InputIterator2& last2,
    >> OutputIterator result)
    >> {
    >> ...
    >> }

    >
    >Iterators should be passed by value.
    >


    Why?

    --
    Richard Herring
     
    Richard Herring, Nov 24, 2005
    #4
  5. Generic Usenet Account

    Ben Pope Guest

    Richard Herring wrote:
    > In message <>, Old
    > Wolf <> writes
    >>
    >> Iterators should be passed by value.
    >>

    >
    > Why?


    Most of the time they're pointers and so they're the same size, and so
    thats one less indirection than passing by reference.

    ....just guessing.

    Ben
     
    Ben Pope, Nov 24, 2005
    #5
  6. Generic Usenet Account

    Guest

    Ben Pope wrote:
    > Richard Herring wrote:
    > > In message <>, Old
    > > Wolf <> writes
    > >>
    > >> Iterators should be passed by value.
    > >>

    > >
    > > Why?

    >
    > Most of the time they're pointers and so they're the same size, and so
    > thats one less indirection than passing by reference.
    >
    > ...just guessing.


    std::vector iterators can be implemented as pointers but I'm not sure
    whether iterators for any other std containers can be.

    And if iterators were usually pointers I expect we'd have a lot fewer
    people suggesting that we should prefer pre-increment over
    post-increment.

    Gavin Deane
     
    , Nov 24, 2005
    #6
  7. Generic Usenet Account

    peter koch Guest

    Richard Herring skrev:

    > In message <>, Old
    > Wolf <> writes

    [snip]
    >
    > >Iterators should be passed by value.
    > >

    >
    > Why?
    >
    > --
    > Richard Herring


    Iterators should be (and in practice they are) lightweight objects
    where passing by value is more efficient.

    /Peter
     
    peter koch, Nov 24, 2005
    #7
  8. In message <>,
    peter koch <> writes
    >
    >Richard Herring skrev:
    >
    >> In message <>, Old
    >> Wolf <> writes

    >[snip]
    > >
    >> >Iterators should be passed by value.

    >>
    >> Why?

    >
    >Iterators should be (and in practice they are) lightweight objects


    Iterators are _any_ kind of object which models the concept of Iterator.
    Not everything used as an iterator is lightweight - for example, an
    istream_iterator has to contain a copy of the last item it read, which
    could be arbitrarily complex.

    >where passing by value is more efficient.


    Have you measured it?

    --
    Richard Herring
     
    Richard Herring, Nov 25, 2005
    #8
  9. Mark P wrote:

    > // note: untested code-- use at your own risk :)
    >
    > InputIterator1 it1 = first1;
    > InputIterator2 it2 = first2;
    >
    > while (it1 != last1 && it2 != last2)
    > {
    > if (*it1 < *it2)
    > ++it1;
    > else if (*it2 < *it1)
    > ++it2;
    > else // *it1 == *it2
    > {
    > *result = *it1;
    > ++result;
    > ++it1;
    > }
    > }
    >


    The correct code turned out to be slightly different...

    Instead of
    > else // *it1 == *it2
    > {
    > *result = *it1;
    > ++result;
    > ++it1;
    > }


    it turned out to be
    else // *it1 == *it2
    {
    while(*it1 == *it2)
    {
    *result = *it1;
    ++result;
    ++it1;
    }
    ++it2;
    }

    I have posted the source code to comp.sources.d


    Gus
     
    Generic Usenet Account, Dec 7, 2005
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Jesus M. Salvo Jr.
    Replies:
    2
    Views:
    4,246
    robert
    Feb 11, 2006
  2. Kushal
    Replies:
    2
    Views:
    6,217
    tom_usenet
    Jan 30, 2004
  3. Alfonso Morra
    Replies:
    11
    Views:
    721
    Emmanuel Delahaye
    Sep 24, 2005
  4. Replies:
    1
    Views:
    274
    Heinz Ozwirk
    Mar 17, 2006
  5. Steve Howell
    Replies:
    1
    Views:
    345
    Steve Howell
    Nov 18, 2009
Loading...

Share This Page