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]

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]

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]

Iterators should be passed by value.

Why?

 

[Ben Pope]

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]

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 <[email protected]>, Old
>

Why?

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

/Peter

 

[Richard Herring]

Richard Herring skrev:


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?

 

[Generic Usenet Account]

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