Neat

[dimrub]

programming trick (thanks to ilya_dogolazky for inspiration for looking it up).

Comments

[cema.livejournal.com]

avva вроде бы обсуждал это не так давно, или я путаю?

[dimrub.livejournal.com]

Не припомню.

[ex 314truha (from livejournal.com)]

Понравилась в коментах идея как реализовать remove(i)

[dimrub.livejournal.com]

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

[ex 314truha (from livejournal.com)]

Нет. Поменять местами dense[n-1] dense[i] с соответствующим изменением индекса в sparse и уменьшить n на единицу :)

[dimrub.livejournal.com]

Да, действительно.

[ex 314truha (from livejournal.com)]

Однако тут возможны грабли. В Статье среди прочего говорится о том, что dense является как бы стеком, и мы получаем возможность бегать по элементам sparse в порядке, в котором они были занесены (или в обратном), что делает возможным применение этой схемы например в алгоритмах на графах.
Однако приведённая имплементация remove сводит всё на нет, так как нарушается порядок элементов в dense.
Нет щастя в жизни...

[ex 314truha (from livejournal.com)]

Даже не поменять местами; достаточно dense[n-1] скопировать в dense[i] так как после удаления бывшее dense[i] никого не интересует