Prev: Mapping Templates function betweeen 2 class
Next: The reuse of keywords in the C++ standard
From: lallous on 23 Apr 2008 16:04
Hello Group,

Please advise. Does this work with all STL implementations?

Thank you,
Elias

[code]
#include <iostream>
#include <list>

typedef std::list<int> int_list_t;
typedef std::list<int_list_t::iterator> int_list_iterator_list_t;

void print_list(int_list_t &L)
{
for (int_list_t::iterator it=L.begin();it!=L.end();++it)
{
std::cout << "value = " << *it << std::endl;
}

}

void delete_odd(int_list_t &L)
{
int_list_iterator_list_t it_list;
int_list_t::iterator it;

for (it=L.begin();it!=L.end();++it)
{
if (*it % 2 != 0)
it_list.push_back(it);
}

for (int_list_iterator_list_t::const_iterator di=it_list.begin();di!
=it_list.end();++di)
{
L.erase(*di);
}

}

void populate_list(int_list_t &L, int start, int end)
{
L.clear();
for (int i=start;i<=end;i++)
L.push_back(i);

}

int main()
{
int_list_t L;

populate_list(L, 1, 10);
print_list(L);

std::cout << "---------------------" << std::endl;

delete_odd(L);
print_list(L);

return 0;

}
[/code]

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Paul M. Dubuc on 24 Apr 2008 06:19

lallous wrote:
> Hello Group,
>
> Please advise. Does this work with all STL implementations?
>

list<T>.erase() takes an iterator, not a value, so you don't want to
dereference di. You also don't want to increment the iterator value that
you
just used with erase(). Use the return value from erase() instead.

Yes, this should work with all conforming STL implementations. It will not
work for all types of STL containers, however. You should get a copy of
Scott
Meyers' book "Effective STL." Look at Item 9 in particular.


--
Paul M. Dubuc

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Ron Natalie on 24 Apr 2008 06:43
lallous wrote:
> Hello Group,
>
> Please advise. Does this work with all STL implementations

Doesn't work with any implementation as far as I know.


>
> for (int_list_iterator_list_t::const_iterator di=it_list.begin();di!
> =it_list.end();++di)
> {
> L.erase(*di);
> }
>
> }

An iterator to a deleted item in a list is invalid. You can't
apply ++di to it. This is why sequence erases return the next
iterator.

for (int_list_iterator_list_t::const_iterator di=it_list.begin();
di != it_list.end; )
{
it = L.erase(*di);
}

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Chris Uzdavinis on 24 Apr 2008 06:43
On Apr 24, 3:04 am, lallous <lall...(a)lgwm.org> wrote:
> Hello Group,
>
> Please advise. Does this work with all STL implementations?

Your code looks ok, but could still use some improvement to eliminate
some of the boilerplate code, and reduce the chances for hand-written
errors.


> void print_list(int_list_t &L)
> {
> for (int_list_t::iterator it=L.begin();it!=L.end();++it)
> {
> std::cout << "value = " << *it << std::endl;
> }
> }

First pass, I'd change to L a reference to a const object, since this
function doesn't actually change the object.

Then, you might consider using the copy algorithm into an
ostream_iterator. It's a common way of dumping a sequence.


> void delete_odd(int_list_t &L)
> {
> int_list_iterator_list_t it_list;
> int_list_t::iterator it;
>
> for (it=L.begin();it!=L.end();++it)
> {
> if (*it % 2 != 0)
> it_list.push_back(it);
> }
>
> for (int_list_iterator_list_t::const_iterator di=it_list.begin();di!
> =it_list.end();++di)
> {
> L.erase(*di);
> }
> }


I presume this iterator-list is intended to protect the list you're
traversing from being modified? It works but is overhead and not
strictly necessary. If you notice the return value from the erase()
function, it is the next iterator in the list. You can take advantage
of that fact and make this faster and simpler as follows:

void delete_odd(int_list_t & L)
{
int_list_t::iterator it = L.begin();
int_list_t::iterator const end = L.end();

while (it != end)
{
if (*it % 2 != 0)
it = L.erase(it);
else
++it;
}
}

But clearly, the traversal and iterator maintenance is mixed together
with your oddness checking, which is tedious and somewhat hides the
real intent of the code (other than the function name.) Since most of
that is boilerplate, it can (should) be factored out into a helper
function to abstract the concept. In fact, it already has been, in the
standard library function remove_if.

The only code you have that is really unique to this problem is the
test for whether the element should be erased or not. Factor that out
into its own inlined function object to be a simple predicate:

struct is_odd
{
bool operator()(int num) const { return num & 1; }
};


Then rewrite delete_odd using standard library function remove_if
which uses your predicate:

#include <algorithm>

void delete_odd(int_list_t & L)
{
// move the even elements to the front of the list
int_list_t::iterator logical_end =
std::remove_if(L.begin(), L.end(), is_odd());

// get rid of odd values that are now at the end of the list.
L.erase(logical_end, L.end());
}

Note that remove_if doesn't really remove anything, but bubbles the
keepers up to the front of the sequence, and puts the trash at the
end, returning the logical end of the sequence. Therefore, we erase
the trash at the end from the logical end to the physical end with the
call to erase on the list.

Just some ideas.

--
Chris

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

 | 
Pages: 1
Prev: Mapping Templates function betweeen 2 class
Next: The reuse of keywords in the C++ standard