двигающиеся кнопки

[8Observer8]

Сообщение от rrrFer

1 Ты мне сказал - константная и отправил в документацию. В документации написано - линейная.
2 ты сказал разобраться с "наихудшим случаем" и опять отправил читать, но сам не разобрался
3 ты сказал "amortized time" (а ведь недавно говорил "константная"). и отправил читать, но сам не прочитал же опять - иначе бы не писал че попало. "amortized time" - это вообще не оценка сложности.

amortized time - это константное время, если массив маленький и линейное время, если очень большой. Если элементов становится больше и больше, то приходится увеличивать буфер для хранения, то есть выделять новый буфер большего размера и копировать из старого места в новое. В задаче автора темы мы добаляем по одной лошадке. Здесь будет константное время, поэтому можно использвать std::vector и другой контейнер для этой задачи не даст выгоды

[rrrFer]

amortized time - это константное время, если массив маленький и линейное время, если очень большой

т.е. внутри у вектора есть такой код примерно: ?

if (m_size < LIM) {
  // .. добавление за константное время
}
else {
  // добавление за линейное время
}

Такой код таки бывает, например в алгоритмах сортировки. Но в случае с вектором я себе такое не представляю. Я думаю обсуждение на стэковерфлоу, на которое ты ссылался ты сам до сих пор не прочитал.

Если элементов становится больше и больше, то приходится увеличивать буфер для хранения, то есть выделять новый буфер большего размера и копировать из старого места в новое.

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

Когда говорят о сложности алгоритма, то почти всегда полагают что N стремится к бесконечности. И тогда все разруливают пределы - примерно как я выше показал.

[8Observer8]

У меня было неправильное понимание "amortized time". В документации Qt хорошо написано:

"Amort. O(1)" means that if you call the function only once, you might get O(n) behavior, but if you call it multiple times (e.g., n times), the average behavior will be O(1).

[rrrFer]

[удалил, но кто-то прочитал]

[8Observer8]

Сообщение от rrrFer

Я написал выше, что если ты собрался добавлять в рантайме - юзай список, а не вектор. Если не добавлять - то обычный массив.

Пользователь будет добавлять лошадок через меню. Есть функция, которая вызывается по таймауту. Допустим таймаут каждые 10 миллисекунд. Произошёл таймаут, функция изменяет значение координат и в цикле показывает лошадок. В std::list доступ к элементам происходит за линейное время, а в std::vector за константное. Значит выбор в пользу std::vector

[min@y™]

пока в вилларибо ещё двигают кнопки, в виллабаджо давно рисуют анимированных лошадей!

[8Observer8]

goshek, спросите у преподавателя, может ли он разрешить использовать Qt? Думаю, на VS врядли вы осилите. Сделал вам примерчик. Здесь три кнопки движутся по окружности. Рад ответить на ваши вопросы

Исходники: https://github.com/8Observer8/Hippodrome

[goshek]

Сообщение от 8Observer8

goshek, спросите у преподавателя, может ли он разрешить использовать Qt? Думаю, на VS врядли вы осилите. Сделал вам примерчик. Здесь три кнопки движутся по окружности. Рад ответить на ваши вопросы

Исходники: https://github.com/8Observer8/Hippodrome

Спасибо, сегодня спрошу

[rrrFer]

Пользователь будет добавлять лошадок через меню. Есть функция, которая вызывается по таймауту. Допустим таймаут каждые 10 миллисекунд. Произошёл таймаут, функция изменяет значение координат и в цикле показывает лошадок. В std::list доступ к элементам происходит за линейное время, а в std::vector за константное. Значит выбор в пользу std::vector

А нужен ли произвольный доступ?
Если тебе надо перебрать всех лошадей - то разницы между списком и вектором нет.
Разница есть если тебе может потребоваться лошадь с конкретным индексом.

Короче аргумент не канает - если по таймеру ты решишь перерисовать лошадей из контенера - разницы между вектором и списком нет

А если ты юзаешь Qt - то скорее всего тут вообще не нужен контейнер. Создавая лошадь сразу соединяй ее слот перерисовки с сигналом таймера.

8Observer8
Критика к коду нужна? )

[8Observer8]

Критика к коду нужна?

Спасибо! Не нужна