 |
|
Модераторы: Daevaorn |
 
|
|
Задач на собеседовании stl::vector 
| Paspartu |
|
|||
|
Шустрый  Профиль Группа: Участник Сообщений: 67 Регистрация: 3.5.2007 Репутация: нет Всего: нет |
Доброго времени суток!
...Вот такой у меня был вопрос: Kак удалить из вектора элемент (не первый/последний) максимально эффективно? |
|||
|
||||
Загрузка ...
| mrbrooks |
|
|||
 трололомен Профиль Группа: Завсегдатай Сообщений: 4259 Регистрация: 4.10.2006 Где: Дол Гулдур Репутация: 2 Всего: 306 |
если память не подводит, для этого используется сегментированный список.
Добавлено через 2 минуты и 2 секунды так же можно посмотреть реализацию удаления в std::list. |
|||
|
||||
| Paspartu |
|
|||
|
Шустрый Профиль Группа: Участник Сообщений: 67 Регистрация: 3.5.2007 Репутация: нет Всего: нет |
c std::list все понятно, вставка и удаление - быстро, поиск - медленно, сегментированный - лучше, но речь не идет о замене std::vector on std::list, реч идет как это реализовать именно в std::vector...
|
|||
|
||||
| Abyx |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 601 Регистрация: 3.11.2009 Репутация: 1 Всего: 10 |
в 101 совете вроде было
|
|||
|
||||
| jonie |
|
|||
|
Эксперт Профиль Группа: Завсегдатай Сообщений: 5613 Регистрация: 21.8.2005 Где: Владимир Репутация: 15 Всего: 118 |
думаю эффективнее заменить этот элемент последним и сделать декремент количества элементов не придумать - вектор в памяти линейно представлен, без "пробелов".... ну, конечно, порядок собъем, но об этом ничего не говорилось.
-------------------- Что-то не поняли? -> Напейтесь до зеленых человечков... эта сверхцивилизация Вам поможет... |
|||
|
||||
| Paspartu |
|
|||
|
Шустрый Профиль Группа: Участник Сообщений: 67 Регистрация: 3.5.2007 Репутация: нет Всего: нет |
To jonie, вариант!!!
Еще у кого есть что? |
|||
|
||||
| Peter |
|
|||
 Опытный Профиль Группа: Участник Сообщений: 771 Регистрация: 28.7.2003 Где: Ставрополь Репутация: -1 Всего: 1 |
Кроме erase(нужный_итератор), другого ответа на заданный вопрос не знаю. Можно ли менять порядок следования элементов - этого в задании не было.
-------------------- всё, что делаете, делайте от души, как для Господа (Послание апостола Павла колоссянам, 3:23). |
|||
|
||||
| borisbn |
|
|||
 Эксперт Профиль Группа: Завсегдатай Сообщений: 4875 Регистрация: 6.2.2010 Где: Ростов-на-Дону Репутация: 22 Всего: 135 |
Так как вектор по стандарту линейно располагается в памяти, то быстрее всего, кроме варианта
jonie ( кстати  ), будет memcpy
-------------------- Женщины отличаются от программистов тем, что у них чары состоят из стрингов |
|||
|
||||
| mes |
|
|||
|
любитель Профиль Группа: Участник Клуба Сообщений: 7954 Регистрация: 14.1.2006 Репутация: 144 Всего: 250 |
а кто сказал, что хранятся Pod'ы ?!  Добавлено через 4 минуты и 6 секунд и кстати даже если поды, то работать не будет, так как src и dst пересекаются в памяти .. нужна memmove  |
|||
|
||||
| jonie |
|
|||
|
Эксперт Профиль Группа: Завсегдатай Сообщений: 5613 Регистрация: 21.8.2005 Где: Владимир Репутация: 15 Всего: 118 |
mes, нафиг,нафиг эти переносы в памяти - есть operator=() , который должен быть реализован для контейнерных элементов - считаю это самым правильным способом, да и архитектурно независимым....
Я изначально предложил сдела vec[i] = vec[length] и уменьшить размер.... оверхед минимален, побочный эффект - собъется порядок, но обычно в vector не хранят порядокозависимые элементы имхо... Это сообщение отредактировал(а) jonie - 23.6.2010, 07:35 -------------------- Что-то не поняли? -> Напейтесь до зеленых человечков... эта сверхцивилизация Вам поможет... |
|||
|
||||
| borisbn |
|
|||
|
Эксперт Профиль Группа: Завсегдатай Сообщений: 4875 Регистрация: 6.2.2010 Где: Ростов-на-Дону Репутация: 22 Всего: 135 |
mes, при копировании "назад" всё будет работать и с memcpy (правда, стандартом не оговорено, что будет в случае пересечения, но на всех компиляторах и платформах, которые я знаю, это - работает). А вот с non POD'ами я конечно ступил. -1 мне
 -------------------- Женщины отличаются от программистов тем, что у них чары состоят из стрингов |
|||
|
||||
| mes |
|
||||
|
любитель Профиль Группа: Участник Клуба Сообщений: 7954 Регистрация: 14.1.2006 Репутация: 144 Всего: 250 |
да я как раз полностью согласен, для общих операций вектор и так может выбрать оптимальный алгоритм.. я лишь уточнил, что memcpy/memmove в контексте С++ для переноса не рекомендовано использовать.. а memcpy в предложенном варианте еще и имеет неопределенность выполнения..
вариант отличный.. но в некоторых случаях (например для vector<vector<int> > или vector<string>) удобнее использовать swap, несмотря на "оверхед". |
||||
|
|||||
|
|
| Правила форума "С++:Общие вопросы" | |
|
|
Добро пожаловать!
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | C/C++: Общие вопросы | Следующая тема » |
[ Время генерации скрипта: 0.0783 ] [ Использовано запросов: 22 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |