0

Is there a better way to create a sorted array of member variable from a sorted array of custom(ie user defined) objects in C++?

Example - 

class People{
public:
   //can have multiple parameters. What are the options in either case?
   unsigned int birth_year;
};

Lets say we have an array of std::vector<People> and we want to get std::vector<unsigned int> sorted by birth year.

We can use one of the many ways to sort the custom object based on the birth_year mentioned in this link - Sorting a vector of custom objects.

Now, if we need to get the sorted birth year vector, we will have to iterate through the sorted People vector and push it on to a new vector of unsigned int.

Is there a faster way to do this(using memory offsets or such)? OR is there a feature in C++11 which we can leverage for this?

Community
  • 1
  • 1
Ashwin
  • 499
  • 1
  • 7
  • 21
  • 1
    Not sure what you're asking (it could help with a concrete example), but anyway, you can avoid many problems by simply using `int` instead of `unsigned`, for numbers. The `unsigned` types are good for bit level manipulation. Not so good for numbers. – Cheers and hth. - Alf Jan 27 '16 at 03:35
  • There's no faster way to make a vector than making the vector... – M.M Jan 27 '16 at 03:36
  • 1
    Good naming is also important in general. Here there is a class named `People`, where each `People` instance has a `birth_year`. And, for example, I don't even know the birth year of the Norwegian people. – Cheers and hth. - Alf Jan 27 '16 at 03:37
  • 1
    Third, while I'm in advice-mode, where you want a simple class with all members public, just use a `struct`: it defaults to public access. – Cheers and hth. - Alf Jan 27 '16 at 03:38
  • @Cheersandhth.-Alf have you got any comments that are actually relevant to the question – M.M Jan 27 '16 at 03:38
  • Why do you need the vector of unsigned ints? If you only need a view into the vector of People, then write a view adaptor; that should be easy. – rici Jan 27 '16 at 03:38
  • 2
    @M.M. Yes, the first one, that it needs an example. You sound like you didn't read? – Cheers and hth. - Alf Jan 27 '16 at 03:39
  • How is original array sorted? – Basilevs Jan 27 '16 at 03:41
  • @Cheersandhth.-Alf Your advice is noted. – Ashwin Jan 27 '16 at 05:39
  • @rici This is just an example. My application needs that vector for additional processing. – Ashwin Jan 27 '16 at 05:40
  • @Basilevs The link I have shared in my question, talks about sorting the original array. – Ashwin Jan 27 '16 at 05:40
  • It is still unclear if original array is sorted by required field values. If this is the case no additional sorting is required for field array (just accumulation of values in another collection/view). Otherwise sorting of original array is irrelevant and question title is misleading. – Basilevs Jan 27 '16 at 05:48
  • @Basilevs I see the source for confusion. Yes the original array is sorted by required field values. Since the custom object has only one value, this should have been implicit. I will edit the question to make this clear. – Ashwin Jan 27 '16 at 14:30

3 Answers3

2

Your question is rather under-specified. So here are a few assumptions and possible solutions

Your vector is already sorted by birth date

In that case, if you really want to be fast, just use reinterpret_cast. It is evil, but if your Person-class really just consists of that one member, then it certainly is the fastest thing.

Your Person class has more members than just birth_date

Use transform with a lambda.

std::vector<unsigned int> vec2;
vec2.reserve(vec1.size());
transform(vec1.begin(), vec1.end(), 
          back_inserter(vec2), 
          [](const Person& p) { return p.birth_date; });

You just want to read from the new vector

In that case, you might consider using a view (instead of a vector), see for instance https://github.com/ericniebler/range-v3

Rumburak
  • 3,416
  • 16
  • 27
  • I am kind of glad I did not specify the number of variables in Person class now. I will look into what `reinterpret_cast` and `transform` does. As you mentioned `view` is a new concept for me as well. Let me look into that and will accept your answer. – Ashwin Jan 27 '16 at 14:49
  • To be honest, it is still a bit hard to read. Try to state clear start conditions, like "I have a `vector` which is sorted by birth_date` if that is what you want to start with. Or "I have an unsorted `const vector`". Then state clear goals like "I need a `vector` containing the sorted birth dates". And maybe conditions like "the `vector` must not be changed in the process. – Rumburak Jan 28 '16 at 06:27
1

It's good to separate the values into a pre-allocated array first, that way they'll all be nice and contiguous for std::sort's rearrangements:

std::vector<unsigned> vec2;
vec2.reserve(vec1.size());
for (const auto& v : vec1) { vec2.push_back(v.birth_year); }
std::sort(vec2.begin(), vec2.end());

std::vector::reserve

Brian Rodriguez
  • 4,250
  • 1
  • 16
  • 37
  • @BrianRodrigez, the vector of People will also be contiguous, so if you provide 'std::sort' with a comparison function for People, you can sort the People vector just as fast, pre allocate the vector of 'unsigned int', and then copy the sorted values to the new vector. This would have the additional benefit that People vector is also sorted, which might be useful. – RobClucas Jan 27 '16 at 06:17
  • @nabla Not necessarily. If the `People` struct contains other members, then you will lose the locality benefits that a simple contiguous array of `int` gives you, especially for huge numbers of `People` instances. – Brian Rodriguez Jan 27 '16 at 12:56
  • Agreed, but you need to consider those benefits vs others. For example, it's likely that you would add to the vector of People, and (depending on the method) an almost sorted array can be sorted more quickly! I suppose that if you kept the sorted int array, then added 'birth_year' to that before you would still get the benefits you mentioned, however, it would mean that you have to keep the sorted int array around, which may not be ideal. – RobClucas Jan 27 '16 at 13:03
  • I like to believe you shouldn't pay for what you don't use. If you're only interested in the sorted values of `birth_year`, then creating a new array of ints (which is relatively cheap) is better than sorting the entire `People` vector. If you _also_ need to do something to the `People` based on the order of `birth_year`, then yes sort the entire vector. The question seems to fall under the former case, however, and so I stand by this as a better solution. – Brian Rodriguez Jan 27 '16 at 13:07
  • I agree with you, I was merely suggesting that since it is not know what will be done with the vector of 'People', in some contexts it may be better to sort the 'People'. – RobClucas Jan 27 '16 at 13:10
0

The answers posted so far create a new vector, copy the values of the birth_year variable into the new vector, and then sort the new vector.

IMO, it would be better to sort the vector of People first by birth_year, and then to copy the birth_year values from the sorted std::vector<People> to a new std::vector<unsigned int>. This would have the same overall performance, but would leave the vector of People sorted, which might be beneficial in some contexts. You can do this by overloading operator< in the Person class, or by providing a custom comparison function, see std::sort. Here is an example:

#include <algorithm>
#include <vector>

class People{
public:
  People(unsigned int BY) : birth_year(BY) {}

  unsigned int birth_year;

  // Overload operator< so that std::sort can compare People
  bool operator<(const People& rhs) const {
    return birth_year < rhs.birth_year;
  }
};

int main() {
  std::vector<unsigned int> uint_sorted_vector;

  // Example People vector
  std::vector<People> people = {4, 2, 9, 3};

  // Reserve space for the sorted uint vector
  uint_sorted_vector.reserve(people.size());

  // Sort the vector of People
  std::sort(people.begin(), people.end());

  // People vector is sorted, copy birth_year values to uint vector
  for (const auto& person : people) {
    uint_sorted_vector.push_back(person.birth_year);
  }
}

Here is a live demo : Coliru demo

RobClucas
  • 815
  • 7
  • 16