Какова оптимальная структура данных для контейнера пула? - PullRequest
Новая
       20

Какова оптимальная структура данных для контейнера пула?

8 голосов
/ 10 августа 2011

В настоящее время я использую шаблон контейнера вектора STL для возврата и получения соединений.

1) при получении возвращается соединение и "erase ()" d из вектора пула.

2) при выпуске соединение передается обратно в пул через «push_back ()».

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

Ответы [ 3 ]

11 голосов
/ 10 августа 2011
  • Если вы добавляете только сзади и стираете со спины, vector хорошо.
  • Если вы добавляете и стираете как спереди, так и сзади, но не посередине, используйте deque.
  • Если вам часто приходится вставлять и стирать с середины, используйте list.
  • В зависимости от ваших требований поиска и обхода, set может быть альтернативой.

В любом случае вы должны профиль производительность; используйте typedef для вашего основного контейнера, чтобы вы могли быстро переключаться и тестировать различные опции.

Могут быть и другие требования, о которых вы не сообщаете, но которые важны для выбора контейнера:

  • vector и deque - контейнеры с произвольным доступом; список и набор основаны на узле. Это влияет на аннулирование итератора.
  • vector, deque и list являются контейнерами последовательностей, а set является ассоциативным; это влияет на поиск по значению.
3 голосов
/ 10 августа 2011

std::vector, вероятно, лучший контейнер для пула. O (1) для вставки, и вы также можете иметь O (1) для удаления, если вам не нужно поддерживать порядок. Вы можете просто поменять последний элемент со снятым элементом и уменьшить вектор. Также std::vector довольно компактно по сравнению с другими контейнерами. Низкое потребление памяти также означает лучшую производительность благодаря большему количеству обращений к кэшу процессора.

2 голосов
/ 10 августа 2011

Сохраняйте вектор, если вы знаете заранее максимально возможное количество соединений (см. Вектор :: резерв).

В противном случае используйте std :: list.

В конце концов, это также зависит от вашей платформы и используемой версии компилятора и libstdc ++.

...