CODEWITHSUNDEEP
c++
Korchkidu
Korchkidu

Reputation: 4946

How to get the last element of an std::unordered_map?

How to get the last element of an std::unordered_map?

myMap.rbegin() and --myMap.end() are not possible.

Upvotes: 13

Views: 17851

Answers (7)

alberto
alberto

Reputation: 33

It may not be the best solution, performance-wise, but in C++11 and later, I use a combination of std::next() and size() to jump all elements from the beginning of the map, as shown below:

std::unordered_map<int,std::string> mapX;
...

if (mapX.size() > 0) {
   std::unordered_map<int,std::string>::iterator itLast =
      std::next(mapX.begin(), mapX.size() - 1);
   ...

Upvotes: 0

Kemin Zhou
Kemin Zhou

Reputation: 6891

The accepted answer seems wrong. Unordered_map does have the last element even though the key-value pair is not stored in sorted order. Since the iterator of unorered_map is forwar_iterator(LegacyForwardIterator), the cost to find the last element is O(n). Yakk - Adam gave the correct answer. Essentially, you have to iterator the container from begin to end. At each iteration, you have to check whether the next element is end(); if yes then you are at the last element.

You cannot call prev(it) or --it. There will be no syntax error, but you will have a runtime error (more likely segmentation fault) when using the prev(it) or --it. Maybe next version of compiler can tell you that you have an logic error.

Upvotes: 0

Andrei Despinoiu
Andrei Despinoiu

Reputation: 510

.end() is an iterator to the "element past the last element". That's why you compare it like this when you loop through a map:

for (auto it = myMap.begin(); it != myMap.end(); ++it) // '!=' operator here makes it possible to only work with valid elements
{
}

So you want the "last" element (whatever that may be, because it's not really guaranteed to be the last in an unordered map, since it ultimately depends on how the key was hashed and in which "bucket" it ends up in). Then you need: --myMap.end()

More specifically, .end() is a function, that returns an iterator, same as .begin() returns an iterator. Since there is no .rbegin() in an std::unordered_map, you have to use -- (the decrement operator):

auto it = --myMap.end();

To access the key you use it->first, to access the value you use it->second.

Upvotes: 1

quantdev
quantdev

Reputation: 23793

There is no "last element" in a container that is unordered.

You might want an ordered container, e.g. std::map and access the last element with mymap.rbegin()->first (Also see this post)

EDIT:

To check if your iterator is going to hit the end, simply increment it (and possibly save it in a temporary) and check it against mymap.end(), or, even cleaner : if (std::next(it) == last)

Upvotes: 14

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275405

In your comments, it appears your goal is to determine if you are on the last element when iterating forward. This is a far easier problem to solve than finding the last element:

template<class Range, class Iterator>
bool is_last_element_of( Range const& r, Iterator&& it ) {
  using std::end;
  if (it == end(r)) return false;
  if (std::next(std::forward<Iterator>(it)) == end(r)) return true;
  return false;
}

the above should work on any iterable Range (including arrays, std containers, or custom containers).

We check if we are end (in which case, we aren't the last element, and advancing would be illegal).

If we aren't end, we see if std::next of us is end. If so, we are the last element.

Otherwise, we are not.

This will not work on iterators that do not support multiple passes.

Upvotes: 2

Jashaszun
Jashaszun

Reputation: 9270

std::unordered_map::iterator last_elem;
for (std::unordered_map::iterator iter = myMap.begin(); iter != myMap.end(); iter++)
    last_elem = iter;
// use last_elem, which now points to the last element in the map

This will give you the last element in whatever order the map gives them to you.

Edit: You need to use std::unordered_map<YourKeyType, YourValueType> instead of just std::unordered_map. I just wrote it like this because you did not provide the type in your question.

Alternatively, as suggested by vsoftco (thanks), you could declare both last_elem and iter as decltype(myMap)::iterator.

(If you're compiling with the MSVC++ compiler, then you will need to add typedef decltype(myMap) map_type; and then instead of decltype(myMap)::iterator use map_type::iterator.)

Upvotes: 1

user3360398
user3360398

Reputation:

You cant. by definition, the element is not stored based on some sort of order. the key is hashed first and that's why O(1) search is possible. if you wanna check whether a key exists in the unordered_map or not, u can use this code:

std::unordered_map dico;
if(dico.count(key)!=0){
    //code here
}

Upvotes: 1

Related Questions