Проход по контейнеру и получение последнего активного значения

@SektorCT · Регистрация: 22.03.2022

Студворк — интернет-сервис помощи студентам

Всем привет.
Есть лист структуры, каждая структура это значение и булево значение активности.
Все структуры находятся в строгом порядке, то есть 1,2,3,4,5. Не может быть такого чтобы была ситуация 1,2,5,4,3.
Активными могут быть минимум 0 а максимум например 5, и нужно узнать какой последний.
Количество активных может меняться постоянно, а значит нужен постоянный проход.

Вопрос, как можно такой алгоритм поиска осуществить чтобы быстро находить последний?

Иметь дополнительно под каждую структуру еще флаг?
Посоветуйте пожалуйста.

@lemegeton · 19.02.2024, 15:04

Последний это какой? Который последний добавили? Который последний изменили? Который с максимальным значением? Который с минимальным значением?

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

@SektorCT · 19.02.2024, 15:43 **[ТС]**

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

Последний это какой? Который последний добавили? Который последний изменили? Который с максимальным значением? Который с минимальным значением?

1 - false
2 - false
3 - true
4 - false
5 - true

вот пример, в данном случаи у последнего элемента статус активности, первым был активен 3 а вторым активен 5, значит мы сообщаем что он активен.
1 - false
2 - false
3 - true
4 - false
5 - false

а вот тут активный только 3 элемент а значит он последнйи из всех допустимых активных.

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

@nmcf · 19.02.2024, 16:15

Что не получится? Почему нельзя изменить способ хранения?

@alexu_007 · 19.02.2024, 16:26

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

вот пример, в данном случаи у последнего элемента статус активности, первым был активен 3 а вторым активен 5

Откуда такая информация? А может был активен 5, а после него активировался 3?
Самый простой способ - добавить в проект переменную, в которую при каждой активации записывать номер активируемого элемента.

@lemegeton · 19.02.2024, 16:55

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

вот пример, в данном случаи у последнего элемента статус активности, первым был активен 3 а вторым активен 5, значит мы сообщаем что он активен.

Понятно. Значит последний это с максимальным значением "ключа".

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

Если все же изменения контролируются, то можно оптимизировать поиск, например храня отсортированный контейнер указателей на "активные" структуры в основном контейнере и при добавлении/удалении/изменении структур менять и контейнер с указателями на "активные" элементы.

Таким образом поиск последнего будет за константное время, а время вставки, удаления и изменения элементов увеличится линейно пропорционально размеру контейнера с указателями на "активные" элементы.

@SektorCT · 19.02.2024, 18:54 **[ТС]**

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

Откуда такая информация? А может был активен 5, а после него активировался 3?

Если после активировался 3 то при следующем проходе мы и изунаем это.
Порядок их менятся не может, так же нельзя добавить никаких дополнительных ключей для определения, я могу только работат ьс результатом, за рабоут логики и заполнения контейнера я не отвечаю.
Исходя из ваших слов получается у меня будет 1 проход с определением номера какой последний а потом второй проход уже найти это значение и сообщить что он последний.

@alexu_007 · 19.02.2024, 20:27

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

Если после активировался 3 то при следующем проходе мы и изунаем это.

Активироваться за 1 раз может только 1 ключ?
Остальные при этом сбрасываются или нет?
Сколько всего ключей?
Какая частота обновления ключей?

В общем случае при проходе нужно создавать копию ключей. При следующем проходе сравнивать копию с новым состоянием ключей, и искать тот, который активировался.

@SektorCT · 25.02.2024, 23:25 **[ТС]**

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

Активироваться за 1 раз может только 1 ключ?

Да, 1 ключь последнйи за 1 проход, остальыне не сбрасываются, но с последующим изменениям может произойти измененеи в активации.

Я нашел 1 способ, а тчонее подсказали что в std есть подходящего чтоыб уменьшить количество проходов каждой итерации.
Но не знаю как правильно написать, может сможете поправить.

C++ (Qt)
1
2
3
    std::vector<int> vec = {1, 2, 3, 4, 5};
 
std::range::reverse_view(vec) | std::find_first_of([](const int limt) {return (тут будет из структуры где будет вектор значение активности)} )

Это просто пример, стректура с вектором и каким то полем активности, делаем перевернутый вид и получаем индекс самого первого активного числа.
То есть в нормлаьнмо виде какое то число нужно самое последнее активное, а в перевернутом он будет самым первым.
Но я не уверен что правильно понимаю как сделать такую запись.

@SmallEvil · 25.02.2024, 23:45

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

Я нашел 1 способ

как обмануть самого себя.

Добавлено через 1 минуту
SektorCT, то есть, у вас нет точной задачи. И на этом пнх...

@SektorCT · 27.02.2024, 13:11 **[ТС]**

Может кто подскажет как сделать реверс контейнера и поулчить уже у перевернутого первый нужный мне? Не понимаю как это правильно записать.

@lemegeton · 27.02.2024, 13:15

В С++ контейнеры не надо реверсить. Для этого есть функции, начинающиеся с буквы r -- rbegin и rend -- возвращающие реверснутые уже за вас итераторы.

Пример:

C++
1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <algorithm>
 
int main() {
 
    std::vector<int> container{1, 2, -1};
    auto result = std::find_if(container.rbegin(), container.rend(), [](auto v) { return std::abs(v) < 2; });
    std::cout << *result;
 
    return 0;
}

@SektorCT · 27.02.2024, 13:41 **[ТС]**

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

В С++ контейнеры не надо реверсить.

Спасибо за ответ.
Вопрос такой к нему, вот в вашем примере контейнер с индексами чисел 0,1,2. И вот переварачиваем представление и если последнее число нам нужно то как я могу получить его индекс который не реверсивный?
Спасибо

@nmcf · 27.02.2024, 13:43

Пересчитай. Ты же знаешь размер.

@lemegeton · 27.02.2024, 16:54

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

Вопрос такой к нему, вот в вашем примере контейнер с индексами чисел 0,1,2. И вот переварачиваем представление и если последнее число нам нужно то как я могу получить его индекс который не реверсивный?

Для вычисления относительной позиции в контейнерах используют функцию distance из библиотеки algorithm.

Не стоит забывать, что итератор, возвращаемый rend указывает на следующий за последним элементом, поэтому надо вычесть единицу для получения индекса, начинающегося с нуля.

Например так:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <algorithm>
 
int main() {
 
    std::vector<int> container{1, 2, -1};
    auto result = std::find_if(container.rbegin(), container.rend(), [](auto v) { return std::abs(v) < 2; });
    std::cout << (std::distance(result, container.rend()) - 1) << std::endl;
 
    std::cout << *result;
 
    return 0;
}

Странно, что вам это понадобилось.
Вы что-то делаете не так.
Расскажите подробнее, что вы пишете.

@sdf45 · 27.02.2024, 18:51

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

Порядок их менятся не может, так же нельзя добавить никаких дополнительных ключей для определения, я могу только работат ьс результатом, за рабоут логики и заполнения контейнера я не отвечаю

имхо, раз так - то без создания копии, как советует alexu_007, или сопровождения изменений как советует lemegeton, не обойтись.

Кликните здесь для просмотра всего текста

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

в данном случаи у последнего элемента статус активности, первым был активен 3 а вторым активен 5, значит мы сообщаем что он активен.

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

Откуда такая информация? А может был активен 5, а после него активировался 3?

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

Если после активировался 3 то при следующем проходе мы и изунаем это.

Последняя фраза-что это значит? Как ты поймешь что менялось первым?

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

Понятно. Значит последний это с максимальным значением "ключа".

Вот тут я не понимаю... Если у него (упорядоченный?) вектор структур вида:
struct S{int value, bool status}; vetor<S>vec;
и последний измененный - это элемент вектора, структура S с максимальным value? Зачем тогда status и структура вообще? Зачем эта непонятная авадакедабра с реверсом контейнера?(это вопрос к ТС) Ты его хоть переверни, хоть на уши поставь-как это поможет узнать, какой элемент вектора изменился последним?

Алексей1153 · 27.02.2024, 19:01

SektorCT, а чем не устроил массив (или список) из пяти указателей ? Новый добавляется в начало, более старые сдвигаются в конец, затирая самый старый

Только при удалении узла из основного списка нужно не забывать удалить указатель из массива

@sdf45 · 27.02.2024, 19:42

Сообщение от Алексей1153

Новый добавляется в начало, более старые сдвигаются в конец, затирая самый старый

похоже на стэк

Алексей1153 · 27.02.2024, 19:45

sdf45, точнее - очередь

@sdf45 · 27.02.2024, 19:47

Алексей1153, угу

Новые блоги и статьи Все статьи Все блоги /
Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .	Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .

@SektorCT 2 / 2 / 0 Регистрация: 22.03.2022 Сообщений: 225

	Проход по контейнеру и получение последнего активного значения 19.02.2024, 14:37. Показов 1530. Ответов 28 Метки с++ (Все метки) Всем привет. Есть лист структуры, каждая структура это значение и булево значение активности. Все структуры находятся в строгом порядке, то есть 1,2,3,4,5. Не может быть такого чтобы была ситуация 1,2,5,4,3. Активными могут быть минимум 0 а максимум например 5, и нужно узнать какой последний. Количество активных может меняться постоянно, а значит нужен постоянный проход. Вопрос, как можно такой алгоритм поиска осуществить чтобы быстро находить последний? Иметь дополнительно под каждую структуру еще флаг? Посоветуйте пожалуйста. 0

@lemegeton 4903 / 2696 / 921 Регистрация: 29.11.2010 Сообщений: 5,783
	19.02.2024, 15:04
	Последний это какой? Который последний добавили? Который последний изменили? Который с максимальным значением? Который с минимальным значением? Елси это "боевой код", я бы вообще не делал проходов, а сделал бы фасад или обертку над конткейнером, в котором бы сохранял "последний" "активный" элемент и изменял его при добавлении/удалении/обновлении. 0

@nmcf 7804 / 6568 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	19.02.2024, 16:15
	Что не получится? Почему нельзя изменить способ хранения? 0

@SektorCT 2 / 2 / 0 Регистрация: 22.03.2022 Сообщений: 225
	27.02.2024, 13:11 [ТС]
	Может кто подскажет как сделать реверс контейнера и поулчить уже у перевернутого первый нужный мне? Не понимаю как это правильно записать. 0

@nmcf 7804 / 6568 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	27.02.2024, 13:43
	Пересчитай. Ты же знаешь размер. 0

Алексей1153 фрилансер 6449 / 5643 / 1129 Регистрация: 11.10.2019 Сообщений: 15,029
	27.02.2024, 19:01
	SektorCT, а чем не устроил массив (или список) из пяти указателей ? Новый добавляется в начало, более старые сдвигаются в конец, затирая самый старый Только при удалении узла из основного списка нужно не забывать удалить указатель из массива 0

Алексей1153 фрилансер 6449 / 5643 / 1129 Регистрация: 11.10.2019 Сообщений: 15,029
	27.02.2024, 19:45
	sdf45, точнее - очередь 0

@sdf45 Покинул чат. 1132 / 727 / 195 Регистрация: 30.03.2021 Сообщений: 2,379
	27.02.2024, 19:47
	Алексей1153, угу 0