STL :: Set operations on sorted structures

[Generic Usenet Account]

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
}

[Mark P]

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

[Old Wolf]

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.

[Richard Herring]

In message <11**********************@z14g2000cwz.googlegroups .com>, Old
Wolf <ol*****@inspire.net.nz> 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

[Ben Pope]

Richard Herring wrote:

In message <11**********************@z14g2000cwz.googlegroups .com>, Old
Wolf <ol*****@inspire.net.nz> 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

[deane_gavin]

Ben Pope wrote:

Richard Herring wrote:

In message <11**********************@z14g2000cwz.googlegroups .com>, Old
Wolf <ol*****@inspire.net.nz> 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

[peter koch]

Richard Herring skrev:

In message <11**********************@z14g2000cwz.googlegroups .com>, Old
Wolf <ol*****@inspire.net.nz> 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

[Richard Herring]

In message <11**********************@g49g2000cwa.googlegroups .com>,
peter koch <pe***************@gmail.com> writes

Richard Herring skrev:

In message <11**********************@z14g2000cwz.googlegroups .com>, Old
Wolf <ol*****@inspire.net.nz> 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

[Generic Usenet Account]

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