 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Scott Meyers
Guest
|
 Posted: Thu Jan 27, 2005 9:08 pm Post subject: Specializing an algorithm for deque iterators |
 |
|
My brain must be running on empty tonight, because I'll be darned if I can
figure out how to do something I'm sure is easy. I want to write a STLish
algorithm that behaves specially for deques. My first attempt was to
overload the template for deque iterators, but it won't work, because
template argument deduction won't work for nested types:
template<typename It, typename Func>
void applyFunc(It begin, It end, Func f)
{
std::cout << "General versionn";
}
template
void applyFunc(typename std::deque<T>::iterator begin, // the nested
typename std::deque<T>::iterator end, // iterator
Func f) // type is
{ // never
std::cout << "Special versionn"; // deduced
}
I was reminded of this when I looked up a thread on essentially the same
topic from nearly four years ago ([url]http://tinyurl.com/4she6)[/url]. So, among
other things, I tried the approach advocated by Brian McNamara at the end
of that thread: I had the function template forward the call to a class
template, using partial specialization to get the behavior I wanted:
template
struct Helper {
static void applyFunc2(It begin, It end, Func f)
{
std::cout << "General versionn";
}
};
template
struct Helper<typename std::deque {
static void applyFunc2(typename std::deque<T>::iterator begin,
typename std::deque<T>::iterator end,
Func f)
{
std::cout << "Special versionn";
}
};
template
void applyFunc2(It begin, It end, Func f)
{
Helper<It, Func>::applyFunc2(begin, end, f);
}
But no matter how I call applyFunc2, I get the general version, not the
special version. How can I write a function template that will do
something special when passed a pair of deque iterators?
Thanks,
Scott
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
Pete Becker
Guest
|
| Posted: Fri Jan 28, 2005 12:35 am Post subject: Re: Specializing an algorithm for deque iterators |
|
|
Scott Meyers wrote:
| Quote: | But no matter how I call applyFunc2, I get the general version, not the
special version. How can I write a function template that will do
something special when passed a pair of deque iterators?
|
You're trying to go the wrong way down a one-way street. There is no
such thing as a pair of deque iterators. A pair of iterators designates
a sequence of values. Algorithms don't know or care what the source of
their iterators is.
If you care about the origin of your sequence of values you're not
dealing with iterators, but with containers. Write code that takes
containers.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Ian McCulloch
Guest
|
| Posted: Fri Jan 28, 2005 12:38 am Post subject: Re: Specializing an algorithm for deque iterators |
|
|
Scott Meyers wrote:
| Quote: | My brain must be running on empty tonight, because I'll be darned if I can
figure out how to do something I'm sure is easy. I want to write a STLish
algorithm that behaves specially for deques. My first attempt was to
overload the template for deque iterators, but it won't work, because
template argument deduction won't work for nested types:
template<typename It, typename Func
void applyFunc(It begin, It end, Func f)
{
std::cout << "General versionn";
}
template
void applyFunc(typename std::deque
typename std::deque<T>::iterator end, // iterator
Func f) // type is
{ // never
std::cout << "Special versionn"; // deduced
}
I was reminded of this when I looked up a thread on essentially the same
topic from nearly four years ago ([url]http://tinyurl.com/4she6)[/url]. So, among
other things, I tried the approach advocated by Brian McNamara at the end
of that thread: I had the function template forward the call to a class
template, using partial specialization to get the behavior I wanted:
template
struct Helper {
static void applyFunc2(It begin, It end, Func f)
{
std::cout << "General versionn";
}
};
template
struct Helper {
static void applyFunc2(typename std::deque<T>::iterator begin,
typename std::deque<T>::iterator end,
Func f)
{
std::cout << "Special versionn";
}
};
|
I don't think that can work, it isn't a partial specialization of Helper.
[...]
How about this:
#include
#include <boost/type_traits.hpp>
#include <iostream>
#include <deque>
#include <vector>
template<typename It, typename Func, typename Enable = void>
struct Helper
{
static void applyFunc2(It begin, It end, Func f)
{
std::cout << "General versionn";
}
};
template
struct Helper<It, Func, typename boost::enable_if<
boost::is_same<
It,
typename std::deque
std::iterator_traits::iterator
static void applyFunc2(It begin, It end, Func f)
{
std::cout << "Deque versionn";
}
};
template
void applyFunc2(It begin, It end, Func f)
{
Helper<It, Func>::applyFunc2(begin, end, f);
}
int main()
{
std::deque<int> foo(10);
applyFunc2(foo.begin(), foo.end(), 0);
std::vector<int> bar(10);
applyFunc2(bar.begin(), bar.end(), 0);
}
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Thomas Maeder
Guest
|
| Posted: Fri Jan 28, 2005 12:41 am Post subject: Re: Specializing an algorithm for deque iterators |
|
|
Scott Meyers <smeyers (AT) aristeia (DOT) com> writes:
| Quote: | But no matter how I call applyFunc2, I get the general version, not the
special version. How can I write a function template that will do
something special when passed a pair of deque iterators?
|
This works if sizeof(char)<sizeof(deque iterator). I think that it can
easily been made to work without that condition.
Y::makeIt() is there because iterators don't have to be
default-constructible, so we can't simply write
sizeof(Xsizeof(char)
#include <deque>
#include <vector>
#include <iostream>
#include <ostream>
template<typename It, bool isDequeIterator>
struct Helper {
static void applyFunc2(It begin)
{
std::cout << "General versionn";
}
};
template
struct Helper<It,true> {
static void applyFunc2(It begin)
{
std::cout << "Special versionn";
}
};
template
struct X : public std::deque<T>
{
using std::deque<T>::erase;
char erase(...);
};
template <typename It>
struct Y
{
typedef typename std::iterator_traits<It>::value_type value_type;
static It makeIt();
enum
{
ItIsDequeIterator = sizeof(X<value_type>().erase(makeIt()))>sizeof(char)
};
};
template<typename It>
void applyFunc2(It begin)
{
Helper<It,Y::applyFunc2(begin);
}
int main()
{
char const c(' ');
applyFunc2(&c);
std::vector<double> v;
applyFunc2(v.begin());
std::deque<int> d;
applyFunc2(d.begin());
}
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Daniel Frey
Guest
|
| Posted: Fri Jan 28, 2005 2:05 am Post subject: Re: Specializing an algorithm for deque iterators |
|
|
Scott Meyers wrote:
| Quote: | My brain must be running on empty tonight, because I'll be darned if I can
figure out how to do something I'm sure is easy. I want to write a STLish
algorithm that behaves specially for deques. My first attempt was to
overload the template for deque iterators, but it won't work, because
template argument deduction won't work for nested types:
|
Easy is relativ. At least with typeof/decltype and assuming that the
deque's iterators are UDTs not shared with other containers, it think
it's easy:
#include <deque>
#include <vector>
#include <iostream>
using namespace std;
#include <boost/type_traits/is_same.hpp>
#include <boost/utility/enable_if.hpp>
template< typename T > struct dereference
{
static T t();
typedef __typeof__( *t() ) type;
};
template< typename It > struct is_deque_iterator
{
typedef typename dereference< It >::type T;
typedef typename deque< T >::iterator DequeIt;
typedef typename deque< T >::const_iterator DequeConstIt;
enum {
value = boost::is_same< It, DequeIt >::value ||
boost::is_same< It, DequeConstIt >::value
};
};
template< typename It >
typename boost::disable_if< is_deque_iterator< It > >::type
algorithm( It b, It e )
{
cout << "No deque  " << endl;
}
template< typename It >
typename boost::enable_if< is_deque_iterator< It > >::type
algorithm( It b, It e )
{
cout << "It's a deque!" << endl;
}
int main()
{
vector< int > v;
deque< int > d;
algorithm( v.begin(), v.end() );
algorithm( d.begin(), d.end() );
}
Now you just have to decide if you can accept the use of typeof and if
the assumption on the iterator types holds for your use case. :)
Regards, Daniel
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Daniel Frey
Guest
|
| Posted: Fri Jan 28, 2005 11:20 am Post subject: Re: Specializing an algorithm for deque iterators |
|
|
Daniel Frey wrote:
| Quote: | template< typename T > struct dereference
{
static T t();
typedef __typeof__( *t() ) type;
};
|
OK, I missed iterator_traits (as suggested by Ian).
The next thing I tried was to generalize the code a bit. Besides the
assumptions about non-shared iterator types for the containers, I wonder
if my code is now legal. Consider:
#include <deque>
#include <vector>
#include <iostream>
#include <iterator>
#include <boost/type_traits/is_same.hpp>
#include <boost/utility/enable_if.hpp>
// This is the line in question:
template< typename It, template< typename > class Container >
struct is_iterator_of
{
typedef typename std::iterator_traits< It >::value_type T;
enum {
value = boost::is_same< It, typename Container< T >::iterator
| Quote: | ::value ||
boost::is_same< It, typename Container< T >::const_iterator
::value
}; |
};
template< typename It >
typename boost::disable_if< is_iterator_of< It, std::deque > >::type
algorithm( It )
{
std::cout << "Generic" << std::endl;
}
template< typename It >
typename boost::enable_if< is_iterator_of< It, std::deque > >::type
algorithm( It )
{
std::cout << "Deque version!" << std::endl;
}
int main()
{
std::vector< int > v;
std::deque< int > d;
algorithm( v.end() );
algorithm( d.end() );
}
The problem I have is the template template parameter. A deque has a
second parameter, an Allocator. So I wonder why the standard actually
cares about the template parameter list of a template template
parameter. Is there any reason why a looser syntax won't work? E.g.
reusing the ellipse for the syntax:
template< typename It, template<...> typename Container >
//etc.
I mean, the idea is that the use of the template template parameter will
limit the type, so why do I have to provide the parameter list
explicitly? Any inside from the language experts? TIA.
Regards, Daniel
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
David Abrahams
Guest
|
| Posted: Fri Jan 28, 2005 11:25 am Post subject: Re: Specializing an algorithm for deque iterators |
|
|
Thomas Maeder <maeder (AT) glue (DOT) ch> writes:
| Quote: | Scott Meyers <smeyers (AT) aristeia (DOT) com> writes:
But no matter how I call applyFunc2, I get the general version, not the
special version. How can I write a function template that will do
something special when passed a pair of deque iterators?
This works if sizeof(char)
easily been made to work without that condition.
|
It's true that the condition can be eliminated, and fairly easily.
But what Pete Becker said is even truer. Trying to get special
behavior for deque iterators is anti-generic and probably wrong. The
capabilities of deque iterators are no different from those of any
other random-access iterator. What could you possibly need to do
differently if the iterators happen to come from a std::vector or are
just pointers into some array on the stack?
--
Dave Abrahams
Boost Consulting
www.boost-consulting.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
White Wolf
Guest
|
| Posted: Fri Jan 28, 2005 11:28 am Post subject: Re: Specializing an algorithm for deque iterators |
|
|
Pete Becker wrote:
| Quote: | Scott Meyers wrote:
But no matter how I call applyFunc2, I get the general version, not the
special version. How can I write a function template that will do
something special when passed a pair of deque iterators?
You're trying to go the wrong way down a one-way street.
|
I guess Pete you have made two steps in one. IIRC first you ask "Why do you
want to do that" and only then you straighten the other party out. ;-)
| Quote: | There is no such thing as a pair of deque iterators.
|
Hm. So two iterators denoting a range inside a deque are not a pair of
deque iterators? Forget it, it was only rhetorical.
| Quote: | A pair of iterators designates a sequence of values.
Algorithms don't know or care what the source of
their iterators is.
|
Are you saying they don't care or that they should never care? I think it
is an important distinction. I say that I could not name any algorithm
right now which does (need to know where the iterator range came from), but
I would also have very hard time to prove that no algorithm should ever need
to know it.
| Quote: | If you care about the origin of your sequence of values you're not
dealing with iterators, but with containers. Write code that takes
containers.
|
While I can follow your reasoning I would like to mention that people on the
other end of the food chain (users of the language) cannot just toss a sort
member into std::list if they need one. So they may need to implement
things outside. If there is (or can be) anything like that, which works on
an iterator range and might have different ways depending on the container I
do not know. Should the iterator categories be enough? Always?
I do not know what functionality Scott is looking for, but I for one would
not rule out that his question is a legit one before knowing the reason why
he has asked it.
And as it happens, with iterators (standard conforming iterators), it can be
done. I hope Scott will tell the reson why he wanted to do it.
--
WW aka Attila
:::
The man who does not read good books has no advantage over the man who
cannot read them. -- Mark Twain
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
White Wolf
Guest
|
| Posted: Fri Jan 28, 2005 11:30 am Post subject: Re: Specializing an algorithm for deque iterators |
|
|
Scott Meyers wrote:
[SNIP]
| Quote: | template<typename It, typename Func
struct Helper {
static void applyFunc2(It begin, It end, Func f)
{
std::cout << "General versionn";
}
};
template
struct Helper {
static void applyFunc2(typename std::deque<T>::iterator begin,
typename std::deque<T>::iterator end,
Func f)
{
std::cout << "Special versionn";
}
};
template
void applyFunc2(It begin, It end, Func f)
{
Helper
}
But no matter how I call applyFunc2, I get the general version, not the
special version. How can I write a function template that will do
something special when passed a pair of deque iterators?
|
I have tried, really. But all I was able to come up with (in two hours of
reading The template book and Simons' collected) was that when the compiler
attempts to find a matching class template partial specialization it uses
*exactly* the same deduction rules as for your first attempt (when you have
used function templates). I copy here what makes me think that. So deep
breath, and...
In
'14.5.4.1 Matching of class template partial specializations'
[temp.class.spec.match]
Simon says:
1 When a class template is used in a context {blablabla}. This is done by
matching the template arguments of the class template specialization with
the template argument lists of the partial specializations.
— If exactly one matching specialization is found, the instantiation is
generated from that specialization.
{The above is what you want}
— If more than one matching specialization is found, the partial order rules
(14.5.4.2) are used to determine whether one of the specializations is more
specialized than the others. If none of the specializations is more
specialized than all of the other matching specializations, then the use of
the class template is ambiguous and the program is illformed.
{You have only one partial specialization, so the above does not apply to
you}
— If no matches are found, the instantiation is generated from the primary
template.
{This is what you get. }
2 A partial specialization matches a given actual template argument list if
the template arguments of the partial specialization can be deduced from the
actual template argument list (14.8.2).
{And the above is what makes me think, that resistance is futile, or IOW Ohm
I God!}
The title of 14.8.2 is: "Template argument deduction", which does not sound
bad at all until one realizes that 14.8 is "Function template
specializations"
So (AFAIU) C++ tries to use exactly the same rules to find your class
template partial specialization which have failed to find your function
template: the ones which do not match member types. So it seems that
there should be another trick somewhere in the box to get that one work. :-(
If I misunderstood something I hope someone will let me know.
////////////
I have made the example work. Do not ask me why it works. I have no idea,
I had the gut feeling that it should and it did. See the code. What I did
is veeery simple (as its my essence). Since C++ was/is unable to deduce
what the type T is from the nested (iterator) type, I simply told it to C++.
Of course, all this is automagic. See the code.
But. BUT! Capital but! ( http://home.uchicago.edu/~jebruner/Queen.htm )
This solution *only* works with iterators.
8<---
#include
#include <deque>
#include <list>
#include <vector>
#include <typeinfo>
#include <iterator>
//---------------------------------
#ifdef __GNUC__
namespace abi {
extern "C"
char*
__cxa_demangle(const char* mangled_name, char* buf, size_t* n, int*
status);
}
#endif
//----
template <typename T>
void telltype() {
#ifdef __GNUC__
size_t bsiz=1025;
char buff[bsiz];
int dummy;
abi::__cxa_demangle(typeid(T).name(), buff, &bsiz, &dummy);
std::cout << buff << std::endl;
#else
std::cout << typeid(T).name() << std::endl;
#endif
}
//---------------------------------
template
struct Helper {
static void applyFunc2(It begin, It end){
std::cout << "General version : ";
telltype
}
};
//---------------------------------
template<typename T>
struct Helper<T, typename std::deque{
typedef typename std::deque<T>::iterator deqit;
static void applyFunc2(deqit begin, deqit end) {
std::cout << "Special deque version : ";
telltype
}
};
//---------------------------------
template<typename T>
struct Helper<T, typename std::vector{
typedef typename std::vector<T>::iterator vectit;
static void applyFunc2(vectit begin, vectit end) {
std::cout << "Special vector version: ";
telltype
}
};
//---------------------------------
template<typename It>
void applyFunc2(It begin, It end){
Helper<typename std::iterator_traits
It>::applyFunc2(begin, end);
}
//---------------------------------
typedef int not_void;
not_void main() {
std::deque<int> idq;
std::list<int> ili;
std::vector<int> ive;
const size_t iarr_size=10;
int iarr[iarr_size];
applyFunc2(idq.begin(), idq.end());
applyFunc2(ili.begin(), ili.end());
applyFunc2(ive.begin(), ive.end());
applyFunc2(iarr, iarr+iarr_size);
return 0;
}
--->8
If this works, liked and accepted, can I put it into my CV that I have
helped Scott Meyers? Not that anyone will believe it, but... ;-)
(Also posted directly to the OP to avoid moderation delays.)
--
WW aka Attila
:::
Real_men_don't_need_spacebars.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
wade@stoner.com
Guest
|
| Posted: Sat Jan 29, 2005 4:32 am Post subject: Re: Specializing an algorithm for deque iterators |
|
|
David Abrahams wrote:
| Quote: | The
capabilities of deque iterators are no different from those of any
other random-access iterator. What could you possibly need to do
differently if the iterators happen to come from a std::vector or are
just pointers into some array on the stack?
|
The capabilities are not the same. Given a pair of vector iterators
that denote a range, I know that the elements in the range are
contiguous, and I may write my algorithm to take advantage of that
knowledge. Given an iterator into a deque<>, I know that a reference
to the object it points at will remain valid, even if the deque later
grows at the end. I may write my algorithm to take advantage of that
fact.
If the code does not need to be portable the information can be even
more useful. If I know that deque<T>::iterator is essentially T**
(which is one reasonable implementation) then I can effectively sort a
deque by swapping existing T*, rather than by swapping T (or taking the
time and space to make my own vector<T*>).
You may call these differences traits, rather than capabilities, and
that suggest a "more generic" solution to Scott's problem, but that
doesn't mean that there is no possible use for the information.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Pete Becker
Guest
|
| Posted: Sat Jan 29, 2005 4:42 am Post subject: Re: Specializing an algorithm for deque iterators |
|
|
White Wolf wrote:
| Quote: | Pete Becker wrote:
A pair of iterators designates a sequence of values.
Algorithms don't know or care what the source of
their iterators is.
Are you saying they don't care or that they should never care? I think it
is an important distinction. I say that I could not name any algorithm
right now which does (need to know where the iterator range came from), but
I would also have very hard time to prove that no algorithm should ever need
to know it.
|
Okay, if you insist: "Algorithms AS SPECIFIED IN THE STL don't know or
care what the source of their iterators is." If some code you wrote does
care, then it's not an algorithm AS SPECIFIED IN THE STL.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
David Abrahams
Guest
|
| Posted: Sat Jan 29, 2005 4:50 am Post subject: Re: Specializing an algorithm for deque iterators |
|
|
"White Wolf" <wolof (AT) freemail (DOT) hu> writes:
| Quote: | Pete Becker wrote:
Scott Meyers wrote:
But no matter how I call applyFunc2, I get the general version, not the
special version. How can I write a function template that will do
something special when passed a pair of deque iterators?
You're trying to go the wrong way down a one-way street.
I guess Pete you have made two steps in one. IIRC first you ask "Why do you
want to do that" and only then you straighten the other party out. ;-)
There is no such thing as a pair of deque iterators.
Hm. So two iterators denoting a range inside a deque are not a pair of
deque iterators? Forget it, it was only rhetorical.
A pair of iterators designates a sequence of values.
Algorithms don't know or care what the source of
their iterators is.
Are you saying they don't care or that they should never care? I think it
is an important distinction. I say that I could not name any algorithm
right now which does (need to know where the iterator range came from), but
I would also have very hard time to prove that no algorithm should ever need
to know it.
|
*If* the concept modeled by the deque iterators were more refined than
Random Access Iterator (say, Segmented Random Access Iterator -- see
Austern http://portal.acm.org/citation.cfm?id=647373.724070) then
there would indeed be a point in detecting them -- but really,
one would hope, you'd be detecting the more-refined concept and not
that they were iterators into a deque specifically.
It may be hard to prove, but it's also very hard to imagine a
situation in which detecting deque-iterator-ness is really
appropriate.
--
Dave Abrahams
Boost Consulting
www.boost-consulting.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Thomas Maeder
Guest
|
| Posted: Sat Jan 29, 2005 4:55 am Post subject: Re: Specializing an algorithm for deque iterators |
|
|
David Abrahams <dave (AT) boost-consulting (DOT) com> writes:
| Quote: | But what Pete Becker said is even truer. Trying to get special
behavior for deque iterators is anti-generic and probably wrong. The
capabilities of deque iterators are no different from those of any
other random-access iterator.
|
I agree, in general. But
a) the question was an interesting mind-teaser, and
| Quote: | What could you possibly need to do
differently if the iterators happen to come from a std::vector or are
just pointers into some array on the stack?
|
b) I'm confident that Scott has found such a need in some special case
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Eugene Gershnik
Guest
|
| Posted: Sat Jan 29, 2005 5:05 am Post subject: Re: Specializing an algorithm for deque iterators |
|
|
David Abrahams wrote:
| Quote: | What could you possibly need to do
differently if the iterators happen to come from a std::vector or are
just pointers into some array on the stack?
|
Provided the value_type is memcpy-able I could use memcpy, memmove etc. if
the iterators came from vector or array (and practically even string) but
not for deque. As a matter of fact one very popular standard library
overloads many of algorithms in the case iterators are pointers. Funnily it
doesn't do so for vector iterators so the following
const std::vector<char> buf(4);
const char * test = "abcd";
std::equal(buf.begin(), buf.end(), test);
std::equal(&buf[0], &buf[0] + buf.size(), test);
will use different implementations of equal with probable performance
implications.
--
Eugene
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Scott Meyers
Guest
|
| Posted: Sat Jan 29, 2005 5:06 am Post subject: Re: Specializing an algorithm for deque iterators |
|
|
On 27 Jan 2005 19:35:54 -0500, Pete Becker wrote:
| Quote: | You're trying to go the wrong way down a one-way street. There is no
such thing as a pair of deque iterators.
|
This, of course, is nonsense.
| Quote: | A pair of iterators designates
a sequence of values. Algorithms don't know or care what the source of
their iterators is.
|
This, too, is nonsense. I was revisiting Dietmar Kuehl's claim from long
ago (http://tinyurl.com/5kjst) that library implementers can achieve
significant performance improvements in standard algorithm implementations
if they take advantage of knowledge of the underlying data structures. To
do that, you need to know what data structure you are dealing with, i.e.,
which type of container you have.
| Quote: | If you care about the origin of your sequence of values you're not
dealing with iterators, but with containers. Write code that takes
containers.
|
But we're not always in a position to do that. If I want to implement
std::for_each and do a deque-specific optimization, the interface to
std::for_each is fixed. I have to work with what I have.
Of course, this doesn't mean we can't generalize. Dietmar pointed out that
the kind of optimizations possible for deque are likely to be applicable to
any segmented data structure akin to an array of arrays. So I also tried
the traits-based approach. The code is below. VC7.1 rejects my traits
partial specialization for deque (which I think is an error in VC7.1), and
both gcc 3.4.2 and Comeau 4.3.3 use the general traits template instead of
the one I'm trying to partially specialize for deque. If I'm doing
something wrong, I'd like to know what it is.
Scott
#include <vector>
#include <deque>
#include <iostream>
namespace sdm {
template<typename T>
struct iterator_traits {
static const bool forSegmentedArrayContainer = false;
};
template<typename T>
struct iterator_traits<typename std::deque::iterator> {
static const bool forSegmentedArrayContainer = true;
};
template<typename It, typename Func, bool forSegmentedArray>
struct ForEachHelper;
template<typename It, typename Func>
struct ForEachHelper<It, Func, false> {
static Func do_for_each(It begin, It end, Func f)
{
std::cout << "General for_eachn";
// ...
return f;
}
};
template
struct ForEachHelper<It, Func, true> {
static Func do_for_each(It begin, It end, Func f)
{
std::cout << "deque for_eachn";
// ...
return f;
}
};
template
Func for_each(It begin, It end, Func f)
{
return sdm::ForEachHelper<It, Func, sdm::iterator_traits
::do_for_each(begin, end, f);
}
}
void doNothing(int){}
int main()
{
std::vector<int> v;
std::deque<int> d;
sdm::for_each(v.begin(), v.end(), doNothing);
sdm::for_each(d.begin(), d.end(), doNothing);
}
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
