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

Question

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

c++arraysalgorithmduplicates

3

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

我使用的对象不易于复制，因为它们涉及到缓冲区分配和缓冲区拷贝。然而，它们很容易移动。

例如：
数组[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]]];

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

- Abator Abetor

1

它们移动起来便宜吗？而且那段代码看起来不对，因为它在追踪它们来自哪里之前进行排序和消除。此外，在消除重复项后，它未能修剪数组的末尾。 - Yakk - Adam Nevraumont

是的，它们移动起来很便宜。我已经将这个信息添加到帖子中了。修剪操作没有在代码中显示，它发生在填充ptrarray之前。 - Abator Abetor

另一个问题是您正在存储指向向量内元素的指针。如果以任何方式调整该向量的大小，这些指针可能会失效。例如：ptrarray[i] = &objarray[indexmap[tmp[i]]]; - PaulMcKenzie

@Abator Abetor，对我来说，使用每个对象的向量索引（位置）作为标识符让我感到担忧。 - Mohammad Kanan

@PaulMcKenzie 我知道这个。在设置指针后，objarray不会改变。ptrarray和objarray的生命周期也是相同的。 - Abator Abetor

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Yakk - Adam Nevraumont · Accepted Answer

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

这个程序执行了恰好N次MyObj的移动操作，其中N是原始向量中唯一的MyObj数量。

您的程序执行了M lg M次MyObj操作和N次复制操作，其中M是对象的数量，N是唯一对象的数量。

我的程序做了一些分配（大小为size_ts）可能可以进行清理，但这会使它变得不太清晰。