как найти средний элемент карты ?? СТЛ

Question

Привет, я застрял между концепцией Map в 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 << " ";
}

Теперь, когда я напечатал эту карту, она была напечатана в отсортированном порядке. Есть ли самый простой способ найти середину этой карты ..... Нужно найти медиану более крупной проблемы ... Поэтому пытаемся реализовать сбалансированное бинарное дерево поиска ..

Answer 1

С указанным кодом вы злоупотребляете картой для сортировки ключей.

Вы можете добиться гораздо большей производительности, избегая полной сортировки и копирования:

   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;

Если вы предпочитаете использовать контейнеры STL, ваш код будет выглядеть следующим образом (при условии, что контейнер с итераторами произвольного доступа):

   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;

Answer 2

map - это сбалансированное дерево поиска. Чтобы найти его середину - найдите его размер и итерируйте от begin() для половины его размера - это будет середина. Как то так:

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

// now after the loop it is the median.

Если вы используете map для сортировки - тогда это излишество, ИМХО. Вы можете сделать это намного эффективнее с массивом (или vector), и тогда поиск середины также будет тривиальным. map используется для доступа к данным по ключу, а не только для сортировки.

Answer 3

std::map может быть не лучшим контейнером для определения медианы.Но это будет довольно просто:

it = bst.begin();
advance( it, bst.size() / 2);
cout << endl << "median: " << it->first << endl;

Answer 4

std :: maps не может дать вам медианы за один выстрел. Если вы хотите медианы, вам нужно использовать этот алгоритм .