Is swap really an algorithm?
Scott Meyers
(see 25.2.2). This was a surprise, because my understanding was that
all algorithms took at least one pair of iterators to identify the
objects to work on. This understanding is consistent with 25/3, which
states that "All of the algorithms are ... parameterized by iterator
types." Swap, of course, is not. Furthermore, swap is described as a
sub-section under 25.2, and 25.2's title is "Mutating sequence
operations." But swap doesn't operate on a sequence.
My sense is that swap should not be listed as an algorithm. I frankly
think clause 18 ("Language Support Library") would be a more suitable
home for it. It strikes me as a lot more like auto_ptr than like the
genuine algorithms. Yes, I know that that would separate it from
swap_ranges and iter_swap, but those really ARE algorithms, and anyway,
we separate the new operator and operator new, even though they're about
as closely related as one can get.
Is there some reason why swap is listed as an algorithm that I'm
overlooking?
Thanks,
Scott
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std...@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]
Niels Dekker - no return address
> Is there some reason why swap is listed as an algorithm that I'm
> overlooking?
Possibly the fact that a lot of STL related and swap related websites
also refer to swap as being an algorithm:
The HP C++ User Documentation ((c) Rogue Wave Software) lists swap
within the category "Algorithms that use no iterators", together with
min and max.
http://h30097.www3.hp.com/cplus/algorithms_3c__std.htm
SGI's STL Programmer's Guide about swap: "This is used as a primitive
operation by many other algorithms" [i.e., algorithms other than swap,
implying that swap is an algorithm as well]
http:www.sgi.com/tech/stl/swap.html
Also there's a article by Danny Kalev entitled "Using the Swap()
Algorithm",
http://www.informit.com/guides/content.asp?g=cplusplus&seqNum=155&rl=1
Many more sites call swap an algorithm, e.g.:
http://www.google.com/search?q=std%20"swap%20algorithm"
So I guess a lot of people do think that swap is an algorithm.
--
Niels Dekker
http://www.xs4all.nl/~nd/dekkerware
C++ programmer at LKEB, Leiden University Medical Center
Richard Smith
> It was recently pointed out to me that swap is listed as an algorithm
> (see 25.2.2). This was a surprise, because my understanding was that
> all algorithms took at least one pair of iterators to identify the
> objects to work on.
std::fill_n only takes a single iterator. But I take your point.
> This understanding is consistent with 25/3, which
> states that "All of the algorithms are ... parameterized by iterator
> types." Swap, of course, is not. Furthermore, swap is described as a
> sub-section under 25.2, and 25.2's title is "Mutating sequence
> operations." But swap doesn't operate on a sequence.
Probably because it's a convenient place of iter_swap and keeping the
two together seemed a good idea?
> My sense is that swap should not be listed as an algorithm. I frankly
> think clause 18 ("Language Support Library") would be a more suitable
> home for it.
Clause 18 is where all the bits that blur the language-library
boundary live -- all the things that can't obviously be implemented as
pure library features in the language. It's also (broadly) the only
part of the library that freestanding implementations need provide.
So no, I don't think std::swap belongs there.
> It strikes me as a lot more like auto_ptr than like the
> genuine algorithms.
Which surely suggests clause 20 ("General utilities library")?
--
Richard Smith
James Kanze
> It was recently pointed out to me that swap is listed as an algorithm
> (see 25.2.2). This was a surprise, because my understanding was that
> all algorithms took at least one pair of iterators to identify the
> objects to work on. This understanding is consistent with 25/3, which
> states that "All of the algorithms are ... parameterized by iterator
> types." Swap, of course, is not. Furthermore, swap is described as a
> sub-section under 25.2, and 25.2's title is "Mutating sequence
> operations." But swap doesn't operate on a sequence.
min and max don't take iterators, either, although they're in
the algorithms section as well. As "Sorting and related
operations", which is stretching it a bit too.
> My sense is that swap should not be listed as an algorithm. I frankly
> think clause 18 ("Language Support Library") would be a more suitable
> home for it.
Header <utility>, IMHO. (IMHO, auto_ptr would be better off
there as well.)
> It strikes me as a lot more like auto_ptr than like the
> genuine algorithms. Yes, I know that that would separate it from
> swap_ranges and iter_swap, but those really ARE algorithms, and anyway,
> we separate the new operator and operator new, even though they're about
> as closely related as one can get.
Can't avoid that one: one's language, the other library.
> Is there some reason why swap is listed as an algorithm that I'm
> overlooking?
History? Swap was part of the original STL, from the very
beginning, I think. (But then, so was pair, part of <utility>.)
--
James Kanze (GABI Software) email:james...@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Scott Meyers
> The HP C++ User Documentation ((c) Rogue Wave Software) lists swap
> within the category "Algorithms that use no iterators", together with
> min and max.
And now I see that min and max are also listed as algorithms in the
standard. This strikes me as incorrect for the same reasons as for
swap. It seems to me that there should be a better definition of
"algorithm" than "because we say it's one." If swap, min, and max are
algorithms, why isn't make_pair? (make_pair is a "utility" and lives in
clause 20, which is really where swap, min, and max should live, IMO,
along with any other "algorithms" that don't take pairs of iterators.)
One of the reasons I care about this is the teachability of the concepts
and architecture of the STL. It's already bad enough that an STL
"algorithm" is not the same as a computer science "algorithm." Now I
can't even say that an STL algorithm is a restricted form of function
template that takes one or more iterator pairs, nor can I say that all
algorithms operate on iterators.
With the current state of affairs, what does it mean for a function
template to be an "algorithm?"
Scott
Pedro Lamarão
> One of the reasons I care about this is the teachability of the concepts
> and architecture of the STL. It's already bad enough that an STL
> "algorithm" is not the same as a computer science "algorithm." Now I
> can't even say that an STL algorithm is a restricted form of function
> template that takes one or more iterator pairs, nor can I say that all
> algorithms operate on iterators.
>
> With the current state of affairs, what does it mean for a function
> template to be an "algorithm?"
Hum...
Should we delete the <numerics> header and move accumulate,
inner_product, partial_sum and adjacent_difference into <algorithm> ?
--
Pedro Lamarão
Gennaro Prota
>And now I see that min and max are also listed as algorithms in the
>standard. This strikes me as incorrect for the same reasons as for
>swap.
Please, don't take this as a jab: of course you know that you have to
include <algorithm> both for swap and for min/max, so why are you
surprised that they are listed as algorithms? For the record, I agree
that they aren't quite in the right place, but that applies to the
header which defines them, also (on this matter, we've often mentioned
on c.std.c++ how bad the partitioning of the standard headers is).
--
HELP: many of this group's participants might know that I'm the legit
owner of the yahoo account with id 'gennaro_prota'; I would be
immensely grateful to anyone who might help me gaining access
to it again (note that I'm now using the id 'gennaro.prota').
Thanks!
Genny.
Scott Meyers
> On 7 fev, 16:06, Scott Meyers <use...@aristeia.com> wrote:
>> With the current state of affairs, what does it mean for a function
>> template to be an "algorithm?"
>
> inner_product, partial_sum and adjacent_difference into <algorithm> ?
That would not be unreasonable, IMO, but I think you miss my point.
Regardless of how the STL algorithms are partitioned into headers, it's
still useful to be able to tell people what it is that makes something
an algorithm. If I claim that a class template is an STL container,
somebody can see if it meets the requirements of various tables in the
standard. Ditto for an iterator. But if I claim that a function
template is an algorithm, there does not seem to be any requirement that
it must meet. So if I'm trying to teach people about the fundamental
concepts behind the STL, what do I tell them about what it means to be
an algorithm? I used to think I could tell them that every algorithm
operates on one or more sequences identified by one or more pair of
iterators. But that's not true.
Scott
James Kanze
> Niels Dekker - no return address wrote:
> > The HP C++ User Documentation ((c) Rogue Wave Software) lists swap
> > within the category "Algorithms that use no iterators", together with
> > min and max.
> And now I see that min and max are also listed as algorithms in the
> standard. This strikes me as incorrect for the same reasons as for
> swap.
Even more so, I would say. At least swap does something.
> It seems to me that there should be a better definition of
> "algorithm" than "because we say it's one."
In a certain sense, everything in the standard is "because we
say so". There may be (almost always is, in fact) a rationale
behind it, but that rationale isn't part of the standard.
In this case, I think the standard is making a binary cut: there
are objects, and there are algorithms, and that's it. It's sort
of logical---dictionary.com gives definitions such as "a set of
rules for solving a problem in a finite number of steps", or "a
step-by-step problem-solving procedure". Interestingly enough,
as a matter of principle, the standard doesn't impose an
"algorithm"; it just requires that each function solve the given
problem within certain constraints. The implementation of the
function, however, must be an algorithm.
> If swap, min, and max are
> algorithms, why isn't make_pair? (make_pair is a "utility" and lives in
> clause 20, which is really where swap, min, and max should live, IMO,
> along with any other "algorithms" that don't take pairs of iterators.)
In a certain sense, make_pair does suppose an algorithm, a
finite set of steps which can be applied to solve the problem of
creating an object of type pair. Of course, in this case, the
number of steps is trivially 1, and the purpose of the function
isn't to implement some more or less complicated logic; it's so
that I can construct an object of type pair without having to
spell out the types in their excrutiating detail. Where as swap
really does exist in order that the user doesn't have to write
out the finite number of steps each time manually.
(Not that I disagree with you fundamentally. I'd have put swap
in <utility> as well, and min and max in <numeric>. But I don't
think you can argue too much on the grounds of what is or is not
an algorithm.)
> One of the reasons I care about this is the teachability of the concepts
> and architecture of the STL. It's already bad enough that an STL
> "algorithm" is not the same as a computer science "algorithm." Now I
> can't even say that an STL algorithm is a restricted form of function
> template that takes one or more iterator pairs, nor can I say that all
> algorithms operate on iterators.
> With the current state of affairs, what does it mean for a function
> template to be an "algorithm?"
It means that you have to include <algorithm>, and not some
other header, to use it:-). And that it's defined in section 25
of the standard.
It's interesting in this regard that the title of §26.6 is
"Generalized numeric operations", and not "Generalized numeric
algorithms". Although the text in the section does refer to its
functions as algorithms, e.g.: "The requirements on the types of
algorithms arguments that are described in the introduction to
clause 25 also apply to the following algorithms." There's also
§20.6.4 "Specialized algorithms", and in the current draft,
§28.11 "Regular expression algorithms", which define additional
functions which deal with iterators. Elsewhere, the standard
refers to "non member functions", but then the question is, non
members of what? The functions do operate on a specific type
(as opposed to an algorithm, which defines a sequence of steps
to be carried out, independantly of the type).
--
James Kanze (GABI Software) email:james...@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Kristof Zelechovski
Uzytkownik "James Kanze" <james...@gmail.com> napisal w wiadomosci news:1170939874.0...@k78g2000cwa.googlegroups.com...
> (Not that I disagree with you fundamentally. I'd have put swap
> in <utility> as well, and min and max in <numeric>. But I don't
> think you can argue too much on the grounds of what is or is not
> an algorithm.)
min and max are not restricted to numeric types.
It would not be sound to declare them as numerical operations.
>
> functions which deal with iterators. Elsewhere, the standard
> refers to "non member functions", but then the question is, non
> members of what? The functions do operate on a specific type
Non members of any class.
> (as opposed to an algorithm, which defines a sequence of steps
> to be carried out, independantly of the type).
>
Alex Howlett
> That would not be unreasonable, IMO, but I think you miss my point.
> Regardless of how the STL algorithms are partitioned into headers, it's still
> useful to be able to tell people what it is that makes something an
> algorithm. If I claim that a class template is an STL container, somebody
> can see if it meets the requirements of various tables in the standard.
> Ditto for an iterator. But if I claim that a function template is an
> algorithm, there does not seem to be any requirement that it must meet. So
> if I'm trying to teach people about the fundamental concepts behind the STL,
> what do I tell them about what it means to be an algorithm? I used to think
> I could tell them that every algorithm operates on one or more sequences
> identified by one or more pair of iterators. But that's not true.
>
> Scott
You could use the term "STL container algorithm" to describe algorithms
that operate on iterators into STL containers. That would allow you to
say, "An STL container algorithm is a restricted form of function
template that takes one or more iterator pairs." Additionally, you
would get the added bonus of not smashing the general computer-sciency
definition of "algorithm." If the students already know what an
algorithm is, your definition of "STL container algorithm" would then
be a natural extension of that.
Ben Hutchings
> Scott Meyers wrote :
>
>> That would not be unreasonable, IMO, but I think you miss my point.
>> Regardless of how the STL algorithms are partitioned into headers, it's still
>> useful to be able to tell people what it is that makes something an
>> algorithm. If I claim that a class template is an STL container, somebody
>> can see if it meets the requirements of various tables in the standard.
>> Ditto for an iterator. But if I claim that a function template is an
>> algorithm, there does not seem to be any requirement that it must meet. So
>> if I'm trying to teach people about the fundamental concepts behind the STL,
>> what do I tell them about what it means to be an algorithm? I used to think
>> I could tell them that every algorithm operates on one or more sequences
>> identified by one or more pair of iterators. But that's not true.
>>
>> Scott
>
> You could use the term "STL container algorithm" to describe algorithms
> that operate on iterators into STL containers.
Iterators need not point into containers (consider istream_iterator or
raw pointers) and yet these algorithms can work with them as well. So
they could maybe be called "STL iterator algorithms" or "iterative
algorithms".
Ben.
--
Ben Hutchings
Theory and practice are closer in theory than in practice.
- John Levine, moderator of comp.compilers