1

I am beginner.Let suppose I create 

 map<int, node*> mp;

where a node is 

struct node{
node *previous;
int key; // I have no idea why there is a key variable in this node
int value;
node *next
};

So the map has int key, points to the node of a doubly linked list.

Let suppose I inserted the following elements in the order. 

<key,(let corresponding node.value element be)>  
<5, 1>
<10,2>
<8, 3>

So the doubly linked list looks like: 

1<->2<->3

Now if I want to insert a new node in between existing nodes with node values 2,3. And so I created a new map element. 

<key,(let corresponding node.value element be)>  
<7, 4>

And the (newly adjusted) doubly linked list looks like:(as per my requirement) 

1<->2<->4<->3

Which element will mp.erase(mp.end()); delete,and why?

I wrote a sample program in which map element <8,3> is deleted.Why does this happen?

FYI: I am working for the LRUcache code.

sql_dummy
  • 715
  • 8
  • 23
  • 2
    `map.erase(map.end());` is an error; end-iterators represent a singular state (e.g. past-the-end or a special state). Maps don't preserve the insertion order; if you delete the last element of a map then it will be the one with the largest sort key – M.M Feb 27 '16 at 09:55
  • @M.M but it works very much fine for me.It is deleting an element – sql_dummy Feb 27 '16 at 09:57
  • About the sort order: [std::map, how to sort by value, then by key](http://stackoverflow.com/questions/19842035/stdmap-how-to-sort-by-value-then-by-key) – t.niese Feb 27 '16 at 09:57
  • @t.niese but according to sorted order of keys <10,2> is the last element, the why does the command delete <8,3> in my program. – sql_dummy Feb 27 '16 at 10:01
  • 3
    As @M.M said `map.erase(map.end());` is an _error_ and results in an undefined behaviour: [map.erase( map.end() )?](http://stackoverflow.com/questions/952888/map-erase-map-end) or [std::map::erase](http://en.cppreference.com/w/cpp/container/map/erase) `[...]The iterator pos must be valid and dereferenceable. Thus the end() iterator (which is valid, but is not dereferencable) cannot be used as a value for pos.[...]` – t.niese Feb 27 '16 at 10:03
  • 1
    @sql_dummy see [What is undefined behaviour?](http://stackoverflow.com/a/4105123/1505939) – M.M Feb 27 '16 at 10:07
  • 2
    *"I read map.erase(map.end()); deletes the last element of the map"*. That is incorrect. Where did you read it? – juanchopanza Feb 27 '16 at 10:15
  • @M.M thanks for the link – sql_dummy Feb 27 '16 at 12:51

2 Answers2

3

First, map.end():

Returns an iterator referring to the past-the-end element in the map container.

past-the-end element is a virtual element (that is, it actually doesn't exist). It represents the element just after the last valid element of the map.

If you ask, why a virtual element? Shouldn't map.end() actually mean the last element present?

This is because most of the operations that involve the C++11 containers like map, set, vector etc. specify their operations as [ ) which means that whenever you supply a range to any operation, that range is interpreted as: First element included, last element not.

Example, [2,5) means operation has to be performed on 2,3,4.

Second, when you call mp.erase(element), this element has to be a valid and dereferencable element. But you are specifying map.end() to it.

mp.erase(mp.end()) must not work.

Coming back to your question, TL;DR:

Map doesn't keep a record of insertion order.

So deleting from the end means deleting the last element present in the map, sorted by the key.

Akshay Arora
  • 1,953
  • 1
  • 14
  • 30
2
map<int, node*> mp;
mp.insert(make_pair(5, nullptr));
mp.insert(make_pair(10, nullptr));
mp.insert(make_pair(8, nullptr));

std::map is internally sorted by it's key, by default in ascending order, using std::less<Key>. Therefore, the second value, which could be anything, does not matter.

mp.erase(--mp.end());
// or
mp.erase(std::prev(mp.end(), 1));

Should always the delete the pair with the key "10", not the one with the key "8" as you may think.

Jts
  • 3,447
  • 1
  • 11
  • 14