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

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

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

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

29.11.2012, 20:22. Просмотров 905. Ответов 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 (C++):

STL vector,list - C++
У меня 2 вопроса: 1) можете рассказать,как подробно работает reverse_iterator?Создал вектор,хочу его распечатать в обратном порядке...

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

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

Работа с STL list + пропись List.h - C++
Здравствуйте! Помогите, пожалуйста, разобраться с STL list. Нужно сделать программу в которой будет содержаться класс Student, прописать...

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
HighPredator
5477 / 1843 / 343
Регистрация: 10.12.2010
Сообщений: 5,435
Записей в блоге: 3
29.11.2012, 21:04 #2
Не совсем понимаю, что значит "объяснить теоретически". Вставка элементов в вектор в позиции, отличной от конца вектора, требует линейного времени. Вставка в список требует константного времени. К тому же вставка в вектор может еще привести к перераспределению памяти.
Damaks
18 / 10 / 1
Регистрация: 02.09.2010
Сообщений: 235
30.11.2012, 19:35  [ТС] #3
Память не перераспределяется, т.к. размер не превышает 101. У листа другой недостаток, его перебор происходит гораздо дольще, т.к. нужно обращаться не к следующему блоку памяти, а каждый раз считывать указатель и переходить по нему. Вот только на сколько дольше не понятно. И на сколько чтение дольше записи, если вообще дольше. В вектора ведь происходит сдвиг при вставке.
Може то на то и выходит?
HighPredator
5477 / 1843 / 343
Регистрация: 10.12.2010
Сообщений: 5,435
Записей в блоге: 3
30.11.2012, 23:26 #4
Вот теперь, кажется, я понял суть вашего вопроса.
Цитата Сообщение от Damaks Посмотреть сообщение
его перебор происходит гораздо дольше, т.к. нужно обращаться не к следующему блоку памяти, а каждый раз считывать указатель и переходить по нему. Вот только на сколько дольше не понятно.
А вот это-то как раз понятно. Для списка же нет возможности за константное время вычислить выражение наподобие list.begin()+n. Вариант один - проходить узлы. А время прохода, очевидно, пропорционально n. То есть линейно. Исходя из этого список проиграет вектору.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.11.2012, 23:26
Привет! Вот еще темы с ответами:

STL vector iterator - C++
есть список в списке... ..точнее: vector <Class1*> mapClass1; а уже в Class1 определён вектор vector <Class2*> mapClass2; ...

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

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

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
30.11.2012, 23:26
Ответ Создать тему
Опции темы

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