4

I want to traverse through the values of a vector in opposite direction. As you know the size of a vector is of size_t. When I use the following code:

for(size_t r=m.size()-1; r >= 0; r--)
{
    x[r] = f[r];
    for(size_t c = r+1; c < m.size(); c++)
    {
        x[r] -= m[r][c] * x[c];
    }
}

I will go out of the range of the vector because the r will become 4294967295 after decrementing r = 0.

I am not changing the r's type because in my project, I am treating warnings as errors, so it should be size_t or I should cast it which is not interesting.

mmostajab
  • 1,937
  • 1
  • 16
  • 37

6 Answers6

6

If you actually want to use size_t for indexing, the loop could be formulated as follows.

for(size_t r = m.size(); r > 0; r--)
{
    x[r-1] = f[r-1];
    for(size_t c = r; c < m.size(); c++)
    {
        x[r-1] -= m[r-1][c] * x[c];
    }
}

Basically you would iterate from m.size() to 1 and compensate by shifting inside the loop; but this solution might be a bit hard to follow. In this question, a proposed solution is to use a reverse_iterator, which can be seen as a suitable abstraction of the index. The entire topic is coverd in more depth in this question.

Community
  • 1
  • 1
Codor
  • 17,447
  • 9
  • 29
  • 56
  • 5
    DRY: `auto r1 = r - 1;` and use `r1` in the loop (or switch the names `r` and `r1` to make the loop body even more readable). – Angew is no longer proud of SO Dec 10 '14 at 13:34
  • 4
    @JamesKanze Funny; it's obfuscating to you, it expresses intent to me. But I believe we've had this discussion already. – Angew is no longer proud of SO Dec 10 '14 at 13:53
  • 1
    I strongly believe the 'correct' way would be to reformulate the implementation in such a way that index calculations are unnecessary in the first place. – Codor Dec 10 '14 at 13:54
  • 1
    @Griwes Hiding the type from the reader, especially when it makes so much difference, is obfuscation. It's also very fragile, since a change elsewhere in the code could cause a significant change in the semantics here. Using `auto` for an integral type is _always_ a problem, since it is critical to know whether the type is signed or unsigned; the semantics change radically. – James Kanze Dec 10 '14 at 14:08
  • 1
    James didn't point out not knowing integer promotion rules as a problem. He pointed out changing things elsewhere having a significant change in semantics here. – R. Martinho Fernandes Dec 10 '14 at 14:22
  • 1
    @Griwes What does knowing the promotion rules have to do with anything, when you don't know the type you're starting with. The use of `auto` in such cases is a serious anti-pattern, which should be avoided. Especially when the types potentially involved have such significantly different semantics. (And of course, the promotion rules vary from one platform to the next, depending on the sizes of the different types.) – James Kanze Dec 10 '14 at 14:28
  • @R.MartinhoFernandes Yes. The scenario which I was particularly worried about is if `auto r = m.size();` gets replaced by `auto r = it1 - it2;`. The entire semantics of the program change. – James Kanze Dec 10 '14 at 14:29
3

This is my favorite way:

std::size_t r = m.size();
while (r --> 0)
{
    // access m[r]
}
lisyarus
  • 15,025
  • 3
  • 43
  • 68
  • I realize this is nice and pretty, but I would HIGHLY suggest against using `-->` the post-decrement then compare in the same expression obfuscates what's going on here – Mgetz Dec 10 '14 at 13:57
  • @Mgetz once one learns about how post-decrement works, it should be obvious what is going on here. I wish to consider not understanding this case to be just lack of knowledge of the language. – lisyarus Dec 10 '14 at 14:02
  • @lisyarus the fact that the question Park Young-Bae linked exists at all should be proof otherwise. – Mgetz Dec 10 '14 at 14:03
  • @Mgetz loads of things in C++ look weird and need clarification for those not experienced with the language. In my opinion, this should not be a reason to avoid using this things. – lisyarus Dec 10 '14 at 14:06
  • And now it's my favourite way because it has a funky little `-->' arrow pointing at the zero. – Persixty Dec 10 '14 at 14:09
  • Why not simply `while (r--)` while we're at it? – fredoverflow Dec 10 '14 at 14:09
  • 1
    Having post-decrement and comparison in the same statement isn't that sinful, but breaking it up to look like `-->` will confuse inexperienced readers. – The Forest And The Trees Dec 10 '14 at 14:09
  • @Griwes "so you think we should optimize for newbies, not for experts?" - totally don't understand how you derived this from my words. – lisyarus Dec 10 '14 at 14:11
  • @lisyarus damn, I somehow managed to miss a single "not" in your comment. Sorry ;) – Griwes Dec 10 '14 at 14:13
  • @Griwes btw, I fully agree with your (now deleted) comment :) – lisyarus Dec 10 '14 at 14:17
  • 1
    Modifying state in a conditional should generally be avoided, since it results in side effects where the reader doesn't expect them. What's wrong with putting the `--` in a separate statement at the top of the loop, where it cannot be overlooked. – James Kanze Dec 10 '14 at 14:25
1

Well, you should avoid size_t as much as possible, since it is an unsigned type, and unsigned types aren't well behaved in C++, at least when it comes to arithmetic. But regardless of the type, the usual idiom I'd use for iterating in reverse (assuming for some reason I can't just use reverse iterators, which would be the natural solution) would be something like:

int r = m.size();     //  but size_t r would work here too.
while ( r > 0 ) {
    -- r;
    //  ...
}

Moving the decrementation to the top of the loop solves most of the problems, and is IMHO much clearer.

James Kanze
  • 150,581
  • 18
  • 184
  • 329
  • the problem is that the m.size() is of size_t and it will make a warning. – mmostajab Dec 10 '14 at 13:37
  • So cast it. That's what I'd do. It's the clearest way. As long as your vector isn't utterly vast, that is ;p – Lightness Races in Orbit Dec 10 '14 at 13:45
  • 1
    @mmostajab I know. This is a design defect in the standard (due to constraints on some hardware at the time the library was being designed). If you're sure that `m` can never be larger than `INT_MAX` (and there are a lot of contexts where this can be guaranteed), then just cast. Otherwise, use a larger signed integral type. (In the code I present, `size_t` will actually work. But it could end up causing problems later.) – James Kanze Dec 10 '14 at 13:46
  • I totally second the argument; typically, as the standard library can be used, it should not be necessary to use `size_t` for indexing as iterators can be used. – Codor Dec 10 '14 at 14:07
  • Unsigned types are the ones well behaved in C++, not signed ones - signed over/underflow are undefined, unsigned are well-defined. Please stop spreading harmful propaganda. – Griwes Dec 10 '14 at 14:13
  • Also `int` is wrong; it should be, at the very least, `std::ptrdiff_t`. – Griwes Dec 10 '14 at 14:15
  • 1
    @Griwes Having something defined to do the wrong thing is worse than undefined behavior. In either case, you can't count on the behavior being what you want. Unsigned types in C++ are broken for use as an arithmetic type, for several reasons. Depending on the context, you _might_ want to use `std::ptrdiff_t`, but in a lot of cases, you can know that `int` won't overflow, and safely use it. – James Kanze Dec 10 '14 at 14:22
  • Again the same story. Let me repeat: you can reason about unsigned arithmetics. You cannot reason about undefined behavior. Hence, UB is always worse. Case closed, move on already (and stop spreading harmful advice :/). – Griwes Dec 10 '14 at 14:24
  • 1
    @Griwes You can reason that neither do what you want in the case of overflow. That's about all. In general, the semantics of unsigned integral types in C++ are not appropriate for arithmetic values. They don't work; trying to use them for arithmetic values is an anti-pattern, which should be avoided. – James Kanze Dec 10 '14 at 15:04
0

Unsigned arithmetic is well-defined in C++, so I would just compare against the "overflow":

for (size_t r = m.size() - 1; r != -1; r--)

In the loop condition, the -1 is automatically converted to an unsigned with the correct value.

fredoverflow
  • 256,549
  • 94
  • 388
  • 662
0

Using Boost.Range:

for (auto r : boost::irange(std::size_t(0), m.size()) | boost::adaptors::reversed) {
    x[r] = f[r];
    for (auto c : boost::irange(r + 1, m.size())) {
        x[r] -= m[r][c] * x[c];
    }
}
0

For anyone who is still searching for a method use the difference type from the containers, only a slight modification is needed in the code, instead of using size_t r = m.size()-1 use the following

std::vector<T>::difference_type r = m.end()-m.begin()

or you can use

std::ptrdiff_t r = m.end()-m.begin() and the loop will work ptrdiff_t is just an alias that marks the distance between 2 iterators.

benubha369
  • 1
  • 4