Здравствуйте, e-Xecutor, Вы писали:

EX>Как ты себе представляешь смену map на vector?

Эээ, например так. (только это скорее замена multimap'у)

//вставка
cont.insert(lower_bound(cont.begin(),cont.end(),value,KeyLess()),value);

//поиск
pair<key_t,value_t> value = { key, value_t() };
cont_t::iterator i = lower_bound(cont.begin(),cont.end(),value,KeyLess());
if ( i != cont.end() && i->first == value.first ) // нашли

//удаление
pair<key_t,value_t> value = { key, value_t() };
pair<cont_t::iterator> e = equal_range(cont.begin(),cont.end(),value,KeyLess());
cont.remove(e.first,e.second);

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

Кстати, когда-то давно встречался с задачей реализовать свою функцию void* malloc(size_t s)? Может кто-нибудь дать ссылки по теме? Ещё интересует реализация функций работы с кучей на базе массива. Хотелось бы просветиться прежде чем копаться в исходниках(malloc.c etc.) Tnx!

Здравствуйте, Wind, Вы писали:

W>Но вот незадача, после удаления элемента итераторы становятся не действительными, значит их нужно задать заново и с элемента .begin() заново начать поиск (заново, т.к. ни кто гарантий не дает, как будут располагаться элементы. Или я не прав?) Это потенциально долго, а на ключи полагаться нельзя, т.к. в момент работы алгоритма значения ключей не известны.

Ты не прав.
Контейнеры list, set, map не переупорядочивают элементы при удалении/вставке, и не перемещают их в памяти.
То есть все итераторы (кроме относящихся к удаляемым) остаются валидными, а порядок следования сохраняется.

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

struct no_action
{
  template<class T> void operator()(T& t) const {}
};

template<class C, class P, class U>
void erase_if(C& cont, P pred, U utilize = no_action())
{
  C::iterator i=cont.begin(), j, e=cont.end();
  while(i!=e)
  {
    if(pred(*i))
    {
      j=i; // запомним итератор на текущий элемент
      ++i; // вскоре текущая позиция будет невалидна, поэтому спешим оттуда убраться
      utilize(*j);
      cont.erase(j);
    }
    else
      ++i;
  }
}

Другое дело, что может оказаться, что удаление элемента сопровождается добавлением других (из недр кода деструктора).
В этом случае, чтобы не зациклиться, может оказаться полезным двухфазное удаление: сперва получить список итераторов на удаляемые элементы, затем их всех перестрелять.

Вообще-то правильное удаление из map — это erase по ключу. Каков
критерий удаления? Определяется по содержимому СЛОЖНОЙ_СТРУКТУРЫ? Тогда
стоит попытаться формировать список ключей удаляемых элементов
(set<int>) и проходить по нему, удаляя соотв. элементы map.

Wind wrote:

> у меня есть std::map <int, СЛОЖНАЯ_СТРУКТУРА> a. Периодически
> возникает задача удаления не нужных записей, причем таких записей
> может быть несколько и расположены они могут быть в произвольных
> местах. Алгоритм, который мне пришел в голову: 1) Перебираю каждый
> элемент списка на соответствие некоторым условиям 2) Встретился
> элемент, который нужно удалить — удалил его и продолжил искать далее

Здравствуйте, TheBeard, Вы писали:

TB>Вообще-то правильное удаление из map — это erase по ключу. Каков
TB>критерий удаления? Определяется по содержимому СЛОЖНОЙ_СТРУКТУРЫ? Тогда
TB>стоит попытаться формировать список ключей удаляемых элементов
TB>(set<int>) и проходить по нему, удаляя соотв. элементы map.



В любом случае ты сперва тратишь O(N) времени на обход контейнера от begin() до end(), получая либо список итераторов, либо список ключей элементов, подлежащих удалению.
Затем ищешь каждый элемент за время O(1) если итератор, либо O(log N) если ключ — выполняется поиск.
После чего удаляешь элемент за O(log N) (перебалансировка).

Вопрос: зачем платить больше?

Почему пропускться
на следующей итерации for выполнит it++
и все будет ок пример
мар:
1, объект
2, объект
3, объект
4, обьъект

на каком-то шаге
it = 3
it = map.erase(it); // после этого it =2
continue; // следующий элемент уже it =4 после того как for выполнит it ++








Здравствуйте, itman, Вы писали:

I>Здравствуйте, serega, Вы писали:

I>При этом будет регулярно пропускаться один элемент после удаляемого


S>>Привет
S>>в доке все написано

S>>Iterator map::erase (iterator Where)

S>>Return value:
S>>a bidirectional iterator that designates the first element remaining beyond any elements removed, or a pointer to the end of the map if no such element exists
S>>Следовательно делаем так

S>>

S>>for (it = map.begin();i != map.end();it++)
S>>{
S>>  if (условие)
S>>  {
S>>     it = map.erase(it); // it будет переброшен на первый верхний неизмененный елемент 
S>>  }
S>>}
S>>

S>>Успехов

Здравствуйте, itman, Вы писали:

S>>в доке все написано

Эта дока называется MSDN и писана по Dinkumware STL, которая вот именно в этом месте отходит от Стандарта.
По Стандарту, void map::erase(map::iterator).

S>>for (it = map.begin();i != map.end();it++)
S>>{
S>>  if (условие)
S>>  {
S>>     it = map.erase(it); // it будет переброшен на первый верхний неизмененный елемент 
S>>  }
S>>}

В этом коде — ошибка. После того, как будет получен итератор на следующий за удаляемым элемент, мы на следующем шаге его инкрементируем.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, itman, Вы писали:

S>>>в доке все написано

К>Эта дока называется MSDN и писана по Dinkumware STL, которая вот именно в этом месте отходит от Стандарта.
К>По Стандарту, void map::erase(map::iterator).

Щас придет Alexeib и вкатит тебе минус

B>Щас придет Alexeib и вкатит тебе минус

Будет весело, если Alexeib прийдет и вкатит дяде Кодту плюc

Здравствуйте, Павел Кузнецов,

MAP coll; //MAP - тайпдеф мепа.
MAP::iterator pos;

for(pos = coll.begin(); pos!=coll.end(); ++pos)
    if(pos->second==value)
        coll.erase(pos); //ошибка времени выполнения

Полсе вызова erase() для элемента, на который ссылается итератор, итератор становится не действительным. Любые попытки использовать этот итератор после удаления элемента без повторной инициализации — даже команда ++pos — приведет к непредсказуемым последствиям.

Согласен. Верю. Понимаю.

Правильный способ удаления элемента, на который ссылается итератор, выглядит так:

MAP coll; //MAP - тайпдеф мепа.
MAP::iterator pos;

for(pos = coll.begin(); pos!=coll.end(); )
    if(pos->second==value)
        coll.erase(pos++);
    else
        ++pos;

Код идентичен вашему.
Но лично я не понимаю в чем разница между примерами. Какая разница где итератор инкреминировать?

Посмотрите как реализована операция постинкремента:

T T::operator++(int)
{
   T temp(*this);
   ++(*this);
   return temp; (*)
}

А теперь взгляните на

coll.erase(pos++);

erase принимает старое значение pos (*) и именно старое значение (*) становится невалидным.

Здравствуйте, Wind, Вы писали:

W>Код идентичен вашему.

Нет, не идентичен.

W>Но лично я не понимаю в чем разница между примерами. Какая разница где итератор инкреминировать?

Не "где" а "когда" и "какой".
Давай заменим for() на эквивалентный while() — так будет понятнее

// твой код
pos = coll.begin();
while(pos != coll.end())
{
  if( to_be_deleted(*pos) )
    coll.erase(pos);
  ++pos; // если мы только что инвалидировали итератор (стерев элемент), то не можем его инкрементировать
}

// правильный код
pos = coll.begin();
while(pos != coll.end())
{
  if( to_be_deleted(*pos) )
    coll.erase(pos++);
  else
    ++pos;
}

// поскольку там фигурирует постинкремент, распишем его
pos = coll.begin();
while(pos != coll.end())
{
  if( to_be_deleted(*pos) )
  {
    temp = pos; ++pos; // вот что такое постинкремент
    coll.erase(temp); // тем самым мы никогда не будем иметь дело с инвалидным pos
  }
  else
    ++pos;
}

Здравствуйте, Анатолий Широков, Вы писали:

АШ>Посмотрите как реализована операция постинкремента:

АШ>А теперь взгляните на

АШ>erase принимает старое значение pos (*) и именно старое значение (*) становится невалидным.
Понял. Спасибо.

Здравствуйте, Wind, Вы писали:

W>у меня есть std::map <int, СЛОЖНАЯ_СТРУКТУРА> a. Периодически возникает задача удаления не нужных записей, причем таких записей может быть несколько и расположены они могут быть в произвольных местах. Алгоритм, который мне пришел в голову:
W>1) Перебираю каждый элемент списка на соответствие некоторым условиям
W>2) Встретился элемент, который нужно удалить — удалил его и продолжил искать далее

W>Но вот незадача, после удаления элемента итераторы становятся не действительными, значит их нужно задать заново и с элемента .begin() заново начать поиск (заново, т.к. ни кто гарантий не дает, как будут располагаться элементы. Или я не прав?) Это потенциально долго, а на ключи полагаться нельзя, т.к. в момент работы алгоритма значения ключей не известны.

W>Вот такая ерунда.
W>Что псоветуете?
Вот буквально пару дней назад у меня именно такая задача стояла в дипломе.
Кстати теперь у меня много времени на диплом (в отличие от 4 дня назад) еще целый год, так что жду поздравлений

В целом все то же самое
std::map<int/*иногда свой ключ — некая struct*/, double>
т.е. значение всегда ВСТРОЕННЫЙ тип
Я пытался присобачить std::remove_if, насколько я понимаю std::remove_if переупорядочивает элементы по значению переданного ему предиката, и возвращает итератор, начиная с которого и до map::end() все элемены подлежат удалению
т.е. по сути надо потом позвать map::erase(returned_iterator, map::end())
что я и делал
НО! косяк был в следующем:
компилятор ругался на отсуствие MyMap::value_type::operator= т.е. он явно пытается какие то элементы переставить местами, и ругается что не может сделать присвоение для пары (MyMap::value_type это на самом деле pair<KEY, VALUE>)
причем для ключа я определил оператор присвоения, а значения в карте у меня встроенные...

В общем поскольку на тот момент было два дня до канадской границы, я действительно просто обходил map и перекладывал из него все что мне надо во временный map, а потом просто присваивал его.
Отсюда вопросы:
1) std::remove_if не умеет и не должен что ли работать с сортированными последовательностями (вроде как да, поскольку славные его перестановки должны видимо нарушать порядок в std::map)
2) Если все же они не должны работать, то как то очень подозрительно отсутствие встроенного алгоритма для именно std::map (в принципе тот же find же реализован в std::map, и логично было ожидать что если общий алгоритм имеет недостатки по сравнению с методом, то метод скорее будет реализован в контейнере). А отсуствие такого метода меня как-то наводило на мысль что все же std::remove_if можно научить работать с map!?!
3) и честно говоря так и не получилось у меня определить map::value_type::operator=
Что думаете коллеги?

itman:

> У меня вопро на засыпку:
>

>  m.erase(i++);
>

> и
>

>  i = m.erase(i);
>

> дадут одинаковые значения итератора? если да, то зачем, вообще, из ерейза что-то возвращать?

У стандартного std::map<>::erase возвращаемое значение — void.

Carc:

0)

> компилятор ругался на отсуствие MyMap::value_type::operator= т.е. он явно пытается какие то элементы переставить местами, и ругается что не может сделать присвоение для пары (MyMap::value_type это на самом деле pair<KEY, VALUE>)

Потому что на самом деле в std::map хранятся std::pair<const Key, Value> — и это правильно (*)

> Отсюда вопросы:
> 1) std::remove_if не умеет и не должен что ли работать с сортированными последовательностями (вроде как да, поскольку славные его перестановки должны видимо нарушать порядок в std::map)

Верно.

> 2) Если все же они не должны работать, то как то очень подозрительно отсутствие встроенного алгоритма для именно std::map (в принципе тот же find же реализован в std::map, и логично было ожидать что если общий алгоритм имеет недостатки по сравнению с методом, то метод скорее будет реализован в контейнере). А отсуствие такого метода меня как-то наводило на мысль что все же std::remove_if можно научить работать с map!?!

Т.к. более эффективно, чем простой обход всех значений std::map, реализовать эту специализацию не выйдет, то смысла в ней не видно...

> 3) и честно говоря так и не получилось у меня определить map::value_type::operator=

goto 0)

Здравствуйте, Павел Кузнецов, Вы писали:

ПК>У стандартного std::map<>::erase возвращаемое значение — void.

Вроде поднимался вопрос, чтобы переделать чтобы было как у всех контейнеров. И вроде как идею не зарубили совсем.

В этом смысле Ms просто пошла вперед

Здравствуйте, Кодт, Вы писали:

В реализации метода erase (от ms) какие то контейнеры отдают тот же итератор что им дали, какие то (map к примеру) отдают инкрементнутый итератор.

Юнусов Булат,

> ПК>У стандартного std::map<>::erase возвращаемое значение — void.

> Вроде поднимался вопрос, чтобы переделать чтобы было как у всех контейнеров. И вроде как идею не зарубили совсем.

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

Здравствуйте, Wind, Вы писали:

W>у меня есть std::map <int, СЛОЖНАЯ_СТРУКТУРА> a. Периодически возникает задача удаления не нужных записей, причем таких записей может быть несколько и расположены они могут быть в произвольных местах. Алгоритм, который мне пришел в голову:
W>1) Перебираю каждый элемент списка на соответствие некоторым условиям
W>2) Встретился элемент, который нужно удалить — удалил его и продолжил искать далее

W>Но вот незадача, после удаления элемента итераторы становятся не действительными, значит их нужно задать заново и с элемента .begin() заново начать поиск (заново, т.к. ни кто гарантий не дает, как будут располагаться элементы. Или я не прав?) Это потенциально долго, а на ключи полагаться нельзя, т.к. в момент работы алгоритма значения ключей не известны.

W>Вот такая ерунда.
W>Что псоветуете?

А так ?

    std::map <int,СЛОЖНАЯ_СТРУКТУРА>::iterator e;
    e = std::remove(a.begin(),a.end(),some_map_element); ///если на совпадение
    /// e = std::remove_if(a.begin(),a.end(),predicate(...));   ///если по условию
        a.erase(e,a.end());

:shuffle: