#include <iostream>
#include <cstdlib>
// Just to explore using a map
// A map is used to keep a collection of keys each with an  associated values.
// insertion, retrieval and delete are all O(log n)
// for example we could associate a student id with a mark
// and the collection of these could be stored in a map
// such that we could retrieve a given studentid's mark
// in O(log  n) where n is number of entries in the map
using namespace std;
#include <map>


int main()
{
  map <string,int> results;   // each entry in map will be a string (the key == studentid) and an int (mark)
  map <string,int> ::iterator it;  // an iterator to search through the map
  string stdid;
  int mark;
  cout << "Enter student id and mark  - terminate with control-d" << endl;
  while (cin >> stdid >> mark)
     results.insert(make_pair(stdid,mark));  // we combine the studentid and the mark into an entry
                                             // and insert into the map

  // now can display the whole thing in order of student id 
  
  cout << " Results "<< endl;
  for (it = results.begin(); it != results.end(); it++)
    cout << it->first << ' ' << it->second <<endl;

  // experiment with displaying the map in reverse order
  // use a reverse iterator for this 
  // to retrieve a particular student's marks
  // .... complete


  // now can retrieve in O(log n) time where n is number
  // of entries in map
  cout << "Enter studentid  ";
  cin.clear();  // clears previous end-of-file which we used to terminate data entry
  cin >> stdid;
  it = results.find(stdid);  // set iterator to point to entry if found
  if (it != results.end())
    cout << "mark for " << it->first << " is " << it->second << endl;
  else
    cout << stdid << " not found " << endl; 
    // iterator beyond end of map means that given key wasn't found
  system("pause");
  return 0;
  
}