By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
457,905 Members | 1,643 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 457,905 IT Pros & Developers. It's quick & easy.

STL :: Set operations on sorted structures

P: n/a
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
Share this Question
Share on Google+
8 Replies


P: n/a
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

P: n/a
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

P: n/a
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
Nov 24 '05 #4

P: n/a
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
Nov 24 '05 #5

P: n/a

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

Nov 24 '05 #6

P: n/a

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

Nov 24 '05 #7

P: n/a
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
Nov 25 '05 #8

P: n/a
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 discussion thread is closed

Replies have been disabled for this discussion.