Условие:
Даны 3 списка с числами. Числа в списках не повторяются. Сами списки отсортированы. Необходимо реализовать метод GetNext, который бы обходил все 3 списка и выдавал числа в порядке возрастания. Объединять списки нельзя!
Примеры списков:
[List]: 1, 5, 12, 28, 31
[List]: 6, 9, 13
[List]: 3, 7, 10, 15
Вывод в этом случае должен быть таким:
GetNext << 1;
GetNext << 3;
GetNext << 5;
GetNext << 6;
GetNext << 7;
GetNext << 9;
и т.д.
Решение:
....
vector<vector<int>*> vectors;//тут хранятся наши списки
vector<int> vec1;
vector<int> vec2;
vector<int> vec3;//сами списки
....
vectors.push_back(&vec1);
vectors.push_back(&vec2);
vectors.push_back(&vec3);
vector<int> indexes(vectors.size(),0);//тут храним индекс элемента, который последний раз брали для каждого из списков
GetNext(indexes);
....
bool isExist(vector<int> &vec, int index)
{
return index < vec.size();
}
int GetNext( vector<int> &indexes)
{
int min = 0;
int index = -1;
for(int i=0;i<vectors.size();++i)
{
if(isExist(*vectors.at(i),indexes.at(i)))
{
min = vectors.at(i)->at(indexes.at(i));
index = i;
break;
}
}
if(index == -1)
throw exception();
for(int i=0;i<vectors.size();++i)
{
if(isExist(*vectors.at(i),indexes.at(i)))
{
if(vectors.at(i)->at(indexes.at(i))<min)
{
min = vectors.at(i)->at(indexes.at(i));
index = i;
}
}
}
indexes.at(index)++;
return vectors.at(index)->at(indexes.at(index)-1);
}
Оценка — на 4-
Улучшать можно по-всякому:
— разнести типы значений и индексов
— сделать не на векторах, а по-честному, на списках
— на изменяемых списках это даже проще делается
— at() не нужен, у нас в штатном режиме исключений выхода за границы не возникает — достаточно operator[]
— диагностику конца последовательности можно и без исключений сделать, а, например, отдельной функцией
— для трёх списков можно захардкодить, хотя обобщение на произвольное количество списков — в общем-то, правильный подход
Вместо вектора векторов и вектора индексов логичней использовать 1 вектор итераторов
Хотя я бы сделал проксю на 3 ячейки, которая хранит в себе копии текущих елементов (вместе с итераторами/индексами ессно): выдал наименьший из списка, взял из списка следующий, чтобы лишний раз в память не лазить (хотя это преждевременная оптимизация)
ps/
Впрочем, вру, конечно же, все равно надо еще хвосты запоминать, так-что векторов и с итераторами надо 2 :p
Здравствуйте, Кодт, Вы писали:
К>- сделать не на векторах, а по-честному, на списках К>- на изменяемых списках это даже проще делается
А зачем? Тормозить ведь будет. Это же не merge списков в один большой, а просто вывод по отдельности каждого элемента.
Вот если бы в результате нужен был список — то другое дело, действительно проще и быстрее собрать из трёх связанных списков один большой.
Фактически все равно это слияние отсортированных списков, только результат возвращается из GetNext. А как кстати GetNext должен сигнализировать о завершении всех списков? Я видел в коде throw exception.
Комментарии в коде решения
O>Решение: O>
O>vector<vector<int>*> vectors;//тут хранятся наши списки
// можно хранить списки по значению в векторе, но я бы ограничился массивом
// vector<int> vectors[3];unsigned const NUM_LISTS = 3;
typedef vector<int> numbers;
numbers lists[NUM_LISTS];
O>vector<int> indexes(vectors.size(),0);//тут храним индекс элемента, который последний раз брали для каждого из списков
// можно вместо индексов хранить const_iterator
// для используемого в качестве списка vector<int> это не принципиально,
// но для другого типа контейнеров (например list<int>) будет критично
numbers::const_iterator heads[NUM_LISTS];
heads[0] = lists[0].begin();
heads[1] = lists[1].begin();
heads[2] = lists[2].begin();
// GetNext станет такой: ищем минимальный из heads, возвращаем его, продвигаем итератор вперед int GetNext()
{
int min_head = 0;
for (int i = 0; i < NUM_LISTS; ++i)
{
if (heads[i] == lists[i].end()) continue; // пропускаем пройденный списокif (*heads[i] < *heads[min_head]) min_head = i;
}
if (heads[min_head] == lists[min_head].end())
throw exception(); // end of listsint min = *heads[min_head];
++heads[min_head];
return min;
}
O>}
O>
// почему не const& ? У среднестатистического программиста,
// который увидел передачу не-const ссылки, сразу возникает мысль,
// что передаваемый объект будет меняться внутри функции.
O>bool isExist(vector<int> &vec, int index)
O>
Люди! Люди, смотрите, я сошел с ума! Люди! Возлюбите друг друга! (вы чувствуете, какой бред?)
Здравствуйте, slava_phirsov, Вы писали:
_>Здравствуйте, Ororo1, Вы писали:
O>>
_>// почему не const& ? У среднестатистического программиста,
_>// который увидел передачу не-const ссылки, сразу возникает мысль,
_>// что передаваемый объект будет меняться внутри функции.
O>>bool isExist(vector<int> &vec, int index)
O>>
Да, в реальном проекте конечно же желательно const дописать, а в данном случае не принципиально. Индексы вон тоже бы unsigned не помешало сделать.
_>
_> int min = *heads[min_head];
_> ++heads[min_head];
_> return min;
_>
_> return *(heads[min_head]++);
_>
Не хочу ломать голову в приоритете операций, но похоже у тебя сначала идет инкремент итератора и затем его разыменование. И вот тут оно может свалиться. Нужного эффекта можно добиться с
return *heads[min_head]++;
, но постинкременту я предпочитаю явный порядок следования. Кто-то будет это читать и тоже ломать голову. Олдскульных сишников очень мало и они тоже могут ошибаться.
[offtoppic]
Вот не припомню, когда реально без постинкремента было невозможно обойтись. Вот фича, которую надо бы сделать deprecated в С++17 вместо триграфов
[/offtopic]
PM>Не хочу ломать голову в приоритете операций, но похоже у тебя сначала идет инкремент итератора и затем его разыменование. И вот тут оно может свалиться.
С чего бы это? Постфиксный инкремент возвращает предыдущее значение итератора, так что, все честно.
PM>Вот не припомню, когда реально без постинкремента было невозможно обойтись. Вот фича, которую надо бы сделать deprecated в С++17 вместо триграфов
И не надейся! Вангую: deprecated будут объявлены optional и лямбды
Люди! Люди, смотрите, я сошел с ума! Люди! Возлюбите друг друга! (вы чувствуете, какой бред?)
Здравствуйте, PM, Вы писали:
PM>С чего бы, если строкой выше есть проверка с комментарием "пропускаем пройденный список" PM>Я код проверял на тестовых данных топикстартера, всё отработало.
Ну, это еще ничего не доказывает
Смотри:
PM>int GetNext()
PM>{
PM> int min_head = 0; // Пусть, первый список уже пуст. Тогда heads[min_head] == lists[min_head].end()
PM> for (int i = 0; i < NUM_LISTS; ++i)
PM> {
PM> if (heads[i] == lists[i].end()) continue; // сработает при i == 0
// здесь мы оказываемся при i == 1, и разыменовываем heads[min_head], т.е. heads[0], т.е. lists[0].end()
// всё пропало!
PM> if (*heads[i] < *heads[min_head]) min_head = i;
PM> }
PM> if (heads[min_head] == lists[min_head].end())
PM> throw exception(); // end of lists
PM> int min = *heads[min_head];
PM> ++heads[min_head];
PM> return min;
PM>}
O>>}
Люди! Люди, смотрите, я сошел с ума! Люди! Возлюбите друг друга! (вы чувствуете, какой бред?)
Здравствуйте, slava_phirsov, Вы писали:
O>>не принципиально
_> Вообще-то такое должно на автомате писаться. Ну я так думаю
+1
O>>Индексы вон тоже бы unsigned не помешало сделать
_> Основоположники, ЕМНИП, учили использовать unsigned там и только там, где требуются операции с битами.
-1
емнип это авторы Java оправдывались почему у них нет беззнаковых целых. Последние удобно использовать в качестве индексов, т.к. для проверки индекса в массиве требуется одно сравнение вместо двух:
bool is_valid_index(int i, int size)
{
return i >= 0 && i < size;
}
bool is_valid_index(unsigned i, unsigned size)
{
return i < size;
}
А учитывая, что в стандартной библиотеке для индексов и количества элементов в контейнере используется беззнаковый size_t (с которым кстати в теории можно адресовать в 2 раза больше элементов чем с int), то с is_valid_index(int, int) получим на ровном месте предупреждение компилятора о преобразовании unsigned в int. Которое придется душить явным преобразованием к int
Задолбали такие функции:
void process_string(char const* str, int len);
// приходится их использовать так:
std::string str = "fgfg";
process_string(str.data(), static_cast<int>(str.size()));
Здравствуйте, PM, Вы писали:
PM>емнип это авторы Java оправдывались почему у них нет беззнаковых целых
А мне наоборот припоминается, что это Страуструп в своем талмуде писал такое. Вот нет под рукой, дойду до него — дам точную ссылку
PM>А учитывая, что в стандартной библиотеке для индексов и количества элементов в контейнере используется беззнаковый size_t (с которым кстати в теории можно адресовать в 2 раза больше элементов чем с int)
Ну вот, да, а в Qt наоборот сплошь и рядом int. Люди не смогли договориться о порядке следования байт, где уж тут знаковость индексов уединообразить. Только диктатура спасет человечество, ИМХО
Люди! Люди, смотрите, я сошел с ума! Люди! Возлюбите друг друга! (вы чувствуете, какой бред?)
Здравствуйте, slava_phirsov, Вы писали:
_>Ну, это еще ничего не доказывает
Это да, надо тестировать на крайних случаях
Возможный фикс:
int GetNext()
{
int min_head = -1;
for (int i = 0; i < NUM_LISTS; ++i)
{
if (heads[i] == lists[i].end()) continue;
if (min_head == -1 || *heads[i] < *heads[min_head]) min_head = i;
}
if (min_head == -1)
throw exception();
int min = *heads[min_head];
++heads[min_head];
return min;
}
Здравствуйте, slava_phirsov, Вы писали:
PM>>емнип это авторы Java оправдывались почему у них нет беззнаковых целых _>А мне наоборот припоминается, что это Страуструп в своем талмуде писал такое. Вот нет под рукой, дойду до него — дам точную ссылку
Страуструп да, писал и говорил нечто подобное.
Но если уж и апеллировать к авторитетам, то в области алгоритмов C++ нужно равняться на Степанова — он спокойно использует беззнаковые, и ЕМНИП даже рекомендовал в одной из лекций
.
Использование знаковых целых, там где по смыслу подходят беззаконные (да ещё и имеют большую "ёмкость") — это что-то из области babysitting'а, причём не особо удачного. Если уж нужна нянька — то тогда уже брать safe int и им подобные.
Перекуём баги на фичи!
Вообще-то такое должно на автомате писаться. Ну я так думаю 
Основоположники, ЕМНИП, учили использовать unsigned там и только там, где требуются операции с битами.
