P: n/a

I have a need for a set operation (actually multiset 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 "halfa**" 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 << "Retainedtoo collection\n";
copy(first.begin(), first.end(), ostream_iterator<int>(cout, " "));
cout << endl;
#endif
}  
Share this Question
P: n/a

Generic Usenet Account wrote: I have a need for a set operation (actually multiset 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  
P: n/a

Generic Usenet Account wrote: I have a need for a set operation (actually multiset 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.  
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 multiset 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  
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  
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 preincrement over
postincrement.
Gavin Deane  
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  
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  
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   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 3094
 replies: 8
 date asked: Nov 23 '05
