473,224 Members | 1,721 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,224 software developers and data experts.

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

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

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

Similar topics

3
by: Andrew Clark | last post by:
*** post for FREE via your newsreader at post.newsfeed.com *** it's been a while since i have poseted to this newsgroup, but for a long time i was not programming at all. but now that i am out of...
13
by: Immanuel Goldstein | last post by:
Obtained under the Freedom of Information Act by the National Security Archive at George Washington University and posted on the Web today, the 74-page "Information Operations Roadmap" admits that...
3
by: Franco Perilli | last post by:
I've compiled this code and no problems, but when I run the program, it prints only the last entry i've inserted. Looks like a problem in the sorted insertion algorithm. Can u help me plz? ...
6
by: Burt | last post by:
I need to create a collection of classes (or structures) can be accessed by a string key, eg MyColl("ShortName5").Name for class with key ShortName5. But it also has to be sorted by a second...
5
by: WebSnozz | last post by:
Some collections are such that efficient search algorithms work on them such as binary search if the collection is a type which is sorted. I'm wondering how LINQ searches these collections and if...
11
by: John | last post by:
I am coding a radix sort in python and I think that Python's dictionary may be a choice for bucket. The only problem is that dictionary is a mapping without order. But I just found that if the...
1
by: stmfc | last post by:
what are the fundamental operations that 1- a list structure should support ? 2- a single linked list structure support ? i am asking only the operations which are must for these data...
8
by: Guy | last post by:
Is there a better way to search identical elements in a sorted array list than the following: iIndex = Array.BinarySearch( m_Array, 0, m_Array.Count, aSearchedObject ); aFoundObject= m_Array;...
7
by: Flavio | last post by:
Hi, I have been playing with set operations lately and came across a kind of surprising result given that it is not mentioned in the standard Python tutorial: with python sets, intersections ...
0
by: veera ravala | last post by:
ServiceNow is a powerful cloud-based platform that offers a wide range of services to help organizations manage their workflows, operations, and IT services more efficiently. At its core, ServiceNow...
0
by: VivesProcSPL | last post by:
Obviously, one of the original purposes of SQL is to make data query processing easy. The language uses many English-like terms and syntax in an effort to make it easy to learn, particularly for...
3
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 3 Jan 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). For other local times, please check World Time Buddy In...
0
by: mar23 | last post by:
Here's the situation. I have a form called frmDiceInventory with subform called subfrmDice. The subform's control source is linked to a query called qryDiceInventory. I've been trying to pick up the...
0
by: fareedcanada | last post by:
Hello I am trying to split number on their count. suppose i have 121314151617 (12cnt) then number should be split like 12,13,14,15,16,17 and if 11314151617 (11cnt) then should be split like...
0
by: stefan129 | last post by:
Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific...
0
Git
by: egorbl4 | last post by:
Скачал я git, хотел начать настройку, а там вылезло вот это Что это? Что мне с этим делать? ...
1
by: davi5007 | last post by:
Hi, Basically, I am trying to automate a field named TraceabilityNo into a web page from an access form. I've got the serial held in the variable strSearchString. How can I get this into the...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.