Я работаю над проблемой в C ++, которая включает вычисления для массивов объектов, отсортированных по различным атрибутам. Предположим, у меня есть массив из 5 объектов с 3 различными атрибутами (A, B и C), и я сортирую массив по каждому атрибуту в отдельности. Это дает мне три массива, которые сообщают мне для каждого объекта, где его позиция была бы, если бы я сортировал их по соответствующему атрибуту.
std::vector<int> A_Order = { 1, 3, 0, 2, 4 };
std::vector<int> B_Order = { 2, 4, 3, 1, 0 };
std::vector<int> C_Order = { 0, 2, 4, 3, 1 };
Теперь я хочу разделить объекты на 2 подмножества, всегда выбирая позиция N в одном из порядков, где все объекты в позиции x <= N go в первом подмножестве, а все x > N go в следующем подмножестве. Если я сделаю это для атрибута A в N = 2, я получу следующее:
std::vector<int> A_OrderSub0 = { 1, 0, 2 };
std::vector<int> B_OrderSub0 = { 2, 3, 1 };
std::vector<int> C_OrderSub0 = { 0, 4, 3 };
std::vector<int> A_OrderSub1 = { 3, 4 };
std::vector<int> B_OrderSub1 = { 4, 0 };
std::vector<int> C_OrderSub1 = { 2, 1 };
Для эффективного выполнения следующей итерации вычислений мне снова нужно упорядочить подмножества вдоль атрибутов и получить результирующие позиции (в приведенном выше примере мне нужно B_OrderSub1 = { 4, 0 }, чтобы стать B_OrderSub1 = { 1, 0 }). Каков наиболее эффективный способ для меня повторно использовать «глобальные позиции», которые мне нужно получить только один раз в начале, чтобы затем получать «локально упорядоченные позиции» для объектов каждый раз, когда я делю их на подмножества?