Найти два больших значения для одного ключа в мультикарте - PullRequest
Новая
       23

Найти два больших значения для одного ключа в мультикарте

0 голосов
/ 24 апреля 2018

У меня есть мультикарта, состоящая из ключа, который является парой целых чисел, а значения ключей являются числами с плавающей запятой.Теперь я хочу иметь 2 самых больших значения для всех моих ключей.
В моем примере ключ (1, 1) должен привести к значениям 5.8 и 3.7.
Ключ (2, 2) должен привести к 2.4 и 1.5.
Чтобы указать на это: Я не знаю количество и внешний вид моих ключей.Поэтому я не знаю, существует ли ключ (2, 2).

Вот код: 

int main(int argc, char** argv)
{
    // Create some values - both vectors have the same size
    // The pairs and the thetas may be unsorted
    vector<pair<int, int>> pairs;
    pairs.push_back(make_pair(1, 1));
    pairs.push_back(make_pair(1, 1));
    pairs.push_back(make_pair(1, 1));
    pairs.push_back(make_pair(2, 2));
    pairs.push_back(make_pair(2, 2));
    pairs.push_back(make_pair(3, 3));
    pairs.push_back(make_pair(3, 3));
    pairs.push_back(make_pair(1, 1));

    vector<float> theta;
    theta.push_back(1.4);
    theta.push_back(2.4);
    theta.push_back(3.7);
    theta.push_back(2.4);
    theta.push_back(1.5);
    theta.push_back(1.6);
    theta.push_back(2.4);
    theta.push_back(5.8);

    multimap<pair<int, int>, float> similarities;

    for (size_t i = 0; i < pairs.size(); i++) {
        similarities.insert(make_pair(make_pair(pairs[i].first, pairs[i].second), theta[i]));
    }

}

В моем конкретном случае я не знаю, какие пары ключей определены вмоя мультикартаЯ также думаю, что, возможно, мультикарта не является правильным выбором, но я не уверен, что это лучший тип.
Я пытался сохранить векторный формат тета, но тогда сложно отследить соответствующие пары.

Ответы [ 2 ]

0 голосов
/ 24 апреля 2018

У вас есть несколько вариантов здесь.

  • Сохраните существующий multimap и просто выполните линейный поиск по значениям, чтобы найти два самых больших.
  • Используйте map<pair<int, int>, set<float, std::greater<float> > >вместо этого, а затем первые два элемента сразу же становятся доступными после поиска ключа.
  • Используйте map<pair<int, int>, vector<float> > и сохраняйте вектор отсортированным при вставке.Лучше, когда выполняется больше поисков, чем вставок.
  • Используйте map<pair<int, int>, vector<float> > и partial_sort первые два элемента, когда нужно получить два старших значения.Лучше делать больше вставок, чем искать.
0 голосов
/ 24 апреля 2018

Надеюсь, я вас правильно понял: 

auto range = similarities.equal_range(make_pair(1,1));

size_t found = 0; float highest, second_highest;

if (range.first != similarities.end() && range.first != range.second) {
  ++found;
  highest = (*std::max_element(range.first++, range.second)).second;
  if (range.first != range.second) {
    ++found;
    second_highest =
      (*std::max_element(range.first++, range.second, [&](auto a, auto b){ return a.second < b.second && b.second < highest; })).second;
  }
}

if (found > 0)
  std::cout << highest<< std::endl;
if (found > 1)
  std::cout << second_highest << std::endl;

Вышеприведенное не даст вам одно и то же значение дважды.

...