-2

I need to get the last element from an unordered_set, and it must be using the unordered_set, not any other class. (mostly because I'm to modify lots of code already done) but by what I've been looking the only possible way is iterate over it and save the element and then return it. But in big sets it would be too slow. besides I tried this and did not work.

unordered_set <int>::iterator it = frames.end();
--it;

I got the following error: "no match for 'operator--' in '--it'"

Its kind of useful mostly because of this, it stores the data in a "stack" way, as following:

unordered_set<int> s;
s.insert(9);
s.insert(4);
s.insert(8);
s.insert(0);
s.insert(1);

unordered_set<int>::iterator it = s.end();
for( it = s.begin();  it!= s.end(); ++it )
    cout << *(it) << " ";

it prints:"1 0 8 4 9"

So the "last" element would be always 9, it is the "first" element that was inserted, as I said before in a "stack" way.

Any idea to improve it?

bones.felipe
  • 586
  • 6
  • 20
  • 12
    Define what the "last" element of an ***unordered*** set is. – Xeo Jun 09 '13 at 23:02
  • 1
    What exactly do you mean by "last" element? There is no guaranteed order (hence the name)... – Oliver Charlesworth Jun 09 '13 at 23:02
  • 4
    @templatetypedef: I believe `unordered_set` only has forward iterators (http://ideone.com/HmSbD3). – Oliver Charlesworth Jun 09 '13 at 23:03
  • @templatetypedef unordered_set has no reverse iterator – prajmus Jun 09 '13 at 23:04
  • I got the following error: no match for 'operator--' in '--it' – bones.felipe Jun 09 '13 at 23:05
  • @templatetypedef: An `std::unordered_anything` only provides forward-iteration. – Xeo Jun 09 '13 at 23:06
  • And giving an answer to Oli, its because if we look careful the unordered_set store the info in a "stack" way, thus "last" element would be the bottom of the "stack". – bones.felipe Jun 09 '13 at 23:09
  • @Xeo: Same as the "leader of the anarchists", non? – Kerrek SB Jun 09 '13 at 23:12
  • @Xeo so it means that I can't access to the last iterator? – bones.felipe Jun 09 '13 at 23:13
  • 2
    The short answer is that if you need/want to do that, you probably want to use something other than `unordered_set`. The only way to access the last iterator is to walk through all the others to get there, which is obviously quite inefficient. – Jerry Coffin Jun 09 '13 at 23:13
  • @bones.felipe: Regarding "stores the info in a stack way", there is no guarantee that it will behave in this manner. If you rely on that behaviour, you **must** choose a different container type. – Oliver Charlesworth Jun 09 '13 at 23:15
  • Well thats exactly what I thought... but I would have to change a lot of code... – bones.felipe Jun 09 '13 at 23:16
  • 1
    @bones.felipe: `unordered_set` does not do at all what you think it does. In VS11 on my system, for example, your code prints "1 9 4 0 8". Add a bit more numbers on your own implementation, and I can pretty much guarantee you won't continue to see that stack-like behavior. – Benjamin Lindley Jun 09 '13 at 23:18
  • @BenjaminLindley well that's kind of weird... I'm using TDM GCC 4.7.1 and I did a lot of tests using it in LRU Algorithm implementation and it behaved in that Stack-like behavior. But what you said its pretty interesting, any idea about why? – bones.felipe Jun 09 '13 at 23:24
  • 2
    @bones.felipe: Because there are no such guarantees in the language standard. And the fact that the underlying implementation is basically a hash-table, which has nothing to do with a stack ;) – Oliver Charlesworth Jun 09 '13 at 23:26
  • What Oli said, and try [this code](http://ideone.com/pPcvVv) on your system. – Benjamin Lindley Jun 09 '13 at 23:30
  • Ok, I see, so it seems I was just lucky. Anyway, because of the " forward-iteration" I can't access directly into the last element of the set no matter the underlying implementation? – bones.felipe Jun 09 '13 at 23:30
  • It prints this @BenjaminLindley http://pastebin.com/SJnbfJSk – bones.felipe Jun 09 '13 at 23:34
  • It is better if you stop thinking of a *last* element. Assume no ordering. – juanchopanza Jun 09 '13 at 23:38
  • Ok guys I got it, there's no reason to behave in that "stack" way. Its better to choose another data structure. Thanks to everyone! – bones.felipe Jun 09 '13 at 23:40

1 Answers1

3

In an unordered_set, the order of inserts does not necessarily correspond to the order that you will get when the set is iterated (hence the name "unordered"). Part of the reason why a bi-directional iterator is not supported (using a -- operator) in this data structure is because being able to go backwards/forwards on an unordered_set doesn't make any difference when you don't know what the order of the elements that you will get out of it.

The order of inserts that you have created does not dictate the order you will get when you iterate (inserting "9" first doesn't mean s.end() would return a "9"). This is because what dictates that order solely depends on how that set calculates the hash value of each object you insert, similar to a hash table. Hence, you cannot reliably use this set to replicate a "stack", as this is not what this particular data structure is meant to be used for.

There are other C++ STL data structures that you can use to preserve order such as std::stack.

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Alkaiser Trenken
  • 91
  • 2