Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > укладка в map с проверкой

Автор: becks 23.3.2012, 15:01

Коллеги, добрый день! Подскажите пожалуйста по такому вопросу.  Есть некоторый map вида: Код map<int, int> SentWeight; // ключ - номер предложения, значение его ВЕС Необходимо у него задать максимальный размер = SomeNumber. И писать в него данные с проверкой: Если ВЕС вставляемой пары больше самого маленького веса находящегося в  map, то вставляем эту пару в map (в конец), а пару с минимальным map выкидываем. Иначе не вставляем ничего. Тут я меня ступор.

Автор: IValdemar 23.3.2012, 23:56

Цитата(becks @  23.3.2012,  15:01 ) Есть некоторый map вида: Изначально он пустой? Цитата(becks @  23.3.2012,  15:01 ) Необходимо у него задать максимальный размер = SomeNumber. Размер ты сам задаешь или он как-то высчитывается?

Автор: borisbn 24.3.2012, 10:58

допустим в мапе лежат такие данные Цитата (1, 0) (2, 2) (3, 42) нужно вставить Цитата (2, 1) какую пару нужно выкинуть, какую вставить? как вообще будет выглядеть мап после такой вставки ? расскажи поподробнее о задаче. м.б. для неё вообще не нужен мап.

Автор: IValdemar 24.3.2012, 14:35

Цитата(borisbn @  24.3.2012,  10:58 ) расскажи поподробнее о задаче. м.б. для неё вообще не нужен мап.  вот именно Я так понял что  Цитата(becks @  23.3.2012,  15:01 ) ключ - номер предложения они по нему нумеруются, тогда проще использовать вектор becks,  Объясни подробнее

Автор: becks 26.3.2012, 16:28

Добрый день!  Прошу прощения, не было возможности написать раньше. Цитата Изначально он пустой? Да, изначально пустой. Цитата Размер ты сам задаешь или он как-то высчитывается? Нет, я размер не задаю. Его задает юзер, по своему усмотрению. Цитата допустим в мапе лежат такие данные (1, 0) (2, 2) (3, 42) нужно вставить (2, 1) -----> (4, 1) Да, извиняюсь что без примера, давайте только поменяем этот, как показано выше. Причина : в мап кладутся номер предложения и его вес, т.е. номер предложения уникален и в каждой новой паре он на единицу больше чем в предыдущей. Теперь вернемся к вставке. У вставляемой пары номер предложения = 4, вес = 1. В мапе находим минимальный вес: он равен 0, и соответсвтует 1 предложению.  Минимальный вес меньше веса в вставляемой паре. Удаляем запись (1, 0) из мапа и вставляем в конец (4, 1). Итог: (2, 2) (3, 42) (4, 1) Нужно использовать именно мап, он требуется для других задач потом.

Автор: borisbn 26.3.2012, 17:11

becks, в твоём контейнере в каждый момент времени будет только один элемент, а в итоге останется элемент с максимальным весом. рассмотрим мой пример (подправленный тобой) 1. [] 2. [ (1, 0) ] <-- вставляем элемент, т.к. больше ничего нет 3. [ (2, 2) ] <-- удаляем (1, 0), т.к. его вес меньше 2 4. [ (3, 42) ]  <-- удаляем (2, 2), т.к. его вес меньше 42 5. [ (3, 42) ] <-- НЕ вставляем элемент (4, 1), т.к. его вес меньше минимального

Автор: becks 26.3.2012, 17:30

Вы забыли про размер контейнера, этап №2 мы будем производить пока не заполним его полностью.... при добавлении новых уже будем производить проверку..

Автор: IValdemar 27.3.2012, 00:37

Попробуй так: Код #include <iostream> #include <map> using namespace std; int main() {     map<int,int> pocket;     pair<int,int> minVal;     int nsize;     cin>>nsize; //Юзер ввел размер массива     if(nsize==0) return 0; //размер в 0 маловат     ++nsize;     int nweight;     //Вводим первый элемент отдельно     cin>>nweight;     pocket[1]=nweight;     minVal=make_pair(int(1)/* int нужно указывать, иначе компилятор подумает что 1 имеет тип short  */,nweight);//Первый элемент, пока что он минимальный     for(int i=2; i!=nsize; i++)     {         cin>>nweight;         pocket[i]=nweight;         if(nweight<minVal.second) minVal=make_pair(i,nweight);     }     /*     Теперь у нас в map'e хранятся элементы которые ввел юзер     а в minVal хранится ключ и вес наименьшего элемента     при последующих вставках надо проверять вес вставляемого элемента     с весом минимального элемента и удалять минимальный если надо     */     int key,mass;     while(!cin.eof())//Пока что-то есть в потоке ввода     {         cin>>key>>mass;         if(mass<=minVal.second) continue;         //Новый элемент надо вставлять         pocket.erase(pocket.find(minVal.first));//Удаляем минимальный элемент         pocket[key] = mass;//Вставили новый элемент         //Теперь надо найти минимальный         minVal=make_pair(key,mass);         for( map<int,int>::iterator p = pocket.begin(); p!=pocket.end(); ++p)         {             if(p->second<minVal.second) minVal=make_pair(p->first,p->second);         }         //Теперь в minVal снова минимальный элемент     }     return 0; } Не думаю что это самый оптимальный вариант, но работать должен.

Автор: volatile 27.3.2012, 01:17

Решение IValdemar, имеет право на существование, но оно не эффективно. При каждом добавлении, будет происходить пробежка по всему массиву, в поисках минимального. Можно сделать и по-быстрее, в духе С/С++.    Но все зависит от доп. условий I. Самый простой вариант будет если задачу можно разделить на части:  Заполнение контейнера.  Преобразование в мэп  Работа с мэп. (добавление здесь уже не происходит) II Если же задачу разбить таким образом нельзя, и мэп нужен с самого начала, то просто вводим еще один индекс, упорядоченный по значениям.   1. Самое простое, воспользоваться boost::multi_index   2. Если аллергия на буст, можно сделать все и вручную (есть несколько способов)

Автор: IValdemar 27.3.2012, 13:05

Цитата(volatile @  27.3.2012,  01:17 ) Можно сделать и по-быстрее, в духе С/С++. volatile, А как можно ускорить? Разве что завести еще один контейнер в котором все из мапа будет упорядочено по весу, но тогда будут дополнительные расходы по памяти   Можно по подробнее, уже самому интересно стало

Автор: borisbn 27.3.2012, 13:07

Цитата(IValdemar @  27.3.2012,  13:05 ) Можно по подробнее, уже самому интересно стало Цитата(volatile @  27.3.2012,  01:17 )  Самое простое, воспользоваться boost::multi_index http://www.boost.org/doc/libs/1_48_0/libs/multi_index/doc/tutorial/index.html вот пример оттуда. по нему всё сразу понятно - http://www.boost.org/doc/libs/1_48_0/libs/multi_index/example/basic.cpp

Автор: volatile 27.3.2012, 23:25

Цитата(IValdemar @  27.3.2012,  13:05 ) тогда будут дополнительные расходы по памяти   Безусловно. На доп. индекс нужна доп. память. Но вы так поставили задачу. Возможно там можно обойтись без мэпа, по-крайней мере из условия задачи не понятно вообще зачем он нужен.

Автор: IValdemar 28.3.2012, 13:20

Цитата(volatile @  27.3.2012,  23:25 ) Но вы так поставили задачу. Не я   Цитата(volatile @  27.3.2012,  23:25 ) Возможно там можно обойтись без мэпа, по-крайней мере из условия задачи не понятно вообще зачем он нужен. Я тоже так думаю. Смысла использовать ключ как порядковый номер совсем нету. Тут подойдет deque или vector.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)