C++：两个指向相同结构的指针向量，每个向量的排序不同

Question

我有一个 class 的人结构。每个人都有自己的姓名、主 ID 和次 ID。为了有效搜索，我实现了二进制搜索。问题是我想有效地（优于 O(n)）搜索人员，不仅要通过他们的主要 ID，还要通过他们的次要 ID。但是这些人只能通过一个参数进行排序。所以我想是否有可能制作两个指向 persons 结构的指针向量，一个按其主要 ID 排序，另一个按其次要 ID 排序。

例如，两个人：Mark Smith，主要 ID 9845613，次要 ID 1312469 和 John Doyle，主要 ID 3213444，次要 ID 2654722。因此 m_byPrim 向量的第一个元素和 [=24= 的第二个元素] 向量应指向 John Doyle。

这可能吗？这是到目前为止我设法编写的相关代码的一部分：

#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;
}

位置整数是我的二进制搜索函数的结果（插入人员的位置），我已经成功地实现了它，所以假设这个位置已经被初始化了。

但是我的问题是如何实现指针向量的添加？我对指针（和一般的 C++）还是很陌生，所以我不知道我的想法是否有效和可行。感谢您提供任何提示和帮助。

编辑：我忘了提到在 STL 容器中我只能使用向量。

Answer 1

尝试使用 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;
}

使用向量的缺点：

如果您在列表末尾以外的任何地方插入一个人，向量中已有的所有内容都必须 "bubble down"，被复制到列表中的新位置。
随着向量的增长，它需要定期重新分配并将整个现有元素集复制到新的底层数组。

使用地图的好处：

向列表添加新元素的影响很小
用于添加和查找元素的界面比在排序向量中查找内容更方便和可读。

Answer 2

由于您只能使用 vector，因此您的 AddPerson 函数应该如下所示：

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;
}

您还需要定义一个析构函数，因为您使用的是动态内存：

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


}

C++：两个指向相同结构的指针向量，每个向量的排序不同

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

c++

sorting

pointers

structure

vector