How to reorder vector elements in C++?

Question

I have a vector of objects whose elements I want to access in a sequence other than originally stored. My initial thought was to create an array of pointers, one for each array object, and move the pointer values to the desired order (so the underlying array doesn't need to change).

The vector iterator seems similar to an array of pointers, but I couldn't determine if they can be repointed.

Is there a customary way to do this?

ETA: @doug's comment below sent my mind down another path and I think I was overcomplicating the task. Each object in the array has an attribute that determines the order I want to consume another attribute. Based on doug's suggestion, I could traverse the array and write out two new arrays (one for each attribute) and do a vector of pairs sort. Consistent with @Ted Lyngmo's thought, maybe I could traverse the array and write out a single new array of structures comprised of the two attributes and then do a std::sort.

ETA 2: In case it matters, the vector of objects is generated by an external library and the attributes are only exposed through method calls.

This depends a lot on how you're deciding what the new sequence should be. e.g. Do yo happen to have a collection of indices that tell you the new order, or are you computing that some other way? — cigien, Apr 03 '21 at 02:20
The problem with pointers is lack of cache locality. I've had better results just copying the vector and sorting it against the new criteria.If space constrained, changing the vector to a vector of pairs with an index as the first pair element and the original class as the second works well. Easy to resort. There are variations on this. Indexes are also more space efficient than pointers in most cases. — doug, Apr 03 '21 at 02:29
@doug Thank you for introducing me to vector of pairs. That looks like something that could work for me. — c2po, Apr 03 '21 at 02:48
With regard to down vote. I truely appreciate the help offered and would like to improve how I ask questions. If you can tell me what I did wrong, I'll try to do better next time. Thanks! — c2po, Apr 03 '21 at 02:56
A standard algorithm springs to mind: [`std::sort`](https://en.cppreference.com/w/cpp/algorithm/sort) — Ted Lyngmo, Apr 03 '21 at 03:19
@c2po There is no need for pointers to do this. An array of indices, as indicated by [this answer](https://stackoverflow.com/questions/46382252/sort-array-by-first-item-in-subarray-c/46382976#46382976), is one way to do this without any pointers. — PaulMcKenzie, Apr 03 '21 at 03:37
Do you want to sort a vector of user-defiend elements? If so, there is simple way without using any array or pointers. I will post the answer if this is what you need. — ArashV, Apr 03 '21 at 04:22
Since you are getting the sorting criteria from an external method call, I suggest modifying @PaulMcKenzie 's link by making a vector of pairs. One has the indexes, the other the sorting criteria from the method call. Then sort on the criteria. Hard to say if this is what you need. To get better answers, include code or at least pseudocode for the needed detail. — doug, Apr 03 '21 at 18:13

score 0 · Answer 1 · answered Apr 04 '21 at 16:16

Despite my poorly composed question, the responses helped me arrive at a solution. As an FYI, here it is:

#include <algorithm>

using namespace std;

//structure to hold select data from array provided by external library
struct outdata
{
    string Sort; //data to be sorted
    double SortInfo1; //sort criteria1
    double SortInfo2; //sort criteria2
} od;

//function used to sort by criteria1 and then by criteria2
bool CompareFunc(const outdata& a, const outdata& b)
{ 
   if (a.SortInfo1 < b.SortInfo1) return true;
   if (b.SortInfo1 < a.SortInfo1) return false;

   // a=b for SortInfo1, go to SortInfo2
   if (a.SortInfo2 < b.SortInfo2) return true;
   if (b.SortInfo2 < a.SortInfo2) return false;

   return false;
} 

int main()
{
    vector<obj> source (getarray()); //array provided by external library

    vector<outdata> outarray; //array to hold data extracted from source
    
    //traverse source array and load select data to outarray
    for (vector<obj>::iterator it = source.begin(); it != source.end(); ++it)
    {
        od.Sort = it->getSort();
        od.SortInfo1 = it->getSortInfo1();  
        od.SortInfo2 = it->getSortInfo2();   
        outarray.push_back(od);
    }

    sort(outarray.begin(), outarray.end(), CompareFunc); //sort outarray

    //view results
    for (vector<outdata>::iterator it = outarray.begin(); it != outarray.end(); ++it)
    {
        printf("%s\n", it->Sort.c_str());
    }
}

How to reorder vector elements in C++?

1 Answers1