473,224 Members | 1,721 Online

# STL :: Set operations on sorted structures

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
}

Nov 23 '05 #1
8 3315
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
Nov 23 '05 #2
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.

Nov 23 '05 #3
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
Nov 24 '05 #4
Richard Herring wrote:
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
Nov 24 '05 #5

Ben Pope wrote:
Richard Herring wrote:
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

Nov 24 '05 #6

Richard Herring skrev:
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

Nov 24 '05 #7
peter koch <pe***************@gmail.com> writes

Richard Herring skrev:
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
Nov 25 '05 #8
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

Dec 7 '05 #9

This thread has been closed and replies have been disabled. Please start a new discussion.