Есть ли в мире c++ сабж?

Например, вектор является random access, но удаление посредством erase из середины очень тормозит.

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

А>Есть ли в мире c++ сабж?

А>Например, вектор является random access, но удаление посредством erase из середины очень тормозит.

boost::multi_index попробуйте.

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

А>Есть ли в мире c++ сабж?

А>Например, вектор является random access, но удаление посредством erase из середины очень тормозит.

Вектор указателей.

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

А>Есть ли в мире c++ сабж?

А>Например, вектор является random access, но удаление посредством erase из середины очень тормозит.

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

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

А>Есть ли в мире c++ сабж?
А>Например, вектор является random access, но удаление посредством erase из середины очень тормозит.

1) С++ тут не при чём. Структуры данных не зависят от языка
2) Какая-нибудь иерархическая структура. Например, B-дерево.

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

А>Есть ли в мире c++ сабж?
А>Например, вектор является random access, но удаление посредством erase из середины очень тормозит.

Стандартного контейнера нет, но операцию быстрого удаления реализовать легко:

template<typename C>
void fast_erase1( C c, int i )
{
   c[i] = c.back();
   c.pop_back();
}

Или

template<typename C>
void fast_erase2( C c, int i )
{
   swap( c[i], c.back() );
   c.pop_back();
}

Где c — вектор.

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

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

А>Есть ли в мире c++ сабж?

А>Например, вектор является random access, но удаление посредством erase из середины очень тормозит.

std::deque?

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

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

А>>Есть ли в мире c++ сабж?

А>>Например, вектор является random access, но удаление посредством erase из середины очень тормозит.

_wf>std::deque?

1. Фиговый или вообще нет random access
2. Фиговое или вообще нет удаление из середины

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

А>>Например, вектор является random access, но удаление посредством erase из середины очень тормозит.

MOP>Стандартного контейнера нет, но операцию быстрого удаления реализовать легко:
MOP>В зависимости от типа элементов будет эффективнее один или другой вариант. Можно, конечно, и контейнер-обёртку сделать.

Обычно, от random access ждут сохранения порядка...
Хотя кто его знает, что там ТС надо на самом деле.

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

E>Обычно, от random access ждут сохранения порядка...
E>Хотя кто его знает, что там ТС надо на самом деле.

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

Здравствуйте, Мишень-сан, Вы писали:

МС>Здравствуйте, _wf, Вы писали:

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

А>>>Есть ли в мире c++ сабж?

А>>>Например, вектор является random access, но удаление посредством erase из середины очень тормозит.

_wf>>std::deque?

МС>1. Фиговый или вообще нет random access
МС>2. Фиговое или вообще нет удаление из середины

я чего-то не понимаю?

deque::operator[]
// skipped
Complexity
Constant.

deque::erase
// skipped
Complexity
Linear on the number of elements erased (destructors). Plus, depending on the particular library implemention, additional linear time in up to the number of elements between position and one of the ends of the deque.

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

_wf>>>std::deque?

МС>>1. Фиговый или вообще нет random access
МС>>2. Фиговое или вообще нет удаление из середины

_wf>я чего-то не понимаю?

_wf>

_wf>deque::operator[]
_wf>// skipped
_wf>Complexity
_wf> Constant.

_wf>deque::erase
_wf>// skipped
_wf>Complexity
_wf> Linear on the number of elements erased (destructors). Plus, depending on the particular library implemention, additional linear time in up to the number of elements between position and one of the ends of the deque.

В мелкософтовской/динкумваровской реализации дека размер корзины выбран какой-то совершенно несуразный, поэтому дек на практике вырождается в список. Отсюда и непонятки.

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

А>Есть ли в мире c++ сабж?
А>Например, вектор является random access, но удаление посредством erase из середины очень тормозит.
Деревья или хешированные списки. Смотря насколько быстро нужно делать random access и random erase.