transforme un tableau d'objets en un tableau de pointeurs vers des objets uniques

Question

J'essaie de transformer un tableau d'objets en un tableau de pointeurs d'objets, où les pointeurs pointent vers des éléments d'un tableau qui contient tous les objets uniques du premier tableau.

Les objets que j'utilise ne sont pas faciles à copier car ils impliquent l'allocation et la copie de tampons. En revanche, ils sont peu coûteux à déplacer.

Exemple : Le tableau

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

doit être transformé en un tableau d'objets unique
U = [E,F,G] et un tableau de pointeurs
P = [&U[2], &U[1], &U[0], &U[2], &U[0], &U[2]]]

J'utilise actuellement le code suivant pour y parvenir :

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

Existe-t-il un moyen plus efficace d'y parvenir, éventuellement sans créer une copie du tableau original puisque les copies d'objets sont coûteuses ?

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

Il s'agit exactement de N mouvements de MyObj où N est le nombre de MyObj dans votre vecteur original.

Les vôtres ont fait M lg M mouvements de MyObj et N copies, où M est le nombre d'objets et N le nombre d'objets uniques.

Le mien fait de l'allocation (de size_ts) que vous pouvez probablement nettoyer, mais cela le rendrait un peu moins clair.