Коллеги, добрый день! Подскажите пожалуйста по такому вопросу. 
Есть некоторый map вида:



Необходимо у него задать максимальный размер = SomeNumber.

И писать в него данные с проверкой:
Если ВЕС вставляемой пары больше самого маленького веса находящегося в  map, то вставляем эту пару в map (в конец), а пару с минимальным map выкидываем. Иначе не вставляем ничего.

Тут я меня ступор.

Изначально он пустой?


Размер ты сам задаешь или он как-то высчитывается?

Это сообщение отредактировал(а) IValdemar - 23.3.2012, 23:58

допустим в мапе лежат такие данные

нужно вставить

какую пару нужно выкинуть, какую вставить? как вообще будет выглядеть мап после такой вставки ?
расскажи поподробнее о задаче. м.б. для неё вообще не нужен мап.

вот именно

Я так понял что 

они по нему нумеруются, тогда проще использовать вектор


becks, 
Объясни подробнее

Добрый день! 
Прошу прощения, не было возможности написать раньше.



Да, изначально пустой.



Нет, я размер не задаю. Его задает юзер, по своему усмотрению.



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

Нужно использовать именно мап, он требуется для других задач потом.

Это сообщение отредактировал(а) becks - 26.3.2012, 16:29

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

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

Попробуй так:

Не думаю что это самый оптимальный вариант, но работать должен.

Решение IValdemar, имеет право на существование, но оно не эффективно.
При каждом добавлении, будет происходить пробежка по всему массиву, в поисках минимального.
Можно сделать и по-быстрее, в духе С/С++.    Но все зависит от доп. условий
I. Самый простой вариант будет если задачу можно разделить на части:

•  Заполнение контейнера.
•  Преобразование в мэп
•  Работа с мэп. (добавление здесь уже не происходит)

II Если же задачу разбить таким образом нельзя, и мэп нужен с самого начала, то просто вводим еще один индекс, упорядоченный по значениям.
  1. Самое простое, воспользоваться boost::multi_index
  2. Если аллергия на буст, можно сделать все и вручную (есть несколько способов)

volatile, А как можно ускорить? Разве что завести еще один контейнер в котором все из мапа будет упорядочено по весу, но тогда будут дополнительные расходы по памяти  
Можно по подробнее, уже самому интересно стало   

http://www.boost.org/doc/libs/1_48_0/libs/...rial/index.html
вот пример оттуда. по нему всё сразу понятно - http://www.boost.org/doc/libs/1_48_0/libs/...ample/basic.cpp

Безусловно. На доп. индекс нужна доп. память.
Но вы так поставили задачу.

Возможно там можно обойтись без мэпа, по-крайней мере из условия задачи не понятно вообще зачем он нужен.

Не я  


Я тоже так думаю. Смысла использовать ключ как порядковый номер совсем нету. Тут подойдет deque или vector.