C++: two vectors of pointers to the same structure, each differently sorted

Question

I have a class with a structure of persons. Each person has its own name, primary ID and secondary ID. For effective searching I have implemented binary search. The problem is that I would like to effectively (better than O(n)) search persons not only by their primary ID, but also by their secondary ID. But the persons can be sorted only by one parameter. So I have thought if its possible to make two vectors of pointers to the persons structure, one sorted by their primary ID and the other one by their secondary ID.

For example, two persons: Mark Smith with primary ID 9845613 and secondary ID 1312469 and John Doyle, primary 3213444, secondary 2654722. So the first element of m_byPrim vector and second element of m_bySec vector should be pointing to John Doyle.

Is that even possible? Here is a part of the relevant code I have managed to write so far:

#include <cstdlib>
#include <cstdio>
#include <vector>
#include <string>

using namespace std;

class CPersons
{
public:
  bool AddPerson (const string &name,
                  unsigned int primID,
                  unsigned int secID);

private:
  struct Person {
    Person (const string & init_name,
            unsigned int init_primID,
            unsigned int init_secID)
     : m_name (init_name), m_primID (init_primID), m_secID (init_secID){}

      string m_name;
      unsigned int m_primID;
      unsigned int m_secID;
  };
  vector<Person*>m_byPrim;
  vector<Person*>m_bySec;
};

bool CPersons::AddPerson (const string &name, 
                          unsigned int primID, 
                          unsigned int secID){

  int positionPrim;
  int positionSec;

  return false;
}

int main ( void )
{
  CPersons a;
  a.AddPerson ( "Mark Smith", 9845613, 1324697 );
  a.AddPerson ( "John Doyle", 3213444, 2654722 );
  return 0;
}

The position integer is the result of my binary search function (position to which insert persons), I have managed to implement that successfully, so just assume that this position will be already initialized.

But my problem is how to implement the adding to the vector of pointers? I am still pretty new to the pointers (and C++ in general), so I don't know if my thought is valid and possible. Thank you for any tips & help.

edit: I forgot to mention that from STL containers I can use only vectors.

Answer 1

Since you can't use anything but vector, here's how your AddPerson function should look:

bool CPersons::AddPerson(
        const string &name, unsigned int primID, unsigned int secID) {
    // I'm assuming that the two functions below binary-search to get
    // the positions where inserting the elements into the arrays would
    // maintain their sorting
    int positionPrim = getPositionPrim();
    int positionSec = getPositionSec();
    Person *person = new Person(name, primID, secID);
    m_byPrim.insert(m_byPrim.begin() + positionPrim, person);
    m_bySec.insert(m_bySex.begin() + positionSec, person);
    return false;
}

You'll need to define a destructor as well because you're using dynamic memory:

CPersons::~CPersons()
{
    for (const auto &i: m_byPrim) {
        delete i;
    }


}

Answer 2

Instead of using sorted vectors, try using a std::map:

class CPersons
{
public:
  bool AddPerson (const string &name, unsigned int primID, unsigned int secID);

private:
  struct Person {
    Person (const string & init_name, unsigned int init_primID, unsigned    int init_secID)
      : m_name (init_name), m_primID (init_primID), m_secID (init_secID) {}

      string m_name;
      unsigned int m_primID;
      unsigned int m_secID;
  };
  map<unsigned int, Person*>m_byPrim;
  map<unsigned int, Person*>m_bySec;
};

bool CPersons::AddPerson (const string &name, unsigned int primID, unsigned int secID){

  p = new Person(name, primID, secID);
  m_byPrim[primID] = p;
  m_bySec[secID] = p;

  return false;
}

The drawbacks of using a vector:

• If you insert a person anywhere other than the end of the list, everything already in the vector has to "bubble down", being copied to its new position in the list.
• As the vector grows, it will periodically need to be reallocated and the entire set of existing elements copied to the new underlying array.

The benefits of using a map:

• The impact of adding new elements to the list is minimal
• The interface for adding and looking up elements is more convenient and readable than finding things up in a sorted vector.