Iterator for range-based for loops

[stable mist]

I'm implementing iterators for a data structure. Using a "normal" for loops yields the correct result but for some reason ranged-based for loops do not. I copied the exact syntax used by range-based for loops on cppreference and it also yields the same incorrect result but I cannot figure out why even with a debugger. My structure currently contains {5, 12, 7}.

My "normal" for loop:

for(auto begin = q.begin(); begin != q.end(); ++begin)
{
    std::cout << *begin << ', ';
}

// Result: 5, 12, 7, 

Syntax used by the range-based for loop:

for(auto __begin = q.begin(), __end = q.end(); __begin != __end; ++__begin)
{

    std::cout << *__begin << '\n';

}

// Result: 5, 21845, 1
// Range-based for loops give the same result

State of the iterator at every step of the "normal" for loop:

{m_data = 0x7fffffffd990, m_current = 0, m_head = 0, m_tail = 0, m_end = false}
{m_data = 0x7fffffffd990, m_current = 1, m_head = 0, m_tail = 0, m_end = false}
{m_data = 0x7fffffffd990, m_current = 2, m_head = 0, m_tail = 0, m_end = false}

State of the iterator at every step of the range-based for loop:

{m_data = 0x7fffffffd990, m_current = 0, m_head = 0, m_tail = 0, m_end = false}
{m_data = 0x7fffffffd990, m_current = 1, m_head = 0, m_tail = 0, m_end = false}
{m_data = 0x7fffffffd990, m_current = 2, m_head = 0, m_tail = 0, m_end = false}

The syntax for both loops is nearly identical and the state of the iterator is identical for both. I fail to see why it doesn't yield the same result.

[quaint parcel]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question run !howto ask.

[velvet geode]

May we see the class definition of q

[rocky pike]

fun 🙂

Does for(auto begin = q.begin(), end = q.end(); begin != end; ++begin) yield the correct result?

[stable mist]

Anything specific you want to see? I think dumping the whole class definition of both the data structure and the iterator would be a bit much

[velvet geode]

Let's start with container::end and iterator::operator==

Also container::begin

[rocky pike]

Are you using address sanitizer btw

[stable mist]

No, same erroneous result

[stable mist]

Yes I am, here are the compiler arguments:

g++ main.cpp -g -O0 -fsanitize=address -o test -std=c++11 -Werror -Wall -Wextra

[delicate mortar]

in you copy constructor for you iterator you don't copy m_end

[rocky pike]

If it's outputting erroneous things bot not triggering asan that's weird af

[velvet geode]

And ,undefiend to the list of santizers

undefined*

[stable mist]

iterator begin()
{
    return iterator(*this, m_tail, false);
}

iterator end()
{
    return iterator(*this, m_head, true);
}

bool operator==(const fixed_deque_iterator_t& other)
{
    return (other.m_data == m_data && other.m_current == m_current && other.m_end == m_end) ? true : false;
}

!= is defined as !(x == y), as per the standard

[stable mist]

I am

[delicate mortar]

let's see the copy/move constructor

[rocky pike]

Do m_tail or m_head change at all during iteration

[stable mist]

Thanks I got something now, I can probably fix the error with that

[delicate mortar]

why check other.m_end == m_end?

[stable mist]

No, they are fixed

[velvet geode]

Oooo, what was it, I am excited :o

[stable mist]

It was an unrelated error in some other tests. I had the wrong order of operation, it's completely irrelevant to my problem 😦

No more errors from fsanatize=undefined unfortunately

[stable mist]

If the starting position is m_head, it means that the array is either empty or full. If it's empty, end is set to true from the beginning (I haven't implemented this yet). If it's full, the end flag is only set if the position reaches m_head after being incremented (after having done a full circle basically).

I haven't eaten yet so I will brb later

[quaint parcel]

@stable mist Has your question been resolved? If so, run !solved :)

[stable mist]

No.

Are there any other sanitisers I can enable? This sht is giving me a headache

[rocky pike]

asan and ubsan are the main ones

what's happening now, still the same output?

[velvet geode]

There is a thread sanitizer

Not sure if that would help

[stable mist]

Ye I've considered the thread and leaks sanitizers but I have no multithreading and no memory allocation

[velvet geode]

Is there just the one file?
If so ypu can post it and I can deep dive the code

[stable mist]

Still the same output. I'm guessing there is some UB involved because I can't get consistent behaviour and everything makes no sense

[stable mist]

Ye ig I'll just drop the file here

[rocky pike]

It does indeed seem like UB 🙂

[stable mist]

Oh

Oh

OH

[rocky pike]

I can't imagine how you're (presumably) reading garbage data and not triggering asan though

[stable mist]

Ye it was garbage data, I have no idea how asan wasn't triggered.

fixed_deque_iterator_t(xcontainer::fixed_deque<T, N> deque, std::size_t current, bool end)
{
    m_data = &(deque.m_data[0]);
    m_head = deque.m_head;
    m_tail = deque.m_tail;

    m_current = current;
    m_end = end;
}```
I was passing the queue by value so the iterator pointed to the data of a local object that went out of scope. Passing by reference fixed it, obviously

[rocky pike]

Ah, interesting 🙂

[stable mist]

I still don't understand why both AddressSanitizer and UndefinedBehaviourSanitizer didn't scream at me though.

Since it's all on the stack maybe the pointer was valid but pointing at memory that was used by other local variables? If so, why did I still get the correct result some times, why wasn't it always garbage/overwritten

If I mark this question as solve will it close it automatically? It's solved but I want to figure out why the sanitizers didn't pick up the mistake

[acoustic remnant]

[stable mist]

main.cpp

#include "fixed_deque.hpp"
#include <iostream>

int main()
{
    xcontainer::fixed_deque<int, 3> q;
    q.push_back(5);
    q.push_back(12);
    q.push_back(7);

    for(auto begin = q.begin(); begin != q.end(); --begin)
    {
        std::cout << *begin << '\n';
    }
}```
It was working on it so I don't guarantee everything works 100%, but at least it compiles.

If you want to replicate the bug, pass the queue by value*

fixed_deque_iterator_t(xcontainer::fixed_deque<T, N> deque, std::size_t current, bool end)

[rocky pike]

It'll mark it as solved but won't lock the thread or anything

[stable mist]

!solved

[quaint parcel]

Thank you and let us know if you have any more questions!

This thread is now set to auto-hide after an hour of inactivity

[acoustic remnant]

why does your iterator have so many fields

you only need T*

oh wait, this is a circular double ended queue with fixed length shoved in an array

[acoustic remnant]

to make for each work you need to define template specializations for std::begin, std::end, the global functions

[stable mist]

Each what?

[delicate mortar]

range based for loop doesn't look for std::begin/std::end directly

it uses ADL to get those

[velvet geode]

;compile -O2

#include <iostream>

namespace haha {
    struct whatevs {
        int a[4];
    };

    int* begin(whatevs& a) {
        return &a.a[0];
    }

    int* end(whatevs& a) {
        return &a.a[4];
    }
}

int main() {
    haha::whatevs b{{1, 2, 3, 5}};
    for (int x : b) {
        std::cout << x << std::endl;
    }
}

[fervent galleon]

Program Output

1
2
3
5

ZeroPointer#6105 | 59ms | c++ | x86-64 gcc 13.1 | godbolt.org

[velvet geode]

A demonstration of ADL here :)

[delicate mortar]

no that's not ADL

that's just in the rules of the ranged for loop

if you class has ::begin and ::end members then it uses those

[velvet geode]

I know that

[delicate mortar]

then why did you say it was ADL

[velvet geode]

if a class does not define member begin and end (like my example), I assumed it looked for non member begin and end using the same rules as ADL

Okay ya it does do what I thought it did

[acoustic remnant]

well, since C++17 I think they are used, before that they aren't

or maybe there is a default implementation that does
return myObj.begin()

[velvet geode]

What range based for loops do is it checks for certain conditions
Assuming you are looping through a
If a is an array it uses a as the start and a + size as the end
If a is an object with a member begin and end it uses a.begin() and a.end()
otherwise it uses begin(a) and end(a) using ADL to find the implmentation

I am fairly certain that this has always been the case (since c++11)

[acoustic remnant]

Confirmed

     If range-expression is an expression of array type, then begin-expr is __range and end-expr is (__range + __bound), where __bound is the number of elements in the array (if the array has unknown size or is of an incomplete type, the program is ill-formed);
    If range-expression is an expression of a class type C that has both a member named begin and a member named end (regardless of the type or accessibility of such member), then begin-expr is __range.begin() and end-expr is __range.end();
    Otherwise, begin-expr is begin(__range) and end-expr is end(__range), which are found via argument-dependent lookup (non-ADL lookup is not performed). 

so yes, no need to overload those functions

[velvet geode]

Now, std::begin and std::end do have default implementations which will defer to a.begin() for classes and a for arrays, but this need not be the source of the ranges in a range based for loop

[acoustic remnant]

yes

[velvet geode]

interestinglly enough, std::ranges::begin seems to follow the same rules as range based for loops