how to find the middle element of the map?? STL

Question

Hi I am stuck in between the concept of Map in STL Library/C++.

int arr[] = {10,15,14,13,17,15,16,12,18,10,29,24,35,36};
int n = sizeof arr / sizeof *arr;

map<int, bool> bst;
map<int, bool>::iterator it;
vector<int> median_output;

const int k = 5;
for (int i = 0; i < k; ++i) {
    bst.insert(make_pair(arr[i], true));
}

for (it = bst.begin(); it != bst.end(); it++) {
    cout << (*it).first << " ";
}

Now when i printed this map, it got printed in sorted Order. Now is there any simplest way to find the middle of this map..... Need to find the median of a bigger problem... So trying to implement balanced binary search tree..

Answer 1

map is a balanced search tree. To find it's middle - find it's size, and iterate from the begin() for half it's size - that will be the middle. Something like this:

for (it = bst.begin(), int middle = 0; middle < bst.size()/2; it++, middle++) {
    cout << (*it).first << " ";
}

// now after the loop it is the median.

If you use map to sort things - then it's an overkill, IMHO. You can do it much more effectively with an array (or vector), and then finding the middle will be trivial as well. map is used for accessing data by key, not just sorting.

Answer 2

With the code shown you are abusing the map to sort the keys.

You can get much more performance, avoiding full sort and copy:

   const int len = 14;
   const int a[len] = {10,15,14,13,17,15,16,12,18,10,29,24,35,36};

   std::nth_element( a, a+len/2, a+len );
   std::cout << "Median: " << a[len/2] << std::endl;

If you prefer to use STL containers, your code would look like this (assuming a container with random access iterators):

   std::vector<int> v( a, a+len );
   std::nth_element( v.begin(), v.begin()+len/2,v.end() );
   std::cout << "Median: " << v[len/2] << std::endl;