C ++ умный линейный контейнер

Question

Позвольте мне объяснить мою проблему вместе с предысторией, чтобы было легче понять, почему я спрашиваю об этом конкретном типе вещей. Я разрабатываю мессенджер. Большая часть архитектуры описана моим учителем, однако детали реализации могут отличаться. Существует класс Engine, EventManager, который регистрирует клиентов. Чтобы идентифицировать их и легко удалить, я использую карту (с идентификаторами клиента) или набор с указателями. Все идет нормально. Но тогда этот EventManager использует poll() (или select(), но это не так удобно для использования, как poll(), так как вам приходится каждый раз перестраивать массив, что, я думаю, медленно и не так приятно, Я могу ограничиться средой UNIX, если вы спросите) в основном цикле. Который нуждается в массиве struct pollfd. Теперь каждый раз, когда приходит или уходит новый клиент, этот массив необходимо перестраивать. Либо я использую динамический массив вручную и каждый раз выделяю память (baaaaaad), либо я использую вектор, который будет довольно хорошо обрабатывать вставку struct pollfd нового клиента в конце контейнера, или деку, которая будет вставлять и удалять где угодно довольно хорошо. Теперь мои два вопроса:

1. Если я выберу vector, будет ли он автоматически сжиматься и перемещать элементы по центру вместо полного перераспределения? и
2. Это в любом случае скопировало бы много, если бы оно было в начале, поэтому я бы хотел использовать deque. Имеет ли он интерфейс массива (как вы сделали бы с вектором - &myVector[0]) или он является строго несмежным?

Answer 1

1. Если вы удалите что-то из середины vector, все следующие элементы переместятся на одну позицию к началу. Это будет не перераспределить. Вам вообще не нужно учитывать перераспределения, потому что они амортизируются, чтобы дать O (1) время на вставку.

2. deque не намного лучше, чем vector. Удаление с начала или конца эффективно. Не с середины. Если вы удалите его из любого места, то, мы надеемся, оно будет в два раза быстрее вектора, но не быстрее. Поскольку это более сложная структура, она, вероятно, будет еще медленнее. deque не гарантирует непрерывное хранение, поэтому, хотя индексирование разрешено и выполняется за время O (1), вы все равно не можете надежно преобразовать его в указатель.

В любом случае пахнет преждевременной оптимизацией. Используйте вектор. Поскольку порядок клиентов не имеет существенного значения, вы можете ускорить удаление клиентов, поменяв элемент, который вы хотите удалить, на последний элемент в векторе и вызвав pop_back() после этого.