Re: std::vector : begin, end and insert - Using Objects instead of ints

On Fri, 18 May 2007 16:52:24 +0100, Gerry Quinn <gerryq@xxxxxxxxx> wrote:

In article <hevj43555ho2a29390i1hdah5dmugti9ka@xxxxxxx>, dsh@xxxxxxxx
says...

Some things to note:

1. When there's a choice, prefer preincrement to postincrement, because pre
doesn't require creation of a temporary object to return the original
value. That is, use ++it instead of it++. (I know, K&R taught the opposite,
but this is C++, which itself would have been better named ++C. <g>)

My view is that readability trumps efficiency in most cases,

The thing is, efficiency can be measured objectively, while "readability"
is highly subjective. I'm not interested in arguing which is more
"readable", ++i or i++. However, besides being more efficient for most
class types, ++i is definitely easier to think about than i++, because the
former simply increments i, while the latter creates a temporary copy of i,
increments i, and returns the temporary, which is ultimately discarded
without being used in the case we're discussing. While it makes most of the
same points, you might want to read what the C++ FAQ says about this:

http://www.parashift.com/c++-faq-lite/operator-overloading.html#faq-13.15

The bottom line is that in C++, it's conventional to use pre when there's a
choice, and there are decent reasons for this.

particularly where the efficiency gain is likely to be very small or
nonexistent. I find postincrement more readable, and use it everywhere
except for special cases. Postincrement certainly seems more idiomatic
in for loops, because if you are incrementing in the body of the loop
you will need to use it:

for ( int i = 0; i < vec.size(); )
{
CPoint & pt = vec[ i++ ];
}

FWIW, many people would say that embedding expressions with side-effects
inside other expressions is not very "readable". Again, this is a departure
from K&R thinking, and I don't necessarily agree with it, at least not in
all cases, because there are times when it would actually be incorrect to
split the operation into two statements, e.g. when erasing a list iterator.
In any event, I think you're really reaching to motivate something you
probably learned very early on. I wonder, what do you do for reverse
iteration? Do you really sit down and think about how you might write a
certain kind of loop that omits stmt3 in a for-loop header when you decide
how to write stmt3 for the vast majority of loops, when the former is
driven by correctness considerations and the latter is not?

(BTW, vector::size returns vector::size_type, which is an unsigned type.
Consequently, you really shouldn't use int for your index type.)

I presume VC7 optimises vector::iterator down to a real pointer,
though?

I dunno. Compile with /FAs and look at the assembly code.

4. The vector::at function is not really an "alternative" to operator[],
because the former checks its argument and throws an exception if it's out
of bounds. The latter doesn't perform any error-checking, and thus there
are major differences in performance and behavior between the two.

Then it's *exactly* an alternative! If it were the same it would
effectively be an alias.

The problem is, lots of people will read an unqualified "alternative" claim
as an "equivalence" claim. I think that's perfectly understandable
considering how you presented it:

CPoint & pt = vec[ i ];
// or alternatively
CPoint & samething = vec.at( i );

For the reasons I gave, I cannot imagine non-trivial usage of either which
would allow the substitution of one for the other without the surrounding
code suffering ripple effects from the change.

6. If you're really nuts about efficiency, don't use vec.end() (or
vec.size()) in your loop condition. Instead save its value to a (const)
variable and use it instead.

I'd rather hope that the optimiser would take care of that, so long as
the size of the vector is not altered inside the loop.

Here's a little program fragment for you to try:

#define _SECURE_SCL 0
#define _HAS_ITERATOR_DEBUGGING 0

#include <vector>

typedef std::vector<int> VecT;

void g(int);

void f1(VecT& v)
{
for (VecT::size_type i = 0; i < v.size(); ++i)
g(v[i]);
}

void f2(VecT& v)
{
for (VecT::iterator i = v.begin(); i != v.end(); ++i)
g(*i);
}

Compiled with:

cl -c -FAs -O2 -EHsc -W4 a.cpp

VC2005 optimizes the end() call but not size(), and the dereferencing of
the iterator is more efficient as well.

If it *is* altered, or more specifically if it is enlarged past its
initial capacity, the advantages of operator[] will become clear.

Sure, that's an advantage of using indexes. If you use iterators, you have
to convert them to indexes and recompute them once they're invalidated.
That's a good reason not to store vector iterators in another data
structure. (But note that indexes can become invalidated under some
conditions as well, such as inserting before their position.) However, we
were talking about loops that iterate over the whole container, and IME, at
least, this issue doesn't come up very often in this context. It's not the
sort of thing that's going to cause me to treat std::vector differently
from all other containers by default. (I could say that treating the
containers uniformly makes it easier to substitute one for the other, and
while that's true to a very small extent, it's not a persuasive argument,
because it's so rarely applicable.)

Though if you are doing tricks like that, vector::at may be a good
idea...

I don't think so. The only use for vector::at is when the provenance of the
index argument is unknown (e.g. user input), and one is too lazy to do his
own range-checking and/or wants the exception behavior of vector::at. That
is, if I'm writing a loop that moves things around such that index
variables have to be updated, I'm not going to use "at" in the misplaced
hope that it will catch mistakes I made in the updating. That would be
conflating exception handling with bug detection, which is a huge mistake.
What is useful is a more generalized range-checking feature, which handles
operator[] and iterators as well, which does not use C++ exceptions to
report errors, that can be enabled for debugging purposes, such as was
introduced in VC2005.

--
Doug Harrison
Visual C++ MVP
.

Relevant Pages

  • Re: std::vector : begin, end and insert - Using Objects instead of ints
    ... When there's a choice, prefer preincrement to postincrement, because pre ... The thing is, efficiency can be measured objectively, while "readability" ... split the operation into two statements, e.g. when erasing a list iterator. ... certain kind of loop that omits stmt3 in a for-loop header when you decide ...
    (microsoft.public.vc.mfc)
  • Re: C# Command to Wait a Specified Period of Time
    ... But the key to use the query syntax is you don't do the for each loop yourself, instead you state what you want, not how to do it. ... I'm sure that once one gains experience with these newer language constructs that they do enhance "readability" - for the people who know and use them. ... But don't go around saying that a code block consisting of delegates and anonymous methods is "more readable" than a simple "for loop". ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Factoring iteration
    ... Now it's cool that the double-nested loop turns into just the one line ... grid iterator class, where the actual per-item action is a method, ... All masks with only one bit set represent a solution for that field. ... actually requires backtracking, unless you want to find all possible ...
    (comp.lang.forth)
  • Re: Generics and for each
    ... so the compiler has no way of matching the 'String' type of the loop ... I used 'String' to ... stands it fails because it doesn't know that the Iterator is a ...
    (comp.lang.java.programmer)
  • Re: wich is faster
    ... On the premature optimisation front - it has to be a judgement call by ... an "& 1" and a simple loop dividing n by odd numbers from 3 to sqrt. ... I do not accept that readability is an excuse ...
    (comp.programming)