Reverse iterators, how to use them?

C4DS

Hi,

Was looking for a way to get the first and last item in an HashMap.
Since the values of the keys are sorted, the first would represent the entry with lowest key, and the last item would be the one with highest key.

To obtain the lowest I use HashMap::Begin().GetKey().
Knowing that std::map has a rbegin() and rend(), I could iterate the hashmap in reverse to get the first of the reversed iteration, which would thus be the entry with highest key. But I don't see any RBegin() in the documentation.

Call me stupid (yes you can), but the available ReverseIterator documentation doesn't ring a bell how to actually use it. Nor does any cinema4dsdk sample use it. And a search on this forum does provide any hit neither.

Should I simply do:

maxon::HashMap<Int32, Int32> my_map;

const Int32 lowestKey = my_map.Begin().GetKey();
const Int32 highestKey = (++ReverseIterator(my_map.End())).GetKey();

Seems logical ... but then again, I have been know to have a twisted logic.
Please, enlighten me. Thanks in advance.

Edit:
just noticed, since reverse iterator would provide the first (in reverse), my sample code would probably better be written as:

maxon::HashMap<Int32, Int32> my_map;

const Int32 lowestKey = my_map.Begin().GetKey();
const Int32 highestKey = ReverseIterator(my_map.End()).GetKey();

No need for the ++ since that would give us the penultimate highest value ... I think.

C4DS

Well, I was wrong.
In contrary to the std::map which does sort the entries by its key value, the maxon::HashMap does not sort its entries. As such, getting the first entry did not result in obtaining the lowest value.

While the question about how to use the ReverseIterator is still a valid one, it is out of context of what I am trying to achieve with it.

Guess in order to obtain the lowest and highest key, I will need to iterate over the whole hashmap? Maybe food for another thread?

m_adam

Hi @C4DS, as you figured it out HashMap doesn't store order.

So your best bet is to translate the thing into a Collection that actually supports order such as BaseArray and then sorts it using a BaseSort.
Finally, I was neither able to use ReverseIterator and there is no use of it in our code base so I've asked the development team about it.
But you can use maxon::Iterable::Reverse.

Here an example:

// Creates a Hash map
// 2 - C E
// 1 - A D F
// 3 - B
// 
maxon::HashMap<maxon::Int, maxon::String> letters;
auto entry = &letters.InsertMultiEntry(2) iferr_return;
if (entry)
	entry->SetValue("C"_s);

entry = &letters.InsertMultiEntry(2) iferr_return;
if (entry)
	entry->SetValue("E"_s);

entry = &letters.InsertMultiEntry(1) iferr_return;
if (entry)
	entry->SetValue("A"_s);

entry = &letters.InsertMultiEntry(1) iferr_return;
if (entry)
	entry->SetValue("D"_s);

entry = &letters.InsertMultiEntry(1) iferr_return;
if (entry)
	entry->SetValue("F"_s);

letters.Insert(3, "B"_s) iferr_return;

ApplicationOutput("Raw Hash Map"_s);
for (const auto& e : letters)
{
	const maxon::Int&    key = e.GetKey();
	const maxon::String& value = e.GetValue();
	ApplicationOutput("@, @", key, value);
}

// Create a Base Array that will store a Pair of data ordered by ID and then by letter using a BaseSort Later
// First fed the BaseArray from the HashMap
maxon::BaseArray<maxon::Pair<maxon::Int, maxon::String>> orderedLetters;
for (const auto& e : letters)
{
	const maxon::Int&    key = e.GetKey();
	const maxon::String& value = e.GetValue();
	orderedLetters.Append(maxon::Pair<maxon::Int, maxon::String>(key, value)) iferr_return;
}

// Sort the Array using a BaseSort
class MyCustomSort : public maxon::BaseSort<MyCustomSort, maxon::BASESORTFLAGS::NONE>
{
public:
	static inline Bool LessThan(maxon::Pair<maxon::Int, maxon::String> a, maxon::Pair<maxon::Int, maxon::String> b)
	{
		// If a and B are not the same return the lowest
		if (a.GetFirst() != b.GetFirst())
		{
			return a.GetFirst() < b.GetFirst();
		}

		// If there are the same then return by stored value
		return a.GetValue() < b.GetValue();
	}
};

// Sort the array
MyCustomSort sort;
sort.Sort(orderedLetters);

ApplicationOutput("Sorted Base Array"_s);
for (const auto& entry : orderedLetters)
	ApplicationOutput("@: @", entry.first, entry.second);	


// Reverse it
ApplicationOutput("Reversed Sorted Base Array"_s);
for (const auto& entry : maxon::Iterable::Reverse(orderedLetters))
	ApplicationOutput("@: @", entry.first, entry.second);

Cheers,
Maxime.

C4DS

@m_adam said in Reverse iterators, how to use them?:

maxon::Iterable::Reverse

Thanks for pointing that out, found it in the documentation ... once you know what to look for.

As for using a sortable collection, I will instead simply iterate over the hashmap and collect the necessary information. This will provide the same end result.
I simply assumed that HashMap was similar to the std::map, which it obviously is not.
A note in the documentation mentioning how it internally will not sort the data, might be useful for others as well.

I will set this post as solved, but feel free to comment about feedback from development team about the ReverseIterator.

C4DS

I have "unsolved" the topic, as there still is an open point to be clarified.

From the documentation:

static maxon::details::ReverseIterable<ITERABLE> Reverse ( ITERABLE && iterable )

This function can be used in a range-based for loop to reverse the iteration such that it starts at the last element of the #iterable and moves towards the first element. The function can only be used for iterables which have suitable RBegin and REnd functions, and for C++ arrays.

Apparently only the BaseArray can be used with the Iterable::Reserve. Nor HashSet, nor HashMap can be compiled using the reverse iterator, and probably because they have no RBegin() nor REnd().
Still, when I look at the documentation of BaseArray I don't see any RBegin(), nor REnd(). So how to know which collection type can be used with Iterable::Reverse ?

m_adam

The HashMap/HashSet iterator does not provide a it-- (as used in the Iterable::Reverse) but only it++ as you can see in https://developers.maxon.net/docs/cpp/2023_2/classmaxon_1_1_hash_map_1_1_iterator_template.html#ab6054287e6f409207af3fa16e49046ad

Cheers,
Maxime.

m_adam

Hi @C4DS

Here the message from the development team which confirms what I said to you previously.

maxon::Iterable::Reverse used RBegin/REnd in the beginning, but not nowadays and the documentation wasn’t adapted. (I will fix this).
maxon::Iterable::Reverse just needs -- and only works for range-based for loops (it does the decrement in operator*, so a use outside of range-based for loops is risky because you might use operator* more than once).
So I’d say ReverseIterator/RBegin/REnd is still useful for non-ranged-based reverse loops, but there’s no such use case in our code base.

HashMap doesn’t support -- so you can’t use a reverse iterator for that.
It wouldn’t make sense anyway because HashMap iteration is unordered.

Cheers,
Maxime.

C4DS

@m_adam said in Reverse iterators, how to use them?:

Hi @C4DS

Here the message from the development team which confirms what I said to you previously.

Hi Maxime,
I didn't doubt what you said earlier.
I only wanted to point out that it wasn't clear from reading the documentation which collection could be used with reverse iterators.
It's nice mentioning in the documentation about RBegin/REnd, Range based loops, etc ... but not everyone looks into the collection implementation to see which types do have RBegin/REnd or are range based, ...

HashMap doesn’t support -- so you can’t use a reverse iterator for that.
It wouldn’t make sense anyway because HashMap iteration is unordered.

Having used std::map some might expect HashMap to be ordered, but it isn't mentioned anywhere it isn't.

But the point has been made, and it is now clear how to use reverse iterator.
Topic well be closed as "solved".