c++ - 将对象数组转换为指向唯一对象的指针数组

Question

我正在尝试将对象数组转换为对象指针数组，其中指针指向包含第一个数组的所有唯一对象的数组元素。

我正在使用的对象复制起来并不便宜，因为它们涉及缓冲区分配和缓冲区复制。然而，它们的移动成本很低。

例子:数组

[G,F,E,G,E,G]

应该转化为一个唯一的对象数组
U = [E,F,G] 和指针数组
P = [&U[2], &U[1], &U[0], &U[2], &U[0], &U[2]]

我目前正在使用以下代码来实现这一点:

int N; // 50 Millions and more
std::vector<MyObj> objarray; // N elements
std::vector<MyObj*> ptrarray; // N elements
...
std::vector<MyObj> tmp(objarray.begin(), objarray.end());

std::sort(objarray.begin(), objarray.end());
auto unique_end = std::unique(objarray.begin(), objarray.end());

// now, [objarray.begin(), unique_end) contains all unique objects

std::map<MyObj, int> indexmap;

// save index for each unique object
int index = 0;
for(auto it = objarray.begin(); it != uniqueend; it++){
    indexmap[*it] = index;
    index++;
}

//for each object in original array, look up index in unique object array and save the pointer
for(int i = 0; i < N; i++)
    ptrarray[i] = &objarray[indexmap[tmp[i]]];

是否有更有效的方法来实现这一点，可能不需要创建原始数组的拷贝，因为对象拷贝很昂贵？

Answer 1

struct r {
  std::vector<MyObj> objects;
  std::vector<MyObj*> ptrs;
};

r func( std::vector<MyObj> objarray ) {

  // makes a vector containing {0, 1, 2, 3, ..., N-1}
  auto make_index_buffer = [&]{
    std::vector<std::size_t> r;
    r.reserve(objarray.size());
    for (std::size_t i = 0; i < objarray.size(); ++i)
      r.push_back( i );
    return r;
  };

  // build a buffer of unique element indexes:
  auto uniques = make_index_buffer();

  // compares indexes by their object: 
  auto index_less = [&](auto lhs, auto rhs) { return objarray[lhs]<objarray[rhs]; };
  auto index_equal = [&](auto lhs, auto rhs) { return objarray[lhs]==objarray[rhs]; };

  std::sort( uniques.begin(), uniques.end(), index_less );
  uniques.erase( std::unique( uniques.begin(), uniques.end(), index_equal ), uniques.end() );

  // build table of index to unique index:
  std::map<std::size_t, std::size_t, index_less> table;
  for (std::size_t& i : uniques)
    table[i] = &i-uniques.data();

  // list of index to unique index for each element:
  auto indexes = make_index_buffer();

  // make indexes unique:
  for (std::size_t& i:indexes)
    i = table[i];

  // after this, table will be invalidated.  Clear it first:
  table = {};

  // build unique object list:
  std::vector<MyObj> objects;
  objects.reserve( uniques.size() );
  for (std::size_t i : uniques)
    objects.push_back( std::move(objarray[i]) );

  // build pointer objects:
  std::vector<MyObj*> ptrarray; // N elements
  ptrarray.reserve( indexes.size() );
  for (std::size_t i : indexes)
    ptrarray.push_back( std::addressof( objects[i] ) );

  return {std::move(objects), std::move(ptrarray)};
}

这正好执行了 MyObj 的 N 次移动，其中 N 是原始 vector 中唯一 MyObj 的数量。

你对 MyObj 进行了 M lg M 次移动，并复制了 N 个拷贝，其中 M 是对象的数量，N 是唯一对象的数量。

我的分配了一些(size_ts)，你可能会清理掉，但这会使它变得不太清晰。