473,320 Members | 1,902 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,320 software developers and data experts.

Is it generally safe to inherit from STL iterator classes?

I understand why it is not safe to inherit from STL containers, but I have
found (in SGI STL documentation) that for example bidirectional_iterator
class can be used to create your own iterator classes by inheriting from
it, ie.

class my_bidirectional_iterator : public bidirectional_iterator<double>
{
...
};

I'm trying to implement STL compatible iterators for my custom class but I
need to change type returned by dereferencing my iterators, and inheriting
from bidirectional_iterator would make my job much easier of course. Now,
what I'm wondering, do I need to use SGI STL to do that safely, or it is
standard behavior for STL?

I have found few tutorials about creating custom iterators and I think I
understand how to do it, but before I start, I want to know is it worth
(safe) to do it and there is nothing in tutorials that explains that...

T.A.
Sep 23 '06 #1
21 5668
"T.A." <to*************@gmail.comwrote:
I understand why it is not safe to inherit from STL containers, but I have
found (in SGI STL documentation) that for example bidirectional_iterator
class can be used to create your own iterator classes by inheriting from
it, ie.

class my_bidirectional_iterator : public bidirectional_iterator<double>
{
...
};

I'm trying to implement STL compatible iterators for my custom class but I
need to change type returned by dereferencing my iterators, and inheriting
from bidirectional_iterator would make my job much easier of course. Now,
what I'm wondering, do I need to use SGI STL to do that safely, or it is
standard behavior for STL?
Bidirectional_iterator has no member functions, member variables, or
nested types. It exists solely to simplify the definition of the
functions iterator_category, distance_type, and value_type.

The only reason bidirectional_iterator exists is so you don't have to
put the three typedefs in your class. So inherit away. Do not inherit
from std::vector::iterator though.

--
There are two things that simply cannot be doubted, logic and perception.
Doubt those, and you no longer have anyone to discuss your doubts with,
nor any ability to discuss them.
Sep 23 '06 #2
Daniel T. wrote:
"T.A." <to*************@gmail.comwrote:
>I understand why it is not safe to inherit from STL containers, but I
have found (in SGI STL documentation) that for example
bidirectional_iterator class can be used to create your own iterator
classes by inheriting from it, ie.

class my_bidirectional_iterator : public bidirectional_iterator<double>
{
...
};

I'm trying to implement STL compatible iterators for my custom class but
I need to change type returned by dereferencing my iterators, and
inheriting from bidirectional_iterator would make my job much easier of
course. Now, what I'm wondering, do I need to use SGI STL to do that
safely, or it is standard behavior for STL?

Bidirectional_iterator has no member functions, member variables, or
nested types. It exists solely to simplify the definition of the
functions iterator_category, distance_type, and value_type.

The only reason bidirectional_iterator exists is so you don't have to
put the three typedefs in your class. So inherit away. Do not inherit
from std::vector::iterator though.
Huh? I just found myself inheriting from std::set::const_iterator the other
day, and I don't see anything wrong with it. The standard arguments agains
inheriting from non-polymorphic classes do not apply: you don't use
std::vector::iterator* polymorphically and the functions taking
std::vector::iterator& as arguments all should be templated on an iterator
type anyway (and the ones from STL are). Could you please elaborate?

For concreteness, the code where I did it, is in this posting:

http://groups.google.com/group/comp....5246c3ffbb9cfc

It defines a policy tracked<Tto be used as

class TrackedClass : public tracked<TrackedClass{
...
}

and automatically adds to the interface of TrackedClass functionality to
iterate over all objects of type TrackedClass that currently exist.
Underlying this logic is a static std::set< tracked* object since casting
to TrackedClass* is not available in tracked< TrackedClass >. Thus, an
iterator type is provided whose operator* performs the necessary up-cast.
Best

Kai-Uwe Bux
Sep 23 '06 #3
On Sat, 23 Sep 2006 11:12:44 -0400, Kai-Uwe Bux wrote:
Daniel T. wrote:

...

Huh? I just found myself inheriting from std::set::const_iterator the other
day, and I don't see anything wrong with it. The standard arguments agains
inheriting from non-polymorphic classes do not apply: you don't use
std::vector::iterator* polymorphically
OK, this makes a sense... No reason to use iterators polymorphically...

But I wonder will something like this work nice and safe (from the point of
view of STL algorithms):

class SomeClass;

class MyClass {

private:
typedef SmartPointer<SomeClasssmart_pointer;
typedef std::vector<smart_pointersmart_pointer_vector;

smart_pointer_vector itsContents;

public:
class iterator : public smart_pointer_vector::iterator {
...
};

iterator begin() { return itsContents.begin(); }
iterator end() { return itsContents.end(); }
}

Now, when somebody uses, for example, find algorithm on MyClass will it
work as expected, or there are some dangers that I'm not aware of? (I think
it will work but I'm still quite new to C++ so I decided to double check)

TIA
Sep 23 '06 #4
T.A. wrote:
On Sat, 23 Sep 2006 11:12:44 -0400, Kai-Uwe Bux wrote:
>Daniel T. wrote:

...

Huh? I just found myself inheriting from std::set::const_iterator the
other day, and I don't see anything wrong with it. The standard arguments
agains inheriting from non-polymorphic classes do not apply: you don't
use std::vector::iterator* polymorphically

OK, this makes a sense... No reason to use iterators polymorphically...

But I wonder will something like this work nice and safe (from the point
of view of STL algorithms):

class SomeClass;

class MyClass {

private:
typedef SmartPointer<SomeClasssmart_pointer;
typedef std::vector<smart_pointersmart_pointer_vector;

smart_pointer_vector itsContents;

public:
class iterator : public smart_pointer_vector::iterator {
...
};

iterator begin() { return itsContents.begin(); }
iterator end() { return itsContents.end(); }
}

Now, when somebody uses, for example, find algorithm on MyClass will it
work as expected, or there are some dangers that I'm not aware of? (I
think it will work but I'm still quite new to C++ so I decided to double
check)
Thanks for being persistent and sceptical.

So I think I figured out what is wrong about inheriting from standard
iterators: to begin with, it might not even be possible! All iterator types
in the standard container are implementation defined. It follows that,
e.g., std::vector<T>::iterator might be just a T*. In this case, you simply
cannot inherit from it. Also, there are methods to inhibit inheritance. The
standard has no provisions demanding that std::set<T>::iterator does not
use such techniques to prevent derivation. Thus, whenever you write

class my_iterator : public std::vector<T>::iterator

you are non-portable because you are relying on a feature of your STL that
happens to allow derivation.

Another problem arises generally from "inheritance for convenience":
functions might match. Consider a derivation like

class my_iterator : std::vector<T>::iterator { ... };

Someone might have defined a function

void do_something ( std::vector<T>::iterator from,
std::vector<T>::iterator to ) { ... }

Note that my_iterator is a std::vector<T>::iterator. Thus, you can call
do_something on your container. The bad thing, however, is that the
parameters will be sliced and the semantics of the vector iterators will be
used. Very likely this will give rise to a surprising bug. Arguably, the
designer of do_something() is at least as guilty as the designer of
my_iterator: had do_something() been properly templated, there would be no
problem.

So, what about algorithms from the standard library? They are all properly
templated, so we should be fine, right? Well, there still is a catch:
consider Mr. I-type-everything-in-one-line. He writes:

my_iterator a_iter;
my_iterator b_iter;
...
std::transform( a_iter++, b_iter--, ... );

What happend? We inherited from std::vector<T>::iterator so that we do not
have to write all those member functions ourselves, right? Well, too bad:
the postfix operator ++ returns a std::vector<T>::iterator and not a
my_iterator. Thus, the wrong template will be chosen.
I guess, I thoroughly refuted my initial thought that there is nothing wrong
with inheriting from std::...<T>::iterator. It is, indeed, riddled with
difficulties. Oh well, I better revise the tracked<Ttemplate to use
composition instead of derivation.
Sorry for the confusion

Kai-Uwe Bux
Sep 24 '06 #5
On Sat, 23 Sep 2006 21:18:35 -0400, Kai-Uwe Bux wrote:
On Sat, 23 Sep 2006 11:12:44 -0400, Kai-Uwe Bux wrote:

Thanks for being persistent and sceptical.

So I think I figured out what is wrong about inheriting from standard
iterators: to begin with, it might not even be possible! All iterator types
in the standard container are implementation defined. It follows that,
e.g., std::vector<T>::iterator might be just a T*. In this case, you simply
cannot inherit from it. Also, there are methods to inhibit inheritance. The
standard has no provisions demanding that std::set<T>::iterator does not
use such techniques to prevent derivation. Thus, whenever you write

class my_iterator : public std::vector<T>::iterator

you are non-portable because you are relying on a feature of your STL that
happens to allow derivation.

Another problem arises generally from "inheritance for convenience":
functions might match. Consider a derivation like

class my_iterator : std::vector<T>::iterator { ... };

Someone might have defined a function

void do_something ( std::vector<T>::iterator from,
std::vector<T>::iterator to ) { ... }

Note that my_iterator is a std::vector<T>::iterator. Thus, you can call
do_something on your container. The bad thing, however, is that the
parameters will be sliced and the semantics of the vector iterators will be
used. Very likely this will give rise to a surprising bug. Arguably, the
designer of do_something() is at least as guilty as the designer of
my_iterator: had do_something() been properly templated, there would be no
problem.

So, what about algorithms from the standard library? They are all properly
templated, so we should be fine, right? Well, there still is a catch:
consider Mr. I-type-everything-in-one-line. He writes:

my_iterator a_iter;
my_iterator b_iter;
...
std::transform( a_iter++, b_iter--, ... );

What happend? We inherited from std::vector<T>::iterator so that we do not
have to write all those member functions ourselves, right? Well, too bad:
the postfix operator ++ returns a std::vector<T>::iterator and not a
my_iterator. Thus, the wrong template will be chosen.

I guess, I thoroughly refuted my initial thought that there is nothing wrong
with inheriting from std::...<T>::iterator. It is, indeed, riddled with
difficulties. Oh well, I better revise the tracked<Ttemplate to use
composition instead of derivation.

Sorry for the confusion

Kai-Uwe Bux
So I guess it is true that only thing to inherit from safely are base
iterator classes (in this case probably the best one would be
std::random_access_iterator) and reimplemetation of whole my_iterator
interface. OK, I probably can do that... Now one more thing... I have found
this in docs:

"random_access_iterator is an iterator base class: it is intended that an
iterator that is a model of Random Access Iterator, and whose value type
and distance type are T and Distance, may be defined by inheriting from
random_access_iterator<T, Distance>
....
This class is no longer part of the C++ standard, although it was present
in early drafts of the standard. It is retained in this implementation for
backward compatibility."

As you see, even this is obsolete... As I understand, using iterator_traits
mechanism is currently the way to implement custom iterator types in
standard way:

"If you are defining a new iterator type I, then you must ensure that
iterator_traits<Iis defined properly. There are two ways to do this.
First, you can define your iterator so that it has nested types
I::value_type, I::difference_type, and so on. Second, you can explicitly
specialize iterator_traits for your type. The first way is almost always
more convenient, however, especially since you can easily ensure that your
iterator has the appropriate nested types just by inheriting from one of
the base classes input_iterator, output_iterator, forward_iterator,
bidirectional_iterator, or random_access_iterator.

Note that iterator_traits is new; it was added to the draft C++ standard
relatively recently. Both the old iterator tags mechanism and the new
iterator_traits mechanism are currently supported [1], but the old iterator
tag functions are no longer part of the standard C++ library and they will
eventually be removed. "

And no inheritance is involved in that. A bit more work than simply
inheriting from existing iterators, though, but that's the way to do it...
Thanks for your help...

Cheers.
Sep 24 '06 #6
Kai-Uwe Bux <jk********@gmx.netwrote:
Daniel T. wrote:
>"T.A." <to*************@gmail.comwrote:
>>I understand why it is not safe to inherit from STL containers,
but I have found (in SGI STL documentation) that for example
bidirectional_iterator class can be used to create your own
iterator classes by inheriting from it, ie.

class my_bidirectional_iterator : public
bidirectional_iterator<double{ ... };

I'm trying to implement STL compatible iterators for my custom
class but I need to change type returned by dereferencing my
iterators, and inheriting from bidirectional_iterator would make
my job much easier of course. Now, what I'm wondering, do I need
to use SGI STL to do that safely, or it is standard behavior for
STL?

Bidirectional_iterator has no member functions, member variables,
or nested types. It exists solely to simplify the definition of the
functions iterator_category, distance_type, and value_type.

The only reason bidirectional_iterator exists is so you don't have
to put the three typedefs in your class. So inherit away. Do not
inherit from std::vector::iterator though.

Huh? I just found myself inheriting from std::set::const_iterator
the other day, and I don't see anything wrong with it. The standard
arguments agains inheriting from non-polymorphic classes do not
apply: you don't use std::vector::iterator* polymorphically and the
functions taking std::vector::iterator& as arguments all should be
templated on an iterator type anyway (and the ones from STL are).
Could you please elaborate?
You shouldn't do it for the same reasons you shouldn't derive from
std::string or std::vector. There are always exceptions of course and
maybe yours applies but the general rational is this:

There are no protected members in std::set::const_iterator that you need
access to, there is (should be) no context where a function takes a
std::set::const_iterator* as a parameter and you need to wrap the
const_iterator to intercept calls to it, and there are no virtual
member-functions in std::set::const_iterator for you to override.
Therefore, there is no reason to derive from std::set::const_iterator.

The stuff you put in the derived class will likely work with any const
iterator that has the same semantics as std::set::const_iterator, and
you are creating an artificial limitation by deriving from
std::set::const_iterator.

--
There are two things that simply cannot be doubted, logic and perception.
Doubt those, and you no longer have anyone to discuss your doubts with,
nor any ability to discuss them.
Sep 24 '06 #7
"T.A." <to*************@gmail.comwrote:
So I guess it is true that only thing to inherit from safely are base
iterator classes (in this case probably the best one would be
std::random_access_iterator) and reimplemetation of whole my_iterator
interface.
Maybe an example will help:

/*
* dat_fibonacci.h
*
* Created by Daniel on 1/30/06.
* Copyright 2006 Daniel Tartaglia. All rights reserved.
*
*/

#pragma once

#include <iterator>

namespace dat {

class fibonacci: public std::iterator< std::forward_iterator_tag, int >
{
int prev_value, value, max;
public:
fibonacci(): prev_value(0), value(0), max(0) { }
explicit fibonacci(int m): prev_value(0), value(1), max(m) { }
const int operator*() const { return value; }
fibonacci& operator++() {
int tmp = value;
value += prev_value;
prev_value = tmp;
return *this;
}
fibonacci operator++(int) {
fibonacci tmp(*this);
++(*this);
return tmp;
}
friend bool operator==(const fibonacci& lhs, const fibonacci& rhs) {
bool result = false;
if ( lhs.value == 0 && rhs.value == 0 ) result = true;
else if ( rhs.value == 0 && !( lhs.value < lhs.max ) )
result = true;
else if ( lhs.value == 0 && !( rhs.value < rhs.max ) )
result = true;
else if ( lhs.prev_value == rhs.prev_value &&
lhs.value == rhs.value && lhs.max == rhs.max )
result = true;
return result;
}
};

bool operator!=(const fibonacci& lhs, const fibonacci& rhs) {
return !(lhs == rhs);
}

}

--
There are two things that simply cannot be doubted, logic and perception.
Doubt those, and you no longer have anyone to discuss your doubts with,
nor any ability to discuss them.
Sep 24 '06 #8
Daniel T. wrote:
>
There are no protected members in std::set::const_iterator that you need
access to, there is (should be) no context where a function takes a
std::set::const_iterator* as a parameter and you need to wrap the
const_iterator to intercept calls to it, and there are no virtual
member-functions in std::set::const_iterator for you to override.
Therefore, there is no reason to derive from std::set::const_iterator.
There is a very good reason for deriving from std::set::const_iterator:
when you do, you don't need to reimplement the member functions that it
provides. Except, of course, for the ones where you want different behavior.
The stuff you put in the derived class will likely work with any const
iterator that has the same semantics as std::set::const_iterator, and
you are creating an artificial limitation by deriving from
std::set::const_iterator.
Maybe, but that sounds like overdesign. If the current application works
with set instances and needs modified iterators, then deriving from
set::const_iterator is perfectly appropriate. If some future application
needs something similar but more general, that's the time to add the
generality.

--

-- Pete

Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." For more information about this book, see
www.petebecker.com/tr1book.
Sep 24 '06 #9
Pete Becker wrote:
Daniel T. wrote:

There are no protected members in std::set::const_iterator that you need
access to, there is (should be) no context where a function takes a
std::set::const_iterator* as a parameter and you need to wrap the
const_iterator to intercept calls to it, and there are no virtual
member-functions in std::set::const_iterator for you to override.
Therefore, there is no reason to derive from std::set::const_iterator.

There is a very good reason for deriving from std::set::const_iterator:
when you do, you don't need to reimplement the member functions that it
provides. Except, of course, for the ones where you want different behavior.
Except for the fact that there are no member functions that a
std::set::const_iterator type is required to provide. The Standard
requires only that the const_iterator type support certain operations -
there is no requirement concerning how those operations are to be
implemented or even any requirement that the library must implement
them itself. A built-in type that supported the necessary built-in
operations with built-in operators would qualify as well. So any class
derived from set's const_iterator cannot be sure of the interface it
will actually be inheriting, nor can it be sure that inheritance is
even an option: after all, set's const_iterator may be a typedef for a
built-in type, such as a pointer.

The stuff you put in the derived class will likely work with any const
iterator that has the same semantics as std::set::const_iterator, and
you are creating an artificial limitation by deriving from
std::set::const_iterator.

Maybe, but that sounds like overdesign. If the current application works
with set instances and needs modified iterators, then deriving from
set::const_iterator is perfectly appropriate. If some future application
needs something similar but more general, that's the time to add the
generality.
The sensible design is to wrap the iterator in a template class, and
implement the handful of operations the program actually will use as
class methods that (in the default case) simply perform the same,
corresponding operation on the wrapped iterator instance.

Any design that involves deriving from std::set::const_iterator is
necessarily a non-portable and fragile implementation based entirely on
the inner workings of a particular implementation of std::set written
by someone else. In other words, there is no solid foundation. Future
revisions of the same Standard library (or even debug or non-debug
builds of the same library) could well render the design's current
assumptions false. Worse, there is no assurance that a design broken in
this way would be reported as an error. Instead the program may still
compile, but when run, would fail silently.

Greg

Sep 24 '06 #10
Pete Becker wrote:
Daniel T. wrote:
>>
There are no protected members in std::set::const_iterator that you need
access to, there is (should be) no context where a function takes a
std::set::const_iterator* as a parameter and you need to wrap the
const_iterator to intercept calls to it, and there are no virtual
member-functions in std::set::const_iterator for you to override.
Therefore, there is no reason to derive from std::set::const_iterator.

There is a very good reason for deriving from std::set::const_iterator:
when you do, you don't need to reimplement the member functions that it
provides. Except, of course, for the ones where you want different
behavior.
[snip]

That is exactly what I thought. And I still think that the standard reasons
usually given to not inherit from classes without protected members and
virtual functions are bogus in this case.

However, there are some difficulties that provide independent good reasons
to be cautious about this inheritance. Consider the following container
implementation where the iterator is derived lazily:

#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>

template < typename T >
struct ptr_vector {

typedef T value_type;
typedef T* pointer;
typedef T& reference;
typedef typename std::vector<T*>::size_type size_type;

private:

typedef std::vector<T*ptr_vect;
typedef typename ptr_vect::iterator ptr_iter;

ptr_vect data;

public:

struct iterator : public ptr_iter {

typedef T value_type;

iterator ( ptr_iter i )
: ptr_iter ( i )
{}

pointer operator-() const {
return ( ptr_iter::operator*() );
}

reference operator* () const {
return ( * ptr_iter::operator*() );
}

};

void push_back ( value_type const & t ) {
data.push_back( new value_type ( t ) );
}

void pop_back ( void ) {
delete data.back();
}

iterator begin ( void ) {
return ( data.begin() );
}

iterator end ( void ) {
return ( data.end() );
}
// some clutter added to handle copies correctly:
// not important for the example at hand.

ptr_vector ( void )
: data ()
{}

ptr_vector ( ptr_vector const & other )
{
data.reserve( other.size() );
for ( size_type i = 0; i < other.size(); ++i ) {
push_back( new value_type ( other[i] ) );
}
}

~ptr_vector ( void ) {
for ( size_type i = 0; i < this->size(); ++i ) {
delete ( data[i] );
}
}

ptr_vector& operator= ( ptr_vector const & other ) {
ptr_vector dummy ( other );
std::swap( data, dummy.data );
return ( *this );
}

size_type size ( void ) const {
return ( data.size() );
}

reference operator[] ( size_type i ) {
return ( *( data[i] ) );
}

};

template < typename Iter >
void bubble_sort ( Iter from, Iter to ) {
for ( Iter low = from; low != to; ++ low ) {
for ( Iter high = low; high != to; ++ high ) {
if ( std::less< typename Iter::value_type >()( *high, *low ) ) {
std::iter_swap( low, high );
}
}
}
}
int main ( void ) {
ptr_vector< int v;
v.push_back( 20 );
v.push_back( 30 );
v.push_back( 10 );
std::copy( v.begin(), v.end(),
std::ostream_iterator<int>( std::cout, " " ) );
std::cout << '\n';
bubble_sort( v.begin(), v.end() );
std::copy( v.begin(), v.end(),
std::ostream_iterator<int>( std::cout, " " ) );
std::cout << '\n';
bubble_sort( v.begin()++, v.end()-- );
std::copy( v.begin(), v.end(),
std::ostream_iterator<int>( std::cout, " " ) );
std::cout << '\n';
}

On my machine, this prints:

20 30 10
10 20 30
10 30 20
The first call to bubble_sort is fine. The second one, however, is all
messed up because postfix operators return iterators of the wrong type.
Thus, a never thought of instance of bubble_sort() is used, and second call
orders the objects by address. So, in the end, you would need to wrap all
method that return std::vector<T*>iterator in the iterator class anyway.
Then, inheritance is not really much less code compared to composition (at
least in this case), unless you are headed for strange bugs.
Best

Kai-Uwe Bux
Sep 24 '06 #11
Greg wrote:
Pete Becker wrote:
>Daniel T. wrote:
>>There are no protected members in std::set::const_iterator that you need
access to, there is (should be) no context where a function takes a
std::set::const_iterator* as a parameter and you need to wrap the
const_iterator to intercept calls to it, and there are no virtual
member-functions in std::set::const_iterator for you to override.
Therefore, there is no reason to derive from std::set::const_iterator.
There is a very good reason for deriving from std::set::const_iterator:
when you do, you don't need to reimplement the member functions that it
provides. Except, of course, for the ones where you want different behavior.

Except for the fact that there are no member functions that a
std::set::const_iterator type is required to provide. The Standard
requires only that the const_iterator type support certain operations -
there is no requirement concerning how those operations are to be
implemented or even any requirement that the library must implement
them itself.
Sigh. Okay, I shouldn't have used the term "member functions" when I
meant "operations."
A built-in type that supported the necessary built-in
operations with built-in operators would qualify as well. So any class
derived from set's const_iterator cannot be sure of the interface it
will actually be inheriting, nor can it be sure that inheritance is
even an option: after all, set's const_iterator may be a typedef for a
built-in type, such as a pointer.
const_iterator for a set cannot be a pointer, nor any other builtin
type. Operators on builtin types don't meet the requirements for an
iterator into a set.
>
>>The stuff you put in the derived class will likely work with any const
iterator that has the same semantics as std::set::const_iterator, and
you are creating an artificial limitation by deriving from
std::set::const_iterator.
Maybe, but that sounds like overdesign. If the current application works
with set instances and needs modified iterators, then deriving from
set::const_iterator is perfectly appropriate. If some future application
needs something similar but more general, that's the time to add the
generality.

The sensible design is to wrap the iterator in a template class, and
implement the handful of operations the program actually will use as
class methods that (in the default case) simply perform the same,
corresponding operation on the wrapped iterator instance.
That's one sensible (over)design, but it's not the only possibility.
Any design that involves deriving from std::set::const_iterator is
necessarily a non-portable and fragile implementation based entirely on
the inner workings of a particular implementation of std::set written
by someone else.
No, it's not. set::const_iterator has a rquired set of operations that
are well specified.
In other words, there is no solid foundation. Future
revisions of the same Standard library (or even debug or non-debug
builds of the same library) could well render the design's current
assumptions false.
Only if you implement it that way.

--

-- Pete

Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." For more information about this book, see
www.petebecker.com/tr1book.
Sep 24 '06 #12
Kai-Uwe Bux wrote:
>
The first call to bubble_sort is fine. The second one, however, is all
messed up because postfix operators return iterators of the wrong type.
Thus, a never thought of instance of bubble_sort() is used, and second call
orders the objects by address. So, in the end, you would need to wrap all
method that return std::vector<T*>iterator in the iterator class anyway.
Not all. Increment and decrement, certainly. But operator* and
operator-should be fine, for example.
Then, inheritance is not really much less code compared to composition (at
least in this case), unless you are headed for strange bugs.
I didn't say anything about how much code was involved. I objected to
the categorical assertion that you shouldn't do it. Far too many
programmers write code based on slogans instead of facts and analysis.

--

-- Pete

Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." For more information about this book, see
www.petebecker.com/tr1book.
Sep 24 '06 #13
Pete Becker <pe********@acm.orgwrote:
I didn't say anything about how much code was involved. I objected to
the categorical assertion that you shouldn't do it. Far too many
programmers write code based on slogans instead of facts and analysis.
Sorry Pete, it wasn't my intention to make a categorical assertion,
that's why I prefaced it with "there are exceptions."

--
There are two things that simply cannot be doubted, logic and perception.
Doubt those, and you no longer*have anyone to discuss your doubts with,
nor any ability to discuss them.
Sep 24 '06 #14
Pete Becker wrote:
Kai-Uwe Bux wrote:
>>
The first call to bubble_sort is fine. The second one, however, is all
messed up because postfix operators return iterators of the wrong type.
Thus, a never thought of instance of bubble_sort() is used, and second
call orders the objects by address. So, in the end, you would need to
wrap all method that return std::vector<T*>iterator in the iterator class
anyway.

Not all. Increment and decrement, certainly. But operator* and
operator-should be fine, for example.
Do those return std::vector<T*>::iterator? I thought that would yield a
recursion loop. Anyway, those were the ones where I wanted different
behavior anyway.

>Then, inheritance is not really much less code compared to composition
(at least in this case), unless you are headed for strange bugs.

I didn't say anything about how much code was involved.
Well you made it sound that way:
>There is a very good reason for deriving from std::set::const_iterator:
when you do, you don't need to reimplement the member functions that it
provides. Except, of course, for the ones where you want different
behavior.
I read that to mean: you safe some t development time by reusing methods
through inheritance so that you don't have to include the boilerplate
forwarding code that comes with composition. Sorry, if I interpreted you to
narrowly.

I objected to
the categorical assertion that you shouldn't do it. Far too many
programmers write code based on slogans instead of facts and analysis.
I don't know what too many programmers do. But I wholeheartly agree that
most categorial dos and don'ts are somewhat bogus.
Best

Kai-Uwe Bux
Sep 24 '06 #15
Kai-Uwe Bux wrote:
Pete Becker wrote:
>Not all. Increment and decrement, certainly. But operator* and
operator-should be fine, for example.

Do those return std::vector<T*>::iterator? I thought that would yield a
recursion loop. Anyway, those were the ones where I wanted different
behavior anyway.
operator* returns T& and operator-returns T*.

--

-- Pete

Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." For more information about this book, see
www.petebecker.com/tr1book.
Sep 24 '06 #16
Pete Becker wrote:
Greg wrote:
[snip]
>Any design that involves deriving from std::set::const_iterator is
necessarily a non-portable and fragile implementation based entirely on
the inner workings of a particular implementation of std::set written
by someone else.

No, it's not. set::const_iterator has a rquired set of operations that
are well specified.
But that does not imply you can inherit meaningfully. (See below)

>In other words, there is no solid foundation. Future
revisions of the same Standard library (or even debug or non-debug
builds of the same library) could well render the design's current
assumptions false.

Only if you implement it that way.
I assume that "it" refers to "design" and not to "Standard library".

Hm, would it be possible for a standard compliant implementation of
std::set, to proceed as follows and effectively break all classes derived
from set::iterator:

template < typename T >
struct set {

class iterator;
class const_iterator;

// more stuff

private:

class blocker {

friend class iterator;
friend class const_iterator;

blocker ( void ) {};
blocker ( blocker const & ) {};

};

public:

class iterator : public virtual blocker {
public:

iterator ( void ) {}

// more stuff

};

// more stuff

};
If my library vendor, along with the next revision, decides to put this
blocker code in, any attempt like the following will result in compiler
errors:

struct my_iter : public set<int>::iterator {

// some stuff

};
int main ( void ) {
my_iter i;
}
Would the standard allow me to prove my library vendor wrong? As far as I
can see, std::set::iterator is an implementation defined type that makes no
guarantees about derivability. But I might be missing a provision. If there
is no guarantee that set::iterator does not use a nasty trick like the
above, then Greg is essentially correct: any derivation from set::iterator
relies on the inner workings of a particular implementation.
Best

Kai-Uwe Bux
Sep 24 '06 #17
Kai-Uwe Bux wrote:
Pete Becker wrote:
>Greg wrote:
[snip]
>>Any design that involves deriving from std::set::const_iterator is
necessarily a non-portable and fragile implementation based entirely on
the inner workings of a particular implementation of std::set written
by someone else.
No, it's not. set::const_iterator has a rquired set of operations that
are well specified.

But that does not imply you can inherit meaningfully. (See below)
Sure it does.
>
>>In other words, there is no solid foundation. Future
revisions of the same Standard library (or even debug or non-debug
builds of the same library) could well render the design's current
assumptions false.
Only if you implement it that way.

I assume that "it" refers to "design" and not to "Standard library".
Yes, indeed.
Hm, would it be possible for a standard compliant implementation of
std::set, to proceed as follows and effectively break all classes derived
from set::iterator:
Maybe. Why would anyone do that?
>
Would the standard allow me to prove my library vendor wrong? As far as I
can see, std::set::iterator is an implementation defined type that makes no
guarantees about derivability. But I might be missing a provision. If there
is no guarantee that set::iterator does not use a nasty trick like the
above, then Greg is essentially correct: any derivation from set::iterator
relies on the inner workings of a particular implementation.
No, not at all. It relies on the assumption that library implementors
don't go out of their way to screw their users.

Portability isn't about being bulletproof. It's about writing code that
has a good chance of surviving changes. This sort of thing isn't high on
my list of worries.

--

-- Pete

Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." For more information about this book, see
www.petebecker.com/tr1book.
Sep 24 '06 #18
Pete Becker wrote:
Kai-Uwe Bux wrote:
>Pete Becker wrote:
>>Greg wrote:
[snip]
>>>Any design that involves deriving from std::set::const_iterator is
necessarily a non-portable and fragile implementation based entirely on
the inner workings of a particular implementation of std::set written
by someone else.
No, it's not. set::const_iterator has a rquired set of operations that
are well specified.

But that does not imply you can inherit meaningfully. (See below)

Sure it does.
We must have slightly different understandings of what "does not imply"
means. I just meant that a standard compliant library implementation is
conceivable where set::const_iterator supports all required operations, yet
still would not support derivation in any meaningful way. The code I
sketched strongly indicates that such an implementation is possible. What
is the meaning of "does not imply" that you used to arrive at the opposite
conclusion?

>>>In other words, there is no solid foundation. Future
revisions of the same Standard library (or even debug or non-debug
builds of the same library) could well render the design's current
assumptions false.
Only if you implement it that way.

I assume that "it" refers to "design" and not to "Standard library".

Yes, indeed.
>Hm, would it be possible for a standard compliant implementation of
std::set, to proceed as follows and effectively break all classes derived
from set::iterator:

Maybe. Why would anyone do that?
One use would be to check code for strict standard compliance. I certainly
would love to have a compiler/library that allowed me to flag all instances
where my code relies on common but not mandated behavior (e.g., it would be
great to have a library with headers that strive to only provide what the
standard puts within that header).

>Would the standard allow me to prove my library vendor wrong? As far as I
can see, std::set::iterator is an implementation defined type that makes
no guarantees about derivability. But I might be missing a provision. If
there is no guarantee that set::iterator does not use a nasty trick like
the above, then Greg is essentially correct: any derivation from
set::iterator relies on the inner workings of a particular
implementation.

No, not at all. It relies on the assumption that library implementors
don't go out of their way to screw their users.

Portability isn't about being bulletproof. It's about writing code that
has a good chance of surviving changes. This sort of thing isn't high on
my list of worries.
Portability is, among other things, about not relying on behavior that is
not guaranteed by the standard. I recall that some code that used to work
perfectly fine broke when my standard library incorporated concept checks
(however, my memory is notoriously unreliable and could be making this up).
At that point, I learned that the standard requires complete types for the
template arguments in many places even in cases where there there are
natural implementations that would not need that. I think, the assumption
that you can meaningfully derive from set::iterator is not that different.
When you do it, you are writing code that is not guaranteed to work as
expected by the standard. That, in itself, is not a reason to never do it.
But it sure is a drawback. More important: that a certain idiom relies on
common but not mandated behavior is a good prima facie reason to warn
agains said idiom.
Best

Kai-Uwe Bux
Sep 24 '06 #19
Kai-Uwe Bux wrote:
Pete Becker wrote:
>>
Portability isn't about being bulletproof. It's about writing code that
has a good chance of surviving changes. This sort of thing isn't high on
my list of worries.

Portability is, among other things, about not relying on behavior that is
not guaranteed by the standard.
That is one aspect of portability, but it must be applied sensibly.
I recall that some code that used to work
perfectly fine broke when my standard library incorporated concept checks
(however, my memory is notoriously unreliable and could be making this up).
At that point, I learned that the standard requires complete types for the
template arguments in many places even in cases where there there are
natural implementations that would not need that. I think, the assumption
that you can meaningfully derive from set::iterator is not that different.
On the contrary: it is quite different. The C++ specification explicitly
says that you cannot use incomplete types in that context, so you
violated an express prohibition. There is no such prohibition on
deriving from std::const_iterator, and no reasonable implementation will
prevent that. It's hard enough to write library code that gets the
actual requirements right. Adding made up ones is simply wasting time.

--

-- Pete

Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." For more information about this book, see
www.petebecker.com/tr1book.
Sep 24 '06 #20
Pete Becker wrote:
Kai-Uwe Bux wrote:
[snip]
>I recall that some code that used to work
perfectly fine broke when my standard library incorporated concept checks
(however, my memory is notoriously unreliable and could be making this
up). At that point, I learned that the standard requires complete types
for the template arguments in many places even in cases where there there
are natural implementations that would not need that. I think, the
assumption that you can meaningfully derive from set::iterator is not
that different.

On the contrary: it is quite different. The C++ specification explicitly
says that you cannot use incomplete types in that context, so you
violated an express prohibition. There is no such prohibition on
deriving from std::const_iterator, and no reasonable implementation will
prevent that.
The standard explictly marks the type std::set::const_iterator as
implementation_defined. The cases may not be exactly parallel, but relying
on being able to derive from set::const_iterator is formally implementation
defined behavior.
Best

Kai-Uwe Bux
Sep 24 '06 #21
Kai-Uwe Bux wrote:
Pete Becker wrote:
The standard explictly marks the type std::set::const_iterator as
implementation_defined. The cases may not be exactly parallel, but relying
on being able to derive from set::const_iterator is formally implementation
defined behavior.
Again: it is permissible for an implementation to make things difficult
for its users by making it hard or impossible to derive from various
types. It is also permissible to not do that, and that's the approach
taken by every implementation I'm aware of. Blocking inheritance means
writing and maintaining extra code for no clear benefit. That's not high
on my list of things to worry about.

--

-- Pete

Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." For more information about this book, see
www.petebecker.com/tr1book.
Sep 25 '06 #22

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

Similar topics

6
by: greg | last post by:
Hello all, I havent used STL containers much, as I am used to MFC containers/classes always ..The differences that I could see is iterators and algorithms. The algorithms providing some basic...
2
by: Rex_chaos | last post by:
Hi all, I am writing my own container and need an iterator. I am hesitating if I should my iterator should inherited from std::iterator or just write my own one. Please give me an idea. BTW,...
8
by: Generic Usenet Account | last post by:
To settle the dispute regarding what happens when an "erase" method is invoked on an STL container (i.e. whether the element is merely removed from the container or whether it also gets deleted in...
5
by: Ernst Murnleitner | last post by:
Hello, is it possible to derive from std::vector and derive also its iterator? If I do it like in the example below, I get a problem when I need the begin of the vector: begin() returns the...
4
by: lwickland | last post by:
Non-visual C# objects on a webpage are not marked as "safe for scripting" I'm developing .NET components in C# which are used as ActiveX-style controls on web pages that are displayed inside a...
2
by: Lorenzo Castelli | last post by:
This is an old problem of mine. Basically I have an abstract base class which represents a generic iterator over a collection of elements, and various derived classes that implement the...
2
by: Christoph Heindl | last post by:
Hi, I'm currently struggling with a design decision. One of my classes (named Attributable) has a protected member of type std::list<StrongReference<Attribute> > Basically the list has...
1
by: David Bilsby | last post by:
All Apologies for cross posing this but I am not sure if this is a VC 8 STL bug or simply an invalid use of the iterator. I have a PCI card access class which basically abstracts a third party...
3
by: andreas.zetterstrom | last post by:
I'm implementing some different c++ classes which I want to be thread safe. All these classes contain lists or arrays of some kind. I'm using protected sections to make them thread safe. The...
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....

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.