Обратное отображение функциональных отношений (c ++)

Question

Я использую простую функцию (y (x)) и хочу сгенерировать значение x из определенного значения y. Хотя обычно обратное отображение не дает единственного значения x, я использую максимум из моих значений y. Это означает, что для введенного мной значения y будет уникальное значение x (максимальное). Я не понимаю, как закодировать это в C ++

Answer 1

Если я правильно понимаю, вам дан конечный диапазон значений x , скажем x[0], x[1], ..., x[N], и функция f, и вы хочу найти индекс k, для которого f(x[k]) является наибольшим из возможных. В этом случае простой поиск будет делать:

size_t k = 0;
T m = f(x[k]);
T tmp;

for (size_t i = 1; i <= N; ++i)
{
  if ((tmp = f(x[i])) > m)
  {
    k = i;
    m = tmp;
  }
}

// Maximum is (x[k], m)

Здесь T - это тип, такой что f равен T f(T);

Answer 2

Если вам не нужна интерполяция, только точный обратный поиск, то это относительно просто:

std::map<YType, XType> lookup;
// (code to read the file goes here)
// for each x {
    YType y = f(x);
    if ((lookup.count(y) == 0) || (lookup[y] < x)) {
        lookup[y] = x;
    }
// }

Тогда ваш обратный поиск просто lookup[y], который вернет 0 (или построенный по умолчанию)значение, где это применимо) если y фактически отсутствовало в данных.

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

typedef std::map<YType, XType> maptype;
typedef std::pair<maptype::iterator, bool> resulttype;

resulttype result = lookup.insert(std::make_pair(y, x));
if (!result.second) {
    // key already existed, so value was not inserted. Check for max.
    maptype::iterator pos = result.first;
    if ((*pos).second < x) {
        (*pos).second = x;
    }
}