0

I have 2 vectors which store properties that are "linked". This is what I mean:

std::vector<std::string> names;
std::vector<int> ids;

// Name of object with an ID of 5
auto name = names[std::find(ids.begin(), ids.end(), 5) - ids.begin()];

Each object has a name and an ID, and so the object at index n has a name of name[n] and an ID of ids[n].

Now I want to sort the names in alphabetical order. I can use std::sort:

std::sort(names.begin(), names.end());

But now the IDs don't match! I thought of doing a vector of pairs, putting every name/id in it, sorting it, and then extracting out the data.

This isn't really efficient, as I have to loop 2 times over every element of both vectors, and the vectors have a lot of elements.

How can I make it more efficient, seeing that I can't use the vector of pairs instead of the 2 vectors from the beginning?

Rakete1111
  • 47,013
  • 16
  • 123
  • 162
  • 1
    a vector of pairs seems to be the way here. You only loop once over the structure and you can define in the sorting by what you want to sort. – Hayt Aug 31 '16 at 14:03
  • @Hayt but to extract the name and IDs out of the pairs requires another loop – Rakete1111 Aug 31 '16 at 14:03
  • 2
    have you tried using `std::map` ? I think that would do the trick for your case. You can provide a custom compare function to `std::sort` btw ;) – meetaig Aug 31 '16 at 14:04
  • a map would work if you only sort by string. But I assume you want to toggle between ID and name sorting? – Hayt Aug 31 '16 at 14:07
  • @meetaig Maybe `std::map` would be much better. As ID is unique same as the key of the map – Khalil Khalaf Aug 31 '16 at 14:07
  • @FirstStep this would not sort by name though – Hayt Aug 31 '16 at 14:07
  • @FirstStep @Hayt that's why I mentioned that you can provide a custom compare function. Maybe `std::pair` would also be a nice solution – meetaig Aug 31 '16 at 14:09
  • @Hayt No need to sort the map. Could take all the values and sort them somewhere else (for display or whatever). Once an ID is needed, search map for the string (value) and retrieve its ID (key). Not the best solution though, I believe – Khalil Khalaf Aug 31 '16 at 14:10
  • Why not take a page from the linked duplicate's accepted answer and make a vector of indices, which you then sort based off the values in your vectors at those indices? – jaggedSpire Aug 31 '16 at 14:29

1 Answers1

1

you could use a std::map string to int that maps names to their index (which is the same index of ids), and if you want to order to ids too another std::map int to int that maps ids to their index (which is the same index of names).

this way you can keep your arrays as is and have two ordered structure which can give you the needed index fast to access your arrays.

Fabio C.
  • 347
  • 4
  • 15
  • This would duplicate the data, which isn't ideal given the amount – Rakete1111 Aug 31 '16 at 20:19
  • True, but other ways I can think to is a vector of struct containing both name and is (discarded by you) or a sort procedure that sort both the arrays the same way (which means reordering every time you pass from names ordering to ids ordering and losing the initial order) – Fabio C. Sep 01 '16 at 08:55