обмен ключами и векселями на карте

Question

У меня есть карта с (xi, f (xi)), и мои f (xi) также строго возрастают. Мне нужно обменять ключ и Vals этого пути

вход моей функции:

карты с

//keys : x0,  x1,  x2,  ...,  xn 
// vals : f(x_0) f(x1), f(x2), ...,  f(xn) 

выхода моей функции: карты с

// key : left_val f(x_0) f(x1), ...,  f(xn-1) 
// vals : x0,  x1,  x2,  ...,  xn 

(здесь left_val - входной параметр, я знаю, что он ниже f (x0)). Я знаю, что я не могу использовать правильную структуру, но мне действительно нужна вставка log (n) и уникальность упорядоченных ключей ...

Как бы вы реализовали это эффективно (т. Е. Не дублировали карту)?

Заранее спасибо.

Answer 1

Это необычная ситуация в том, что вы хотите изменить ключи std::map, которым обычно запрещено избегать изменений, которые нарушили бы порядок. Если вы уверены, что для обеспечения этого инварианта себя, то вы можете изменить std::map следующим образом:

#include <iostream> 
#include <map> 

int main() 
{ 
    typedef std::map<double, double> Mdd; 

    Mdd m; 
    m[1] = 4; 
    m[2] = 6.5; 
    m[3] = 7.2; 
    m[4] = 9.3; 
    m[5] = 12; 

    double x = 2.3; 

    for (Mdd::iterator i = m.begin(); i != m.end(); ++i) 
    { 
     double old_second = i->second; 
     i->second = i->first; 
     const_cast<double&>(i->first) = x; 
     x = old_second; 
    } 

    for (Mdd::const_iterator i = m.begin(); i != m.end(); ++i) 
     std::cout << i->first << "->" << i->second << '\n'; 
} 

Выход:

2.3->1 
4->2 
6.5->3 
7.2->4 
9.3->5 

Все это делает использовать const_cast настаивать на доступ для записи к ключу , Строго говоря, я подозреваю, что Стандарт не будет требовать, чтобы реализация работала после такого хакерства, но на практике я не могу представить реализацию, которая бы не стала. Вам нужно будет решить, что вы хотите сделать с окончательным значением x - в вашем вопросе будет f(xn) ... Я отбросил его, как было предложено вашим вопросом.

С точки зрения эффективности, это делает один проход в порядке по map, что неизбежно, если вы хотите использовать такой контейнер. Нет копий карты или дополнительных распределений кучи. После трансформации и в соответствии с предостережением выше о поддержке, не гарантируемой Стандартом, вы можете рассчитывать на «нормальную» действительную карту, в которой безопасно вставлять и удалять элементы.

Answer 2

При вводе новой записи на новую карту используйте binary search algorithm для ввода. Каждая вставка будет O (log n), а общее время воссоздания карты должно быть O (n log n).