Class with iteration capability like std::map

[Satoshi Yoda]

Good day!

I am currently learning C++ and am struggling with implementing some test class, just for illustration.
The example class should be iteratable with range-based for loop with structured binding declaration with pairs<key, value> like std::map, but instead of custom key type it uses just size_t.
To be more specific, I wrote some tests to illustrate desired behavior.

Firstly, here are the tests for std::map, which demonstrate the possibility of such behavior (these tests pass without errors):

TEST_CASE("std::map tests") {
    std::map<size_t, int> data;

    data[0] = 0;
    data[1] = 1;
    data[2] = 2;

    SECTION("check initial elements") {
        int expected = 0;
        for (auto [index, elem] : data) {
            REQUIRE(elem == expected);
            expected++;
        }
    }

    SECTION("check for not modified elements") {
        for (auto [index, elem] : data) {
            elem = elem + 10;
        }
        int expected = 0;
        for (auto [index, elem] : data) {
            REQUIRE(elem == expected);
            expected++;
        }
    }

    SECTION("check for modified elements") {
        for (auto& [index, elem] : data) {
            elem = elem + 10;
        }
        int expected = 10;
        for (auto [index, elem] : data) {
            REQUIRE(elem == expected);
            expected++;
        }
    }
}

Now, here are the tests I wrote for my_array class. The expected behavior is very similar to std::map:

TEST_CASE("my_array tests") {
    my_array<int> data;

    data.add(0);
    data.add(1);
    data.add(2);

    SECTION("check initial elements") {
        int expected = 0;
        for (auto [index, elem] : data) {
            REQUIRE(elem == expected);
            expected++;
        }
    }

    SECTION("check for not modified elements") {
        for (auto [index, elem] : data) {
            elem = elem + 10;
        }
        int expected = 0;
        for (auto [index, elem] : data) {
            REQUIRE(elem == expected);
            expected++;
        }
    }

    // not compiling at the moment
    // SECTION("check for modified elements") {
    //     for (auto& [index, elem] : data) {
    //         elem = elem + 10;
    //     }
    //     int expected = 10;
    //     for (auto [index, elem] : data) {
    //         REQUIRE(elem == expected);
    //         expected++;
    //     }
    // }
}

Here is my class implementation, stripped of all the unimportant details such as copy/move constructors, assignment operators, const method variants, and some other stuff:

#pragma once

#include <cassert>
#include <vector>

template <typename T>
class my_array_iterator {
private:
    size_t index;
    typename std::vector<T>& data;

public:
    my_array_iterator(size_t index_, typename std::vector<T>& data) : index(index_), data(data) {
        assert(index <= data.size());
    }

    my_array_iterator& operator++() {
        assert(index < data.size());
        index++;
        return *this;
    }

    typename std::pair<size_t, T> operator*() {
        assert(index < data.size());
        return { index, data[index] };
    }

    bool operator==(const my_array_iterator<T>& other) const {
        assert(data.size() == other.data.size());
        assert(index <= data.size());
        return index == other.index;
    }
};

template <typename T>
class my_array {
private:
    std::vector<T> data;

public:
    void add(T element) {
        data.push_back(element);
    }

    T& operator[](size_t index) noexcept {
        assert(index < data.size());
        return data[index];
    }

    typedef my_array_iterator<T> iterator;

    iterator begin() {
        return iterator { 0, data };
    }

    iterator end() {
        return iterator { data.size(), data };
    }
};

I can change this line:

std::pair<size_t, T> operator*() {...}

to this:

std::pair<size_t, T&> operator*() {...}

and have the value be passed by reference, which makes another section of the test case to pass.
However, I'm not sure how to get both to work.

for (auto [index, elem] : data) {...}
for (auto& [index, elem] : data) {...}

Can anyone provide some advice on how to achieve this?

[jonnin]

A simple way to get both iteration and hash/map access is to stuff the data into a sequential container (vector, C-array, C-pointer, whatever) where the key is the index, and the data in a location is marked valid or not..
eg
data[key] would have a data.valid member (perhaps its a pair of <data, bool> where the valid field is the bool in the pair).
then you can iterate and ignore empty (invalid) locations in the container or hop directly to an item using the key.

you can also use parallel containers, where you put the data into a map and when you do that, you ALSO put a pointer or reference to the same data into a vector that you can iterate.

[Satoshi Yoda]

@jonnin
Hmm... I'm sorry it looks like I was not clear enough in my initial post. Yes, I sayed "like std::map but with the key type = size_t". But really what I want from std::map is the illustration of the way how it can be iterated in C++17 style loop, that's all. So these things about "empty gaps in a sequential container" and "underlying structure with two different containers at the same time" — that I can do if I need... But I am not interested in that now. So my class is called my_array, because it kind of contains records with only sequential indexes, unlike std::map. An that is intended to make example more simple. Because the only thing I am interested in is how to make a possibility for some class to be iterated in 2 ways:
like that
for (auto [index, elem] : data) {...}
and like that
for (auto& [index, elem] : data) {...}
with appropriate by value / by reference behavior :)

UPD: and I am interested exactly in that:
for (auto [index, elem] : data) {...}
not that:
for (auto elem : data) {...}
Despite the fact that I am illustrating it with kind of sequential container.

[Satoshi Yoda]

Maybe my problem is not with containers and iterations at all.
Here:

TEST_CASE("just structured bindings") {
    int a = 10;
    int b = 42;

    // How?
    // std::pair<int, int> p1 { a, b };
    // std::pair<int, int>& p { p1 };
    std::pair<int&, int&> p { a, b }; 

    SECTION("check for not modified values") {
        auto [aa, bb] = p;
        aa = 5;
        bb = 7;
        REQUIRE(a == 10);
        REQUIRE(b == 42);
    }

    SECTION("check for modified values") {
        auto& [aa, bb] = p;
        aa = 5;
        bb = 7;
        REQUIRE(a == 5);
        REQUIRE(b == 7);
    }
}

the essential problem:
How can I declare some pair so that it can be later unfolded as structured bindings so its elements can be used as a value and as a reference?

[JLBorges]

Something along these lines, perhaps:

#include <iostream>
#include <vector>
#include <utility>
#include <iterator>
#include <string>

template < typename T > struct my_array
{
    std::vector<T> items ;

    struct const_iterator
    {
        using value_type = std::pair<std::size_t,const T&> ;
        using iterator_category = std::input_iterator_tag ;
        using pointer = void ;
        using reference = value_type ;
        using difference_type = std::ptrdiff_t ;

        auto operator* () const noexcept { return value_type{ pos, *current } ; }
        const_iterator& operator++() noexcept { ++current ; ++pos ; return *this ; }
        const_iterator operator++(int) noexcept { const auto prev = *this ; ++*this ; return prev ; }

        auto operator <=> ( const const_iterator& that ) const noexcept = default ;

        typename std::vector<T>::const_iterator current ;
        std::size_t pos ;
    };

    const_iterator begin() const noexcept { return const_iterator{ items.begin(), 0 } ; }
    const_iterator end() const noexcept { return const_iterator{ items.end(), items.size() } ; }

    // ...
};

int main()
{
    const my_array<std::string> arr { { "zero", "one", "two", "three", "four", "five", "six" } } ;
    for( auto [n,str] : arr ) std::cout << n << ". " << str << '\n' ;
}

http://coliru.stacked-crooked.com/a/c0733f5dc035ef04

[Satoshi Yoda]

@JLBorges
Sorry but your example just doesn't compile when I change auto [n,str] : arr to auto& [n,str] : arr

[seeplus]

It won't as arr is defined as const on L37 and you can't have a non-const ref to a const. Also the given iterator struct is for a const iterator.

[As this is VS update day, I currently don't have access to VS to test]

[Satoshi Yoda]

@seeplus
There are 3 meaningful ways to iterate such container:

for (auto [n, str] : data)        {...} // #1
for (auto& [n, str] : data)       {...} // #2
for (const auto& [n, str] : data) {...} // #3 

And the user of this container should be able to select the most convenient for him, so ideally all three should work without any changes inside container implementation, like in std::map:
#1 User can change iterated values, but it will not affect values stored inside container.
#2 User can change iterated values, and it will affect values stored inside container.
#3 User can not change iterated values.

Looks like @JLBorges implementation supports #1 (as in example, but it works incorrectly, because it does not allow to change the values, because they are const T& instead of non-const value copies, as expected) and #3 (with L38 change). And it does not support #2 variant, just remove const on L37 is not enough.

Looks like I am not capable of implementing even #1 + #2. And the "const thing" brings a whole new level of messiness into that task. So I was hoping to solve #1 and #2 first, and only after that dive deep into const-support-implementation, which is outside of the initial scope of my question, for clarity and simplicity... So, if it will work, it's perfect! But initially my problem was not in the const support.

[seeplus]

Well simply you can do something like this:

#include <iostream>
#include <vector>
#include <string>

template < typename T >
struct my_array {
	std::vector<T> items;

	auto begin() noexcept {
		return items.begin();
	}

	auto end() noexcept {
		return items.end();
	}

	auto begin() const noexcept {
		return items.cbegin();
	}

	auto end() const noexcept {
		return items.cend();
	}

	auto cbegin() const noexcept {
		return items.cbegin();
	}

	auto cend() const noexcept {
		return  items.cend();
	}
};

struct myType {
	size_t n {};
	std::string nam {};
};

int main() {
	my_array<myType> arr {{ { 0, "zero"}, { 1, "one" }, { 2, "two" }, { 3, "three" }, { 4, "four" }, { 5, "five" }, { 6, "six" }}};

	for (auto& [n, str] : arr)
		std::cout << n++ << ". " << (str += '!') << '\n';

	std::cout << '\n';

	for (auto [n, str] : arr)
		std::cout << n << ". " << str << '\n';

	std::cout << '\n';

	for (const auto& [n, str] : arr)
		std::cout << n << ". " << str << '\n';

	std::cout << '\n';

	const my_array<myType> arrc {{ { 0, "zero"}, { 1, "one" }, { 2, "two" }, { 3, "three" }, { 4, "four" }, { 5, "five" }, { 6, "six" }}};

	for (auto [n, str] : arrc)
		std::cout << n << ". " << str << '\n';

	std::cout << '\n';

	for (const auto& [n, str] : arrc)
		std::cout << n << ". " << str << '\n';
}

which displays:

0. zero!
1. one!
2. two!
3. three!
4. four!
5. five!
6. six!

1. zero!
2. one!
3. two!
4. three!
5. four!
6. five!
7. six!

1. zero!
2. one!
3. two!
4. three!
5. four!
6. five!
7. six!

0. zero
1. one
2. two
3. three
4. four
5. five
6. six

0. zero
1. one
2. two
3. three
4. four
5. five
6. six

[deleted account xyzzy]

There are 3 meaningful ways to iterate such container:

There are more than 3 ways. Other ways could use operator[] or the container's defined iterators.

The iterator method can look a bit more "wordy."

// https://en.cppreference.com/w/cpp/container/map/begin
#include <iostream>
#include <map>

int main( )
{
   std::map<int, float> num_map;

   num_map[ 4 ] = 4.13f;
   num_map[ 9 ] = 9.24f;
   num_map[ 1 ] = 1.09f;

   // calls a_map.begin() and a_map.end()
   for ( auto it = num_map.begin( ); it != num_map.end( ); ++it )
   {
      std::cout << it->first << ", " << it->second << '\n';
   }
}

http://coliru.stacked-crooked.com/a/91e5953ebaa7647f

[Satoshi Yoda]

@seeplus
Thank you for that example! It's very illustrative. I will save it in my learn C++ folder =)

But I have a problem with adaptation this to my real-life case. Since I don't have a single? plain? compact? how do I call it? object in memory that stores the key and the value, like your myType does. So I can not implement underlying structure as a single vector. So, I guess, I need my custom iterator (+const_iterator, but not the point) for my class. And the problem is I don't know, what type that iterator should return in operator*
I tried that in my initial example:

typename std::pair<size_t, T> operator*() {
    return { index, data[index] };
}

but it does not give the ability to iterate both ways:

for (auto& [n, str] : arr) {...}
for (auto [n, str] : arr) {...}

Because it creates the copy of my data[index] when pair is created. So, no & iteration available.
How do I solve it?

[Satoshi Yoda]

@George P
Isn't you example just another (pre C++17) syntactic way to write the same thing as this?

for ( auto& [key, value] : num_map )
{
   std::cout << key << ", " << value << '\n'; 
}

...although you raised an interesting point here:
How do I write the analogue of this:

for (auto& [key, value] : obj)
{
    // do something
}

for (auto [key, value] : obj)
{
    // do something
}

Using "old" iterator syntax?
Like that? Or not?...

for (auto it = obj.begin(); it != obj.end(); ++it)
{
    auto& key = it->first;
    auto& value = it->second;
    // do something
}

for (auto it = obj.begin(); it != obj.end(); ++it)
{
    auto key = it->first;
    auto value = it->second;
    // do something
}

If yes, then it means that my problem is not with iteration process (because the last 2 for loops look exactly the same). But with the extraction values or references from my iterator.

[mbozzi]

Referring back to JLBorges's code from above, OP noticed that
for( auto& [n,str] : arr ) { /* ... */ }
doesn't compile since my_array<std::string>::const_iterator::operator* does not return an lvalue reference type.

This same issue with JLBorges' my_array<std::string> is exhibited by std::vector<bool> and some ranges like std::ranges::iota_view. To support the iterators of these ranges, consider using auto&& or auto const& instead.

for( auto&& [n,str] : arr ) 
{ 
  static_assert(std::same_as<decltype(n),   std::size_t>);
  static_assert(std::same_as<decltype(str), std::string const&>);
} 

for( auto const& [n,str] : arr )
{
  static_assert(std::same_as<decltype(n),   std::size_t const>);
  static_assert(std::same_as<decltype(str), std::string const&>);
} 

I don't see a reason to insist that auto& should work. "Use auto&&" is usual advice for generic code. See also:
https://cplusplus.com/forum/beginner/271440/