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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Damaks
18 / 10 / 1
Регистрация: 02.09.2010
Сообщений: 235
#1

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

29.11.2012, 20:22. Просмотров 890. Ответов 3
Метки нет (Все метки)

Дан сортированный по убыванию массив 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
Посмотрите здесь:

Работа с STL. Поменять vector на list - C++
Программа должна быть написана так, чтобы достаточно было заменить в одном месте vector на list и приложение делало все то же самое. Если...

Параллельный доступ к контейнерам STL - C++
Читаю Джосаттиса - Стандартная библиотека C++. Справочное руководство - 2014, стр 84. Написано: Не могу понять. Если параллельный...

vector STL - C++
class data { public: char path; char net; char metric; int number; // для укаания строки таблици }; class vertex

Работа с STL vector - C++
Добрый день! Прошу объяснить следующие моменты связанные с <vector> (почему ругается студия, откуда берутся такие результаты) и дать...

STL. Map, vector. Строки - C++
Здравствуйте. Почти не знаком с STL. Имеется вектор строк. Нужно найти частоту использования каждой буквы. Я уже который...

Stl vector, не резервирует память - C++
vector не резервирует память и не вставляет элемент std::vector<int> myVector; myVector.reserve(10); ...

STL обращение к элементу vector - C++
Помогите исправить ошибку. #include <iostream> #include <vector> using namespace std; class otschet { public: double...

vector и функция read() из STL - C++
Привет всем, мой первый вопрос на этом форуме... Вот: Пишу программу "Список сотрудников", в которой использую vector из библиотеки...

STL vector запись в файл - C++
Здраствуйте! Такая проблема, есть у меня например vector чисел 1,2,3,4,5 надо записать их в файл. Если записываю так, то выбивает ошибка...

stl sort vector не сортирует ?! - C++
class Playlist { private: std::vector<Song> s_container; public: Playlist() { s_container=std::vector<Song>(); } ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
HighPredator
5464 / 1830 / 338
Регистрация: 10.12.2010
Сообщений: 5,412
Записей в блоге: 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
5464 / 1830 / 338
Регистрация: 10.12.2010
Сообщений: 5,412
Записей в блоге: 3
30.11.2012, 23:26     Задача по контейнерам stl vector и list #4
Вот теперь, кажется, я понял суть вашего вопроса.
Цитата Сообщение от Damaks Посмотреть сообщение
его перебор происходит гораздо дольше, т.к. нужно обращаться не к следующему блоку памяти, а каждый раз считывать указатель и переходить по нему. Вот только на сколько дольше не понятно.
А вот это-то как раз понятно. Для списка же нет возможности за константное время вычислить выражение наподобие list.begin()+n. Вариант один - проходить узлы. А время прохода, очевидно, пропорционально n. То есть линейно. Исходя из этого список проиграет вектору.
Yandex
Объявления
30.11.2012, 23:26     Задача по контейнерам stl vector и list
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru