Reverse iterators, how to use them?
-
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.
-
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?
-
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. -
@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 thatHashMap
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
. -
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 theIterable::Reserve
. NorHashSet
, norHashMap
can be compiled using the reverse iterator, and probably because they have no RBegin() nor REnd().
Still, when I look at the documentation ofBaseArray
I don't see any RBegin(), nor REnd(). So how to know which collection type can be used with Iterable::Reverse ? -
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. -
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. -
@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".