c – 对索引值的数组进行排序,打包和重新映射,以最大限度地减少

概述：

我有这样的事情：

std::vector<SomeType> values;
std::vector<int> indexes;

struct Range{
    int firstElement;//first element to be used in indexes array
    int numElements;//number of element to be used from indexed array
    int minIndex;/*minimum index encountered between firstElement 
        and firstElements+numElements*/
    int maxIndex;/*maximum index encountered between firstElement 
        and firstElements+numElements*/
    Range()
        :firstElement(0),numElements(0),minIndex(0),maxIndex(0){
    }
}

std::vector<Range> ranges;

我需要对值进行排序,重新映射索引并重新计算范围,以最小化每个范围的maxValueIndex-minValueIndex.

细节：

values是某种类型的数组(好的,“向量”)(与哪一种无关).值中的元素可能是唯一的,但这不能保证.

index是一个int的向量. “indices”中的每个元素都是与值中的某个元素对应的索引.索引中的元素不是唯一的,一个值可能会重复多种类型.而index.size()> = values.size().

现在,范围对应于索引的“数据块”数据. firstElement是要从索引中使用的元素的索引(即使用如下：indices [range.firstElement]),numElements是(显然)要使用的元素数,minIndex是mininum in(indices [firstElement] …索引[firstElement numElements-1])a,d maxIndex在(indices [firstElement] …索引[firstElement numElements-1])中是最大的.范围从不重叠.
即对于每两个范围a,b

((a.firstElement >= b.firstElement) && (a.firstElement < (b.firstElement+b.numElements)) == false

显然,当我对值进行任何操作(交换到元素等)时,我需要更新索引(因此它们一直指向相同的值),并重新计算相应的范围,因此range的minIndex和maxIndex是正确的.

现在,我需要以最小化Range.maxIndex – Range.minIndex的方式重新排列值.包装后我不需要“最佳”结果,“可能最好”或“好”包装就足够了.

问题：
重新映射索引和重新计算范围很容易.问题是我不确定如何对值中的元素进行排序,因为在多个范围内可能会遇到相同的索引.

关于如何进行的任何想法？

限制：

不允许更改容器类型.容器应该是类似阵列的.没有地图,没有列表.
但是你可以在排序过程中随意使用你想要的任何容器.
此外,没有增强或外部库 – 纯C / STL,我真的只需要一个算法.

附加信息：

没有为SomeType定义更多/更少的比较 – 只有相等/不相等.
但是应该没有必要比较两个值,只有索引.

算法的目标是确保输出

for (int i = 0; i < indexes.size; i++){ 
    print(values[indexes[i]]); //hypothetical print function
}

在排序之前和之后将是相同的,同时也确保每个范围
Range.maxIndex-Range.minIndex(排序后)尽可能小,以合理的努力.
我不是在寻找一个“完美”或“最优”的解决方案,拥有“可能完美”或“可能是最优”的解决方案就足够了.

附：这不是一个功课.