Форум программистов, компьютерный форум CyberForum.ru

Задача по контейнерам stl vector и list - C++

Восстановить пароль Регистрация
 
Damaks
18 / 10 / 1
Регистрация: 02.09.2010
Сообщений: 235
29.11.2012, 20:22     Задача по контейнерам stl vector и list #1
Дан сортированный по убыванию массив int'ов размером 100 элементов. Значение начального максимального элемента a, минимального b. На вход приложения идут числа x входящие в этот диапазон, a>=x>=b.
Необходимо при приходе каждого числа x находить его место в массиве и вставлять соответственно в это место (сортировка массива при этом сохраняется). Последний элемент надо удалять, чтобы размер массива после оставался 100 элементов. Вероятность выпадения приходящего числа x значения соответствующего позиции линейно возрастает от начала массива к концу. Т.е. вероятность что пришедьшее число равно b максимальна, а a минимальна.
Задача объяснить теоретически vector или list будет отрабатывать в данной задаче быстрее.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.11.2012, 20:22     Задача по контейнерам stl vector и list
Посмотрите здесь:

C++ STL vector,list
C++ vector STL
Работа с STL. Поменять vector на list C++
C++ STL vector iterator
C++ stl::vector, метод pop_back()
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
HighPredator
 Аватар для HighPredator
5345 / 1728 / 320
Регистрация: 10.12.2010
Сообщений: 5,112
Записей в блоге: 3
29.11.2012, 21:04     Задача по контейнерам stl vector и list #2
Не совсем понимаю, что значит "объяснить теоретически". Вставка элементов в вектор в позиции, отличной от конца вектора, требует линейного времени. Вставка в список требует константного времени. К тому же вставка в вектор может еще привести к перераспределению памяти.
Damaks
18 / 10 / 1
Регистрация: 02.09.2010
Сообщений: 235
30.11.2012, 19:35  [ТС]     Задача по контейнерам stl vector и list #3
Память не перераспределяется, т.к. размер не превышает 101. У листа другой недостаток, его перебор происходит гораздо дольще, т.к. нужно обращаться не к следующему блоку памяти, а каждый раз считывать указатель и переходить по нему. Вот только на сколько дольше не понятно. И на сколько чтение дольше записи, если вообще дольше. В вектора ведь происходит сдвиг при вставке.
Може то на то и выходит?
HighPredator
 Аватар для HighPredator
5345 / 1728 / 320
Регистрация: 10.12.2010
Сообщений: 5,112
Записей в блоге: 3
30.11.2012, 23:26     Задача по контейнерам stl vector и list #4
Вот теперь, кажется, я понял суть вашего вопроса.
Цитата Сообщение от Damaks Посмотреть сообщение
его перебор происходит гораздо дольше, т.к. нужно обращаться не к следующему блоку памяти, а каждый раз считывать указатель и переходить по нему. Вот только на сколько дольше не понятно.
А вот это-то как раз понятно. Для списка же нет возможности за константное время вычислить выражение наподобие list.begin()+n. Вариант один - проходить узлы. А время прохода, очевидно, пропорционально n. То есть линейно. Исходя из этого список проиграет вектору.
Yandex
Объявления
30.11.2012, 23:26     Задача по контейнерам stl vector и list
Ответ Создать тему
Опции темы

Текущее время: 16:11. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru