C++. Получить минимум вектора по ключу

Question

хотел бы узнать эффективный способ нахождения значения минимума в векторе по некоторому ключу. Конкретная задача: есть структура Thing с полями a1, a2, b; в векторе Thing's найти Thing, у которого сумма (a1+a2) минимальна. Вернуть нужно целое число (a1+a2)

#include <iostream>
#include <vector>
using namespace std;

struct Thing {
    int a1;
    int a2;
    int b;
};


int main()
{
    vector<Thing> things;
    things.push_back({1, 7, 3});
    things.push_back({5, 2, 6});
    things.push_back({7, 5, 2});
    cout << min(/*return minimum value of (a1+a2)*/); // must return 7
    return 0;
}

Answer 1

Ну в векторе для такой специфической задачи действительно эффективных средств нет, придётся перебирать всё или вручную, или с помощью max_element c нужным компаратором, если не введено специальное упорядочивание.

А вот если реальная проблема требует постоянно знать этот самый минимум, то может помочь очередь по приоритетам

Answer 2

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Thing {
    int a1;
    int a2;
    int b;
    };

// В ручную
int min(const vector<Thing>& T) {
    int m = INT_MAX;

    for (auto t : T)
        if (t.a1 + t.a2 < m) m = t.a1 + t.a2;

    return m;
    }

// Стандартный алгоритм
int mins(const vector<Thing>& T) {
    auto mit = min_element(T.begin(), T.end(),
    [](const Thing & a, const Thing & b) {
        return a.a1 + a.a2 < b.a1 + b.a2;
        });
    return mit->a1 + mit->a2;
    }


int main() {
    vector<Thing> things;
    things.push_back({1, 7, 3});
    things.push_back({5, 2, 6});
    things.push_back({7, 5, 2});
    cout << min(things) << endl;  // must return 7
    cout << mins(things) << endl; // must return 7
    }

БЛОГ НА HUSL

C++. Получить минимум вектора по ключу

Ответы (2 шт):