Сортировка двух векторов одновременно

@Kapex · Регистрация: 11.11.2014

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

Всем доброго времени суток!

Дано: набор отрезков, начала которых хранятся в векторе а, концы -- в векторе b.
Задача: отсортировать отрезки по началам, т.е. по сути отсортировать массив а, одновременно перемещая элементы в b.

Понятно, что я могу написать свою собственную функцию quickSort и там делать одновременные преобразования а и b. Вопрос в другом: могу ли я сделать тоже самое с использованием алгоритмов STL и без привлечения дополнительной памяти? В идеале, хочется вот так:

C++
1
2
3
4
5
6
7
8
     vector<int> a, b;
     // a = {...}, b = {...}
 
    sort(a.begin(), a.end(), [&b]( ? x, ? y ) mutable {
                                          if ( a[x] < a[y] )
                                                swap(b[x], b[y]);
                                          return a[x] < a[y];
                                          });

@Hikari · 05.12.2016, 13:57

Что-то мне подсказывает что STL такое не сможет, пока ты два вектора не объединишь в матрицу.

Новичок · 05.12.2016, 14:02

А не проще хранить вектор пар?

C++
1
vector < pair<int, int> > a;

@Kapex · 05.12.2016, 14:51 **[ТС]**

Это приведёт к дополнительному месту O(n), а этого как раз и хочется избежать. Или можно объединить в матрицу так, что будет занято только O(1) допольнительного места?

Т.е. вопрос на самом деле состоит в том, ЧТО именно передаёт алгоритм sort() в фунцию сравнения? Можно ли туда передать не значения, а, скажем, итераторы на сравниваемые элементы? Если можно, то мы просто используем std::distance и всё в шоколаде.

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

@Mr.X · 05.12.2016, 14:54

Сообщение от Новичок

А не проще хранить вектор пар?

Действительно, автор как-то странно хранит отрезки, одна нога здесь, а другая там!

Новичок · 05.12.2016, 15:37

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

Это приведёт к дополнительному месту O(n)

И почему это вдруг? Создали массив пар - одно число начало отрезка, другое число конец отрезка, т.е никакой лишней памяти. И вызвали std::sort для вектора. Если надо, можно свою функцию сравнения передать третьим параметром.

@Kapex · 05.12.2016, 17:48 **[ТС]**

Новичок, если изначально в функцию передаётся два массива, то массив пар -- это уже дополнительное место. Чую, у этой задачи нет решения с исходными двумя массивами в терминах STL. Жаль ))

Новичок · 06.12.2016, 03:28

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

если изначально в функцию передаётся два массива, то массив пар -- это уже дополнительное место

А изначально хранить отрезки не в двух массивах а в одном массиве пар никак нельзя?

@Hikari · 06.12.2016, 07:21

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

это уже дополнительное место

А зачем ты так рьяно место экономишь?

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@Hikari Хитрая блондиночка $) 1472 / 988 / 399 Регистрация: 21.12.2015 Сообщений: 3,785
	05.12.2016, 13:57
	Что-то мне подсказывает что STL такое не сможет, пока ты два вектора не объединишь в матрицу. 0

@Kapex 15 / 15 / 4 Регистрация: 11.11.2014 Сообщений: 122
	05.12.2016, 14:51 [ТС]
	Это приведёт к дополнительному месту O(n), а этого как раз и хочется избежать. Или можно объединить в матрицу так, что будет занято только O(1) допольнительного места? Т.е. вопрос на самом деле состоит в том, ЧТО именно передаёт алгоритм sort() в фунцию сравнения? Можно ли туда передать не значения, а, скажем, итераторы на сравниваемые элементы? Если можно, то мы просто используем std::distance и всё в шоколаде. Добавлено через 1 минуту Новичок, проще, но это приведёт к использованию дополнительного места, а этого хотелось бы избежать. А изначально передаются в фунцию именно два вектора. Ну, да, ну, вот такая задачка. 0

@Kapex 15 / 15 / 4 Регистрация: 11.11.2014 Сообщений: 122
	05.12.2016, 17:48 [ТС]
	Новичок, если изначально в функцию передаётся два массива, то массив пар -- это уже дополнительное место. Чую, у этой задачи нет решения с исходными двумя массивами в терминах STL. Жаль )) 0