I have an array of integers with a bunch of numbers from 1-10 Then I have an array of names(strings) which belong with the numbers a.e.
Numbers[0] = 5, Numbers[1] = 2
Names[0] = "Jeremy", Names [1] = "Samantha".
I can easily order the numbers with:
int n = sizeof(Numbers) / sizeof(Numbers[0]);
sort(Numbers, Numbers + n, greater<int>());
But then the names and numbers don't match at all. How do I fix this?
A very common approach is to create an array of indices and sort that:
std::vector<int> indices(Numbers.size());
std::iota(indices.begin(), indices.end(), 0);
std::sort(indices.begin(), indices.end(),
[&](int A, int B) -> bool {
return Numbers[A] < Numbers[B];
});
The original arrays are not altered, but now indices can be used to access both arrays in the desired order.
If we want to reorder Numbers or Names in place, then we can
create a set of "back indices" that record where to find the element i in the sorted array:
std::vector<int> back_indices(indices.size());
for (size_t i = 0; i < indices.size(); i++)
back_indices[indices[i]] = i;
Now we can reorder, for example, Names in place in the desired order:
int index = 0;
std::string name = Names[index];
for (int i = 0; i < back_indices.size(); i++) {
index = back_indices[index];
std::swap(name,Names[index]);
}
I've tested this code which should give you the required behavior:
struct numberName {
int num;
string name;
};
bool compare(numberName a, numberName b){
return a.num < b.num; // if equal, no need to sort.
}
int main() {
numberName list[2];
list[0].num = 5, list[1].num = 2;
list[0].name = "Jeremy", list[1].name = "Samantha";
sort(list, list+2, compare);
}
Like HAL9000 said, you want to use a struct since this keeps variables that belong to each other together. Alternatively you could use a pair, but I don't know if a pair would be good practice for your situation or not.
This is a great example of the complexities introduced by using parallel arrays.
If you insist on keeping them as parallel arrays, here is a possible approach. Create a vector of integer indexes, initialised to { 0, 1, 2, 3, etc }. Each integer represents one position in your array. Sort your vector of indexes using a custom comparision function that uses the indexes to refer to array1 (Numbers). When finished you can use the sorted indexes to reorder array1 and array2 (Names).
One could also write their own sort algorithm that performs swaps on the extra array at the same time.
Or one could trick std::sort into sorting both arrays simultaneously by using a cleverly designed proxy. I will demonstrate that such a thing is possible, although the code below may be considered a simple hackish proof of concept.
Tricking std::sort with a cleverly-designed proxy
#include <iostream>
#include <algorithm>
constexpr size_t SZ = 2;
int Numbers[SZ] = {5, 2};
std::string Names[SZ] = {"Jeremy", "Samantha"};
int tempNumber;
std::string tempName;
class aproxy {
public:
const size_t index = 0;
const bool isTemp = false;
aproxy(size_t i) : index(i) {}
aproxy() = delete;
aproxy(const aproxy& b) : isTemp(true)
{
tempName = Names[b.index];
tempNumber = Numbers[b.index];
}
void operator=(const aproxy& b) {
if(b.isTemp) {
Names[index] = tempName;
Numbers[index] = tempNumber;
} else {
Names[index] = Names[b.index];
Numbers[index] = Numbers[b.index];
}
}
bool operator<(const aproxy& other) {
return Numbers[index] < Numbers[other.index];
}
};
int main() {
aproxy toSort[SZ] = {0, 1};
std::sort(toSort, toSort+SZ);
for(int i=0; i<SZ; ++i) {
std::cout << "Numbers[" << i << "]=" << Numbers[i] << std::endl;
std::cout << "Names[" << i << "]=" << Names[i] << std::endl;
}
return 0;
}
...and an even more cleverly-designed proxy could avoid entirely the need to allocate SZ "aproxy" elements.
Tricking std::sort with an "even more cleverly-designed" proxy
#include <iostream>
#include <algorithm>
class aproxy;
constexpr size_t SZ = 2;
int Numbers[SZ] = {5, 2};
std::string Names[SZ] = {"Jeremy", "Samantha"};
aproxy *tempProxyPtr = nullptr;
int tempNumber;
std::string tempName;
class aproxy {
public:
size_t index() const
{
return (this - reinterpret_cast<aproxy*>(Numbers));
}
bool isTemp() const
{
return (this == tempProxyPtr);
}
~aproxy()
{
if(isTemp()) tempProxyPtr = nullptr;
}
aproxy() {}
aproxy(const aproxy& b)
{
tempProxyPtr = this;
tempName = Names[b.index()];
tempNumber = Numbers[b.index()];
}
void operator=(const aproxy& b) {
if(b.isTemp()) {
Names[index()] = tempName;
Numbers[index()] = tempNumber;
} else {
Names[index()] = Names[b.index()];
Numbers[index()] = Numbers[b.index()];
}
}
bool operator<(const aproxy& other) {
return Numbers[index()] < Numbers[other.index()];
}
};
int main() {
aproxy* toSort = reinterpret_cast<aproxy*>(Numbers);
std::sort(toSort, toSort+SZ);
for(int i=0; i<SZ; ++i) {
std::cout << "Numbers[" << i << "]=" << Numbers[i] << std::endl;
std::cout << "Names[" << i << "]=" << Names[i] << std::endl;
}
return 0;
}
Disclaimer: although my final example above may technically be in violation of the strict-aliasing rule (due to accessing the same space in memory as two different types), the underlying memory is only used for addressing space-- not modified-- and it does seems to work fine when I tested it. Also it relies entirely on std::sort being written in a certain way: using a single temp variable initialized via copy construction, single-threaded, etc. Putting together all these assumptions it may be a convenient trick but not very portable so use at your own risk.
