Comment effacer les n derniers éléments de la carte C++?

Question

Existe-t-il un moyen agréable et simple de trouver nth element dans C++std::map? Particulièrement je cherche un algorithme pour effacer les derniers éléments k du map. Cela aurait du sens de récupérer l'itérateur au nth element et d'appeler le std::map::erase. L'exigence est que la complexité ne souffre pas - cela devrait être possible d'effacer la plage d'éléments dans O(N).

La copie des données ne doit pas être effectuée uniquement pour effacer les éléments. Par exemple, une solution consiste à copier les données dans std::vector, puis faites std::nth_element sur std::vector, puis std::map::find pour trouver l'itérateur afin de savoir d'où effacer.

L'une des autres solutions consiste à simplement itérer sur std::map en maintenant une variable de compteur sur le nombre d'éléments à supprimer. Cela donnerait O(n). Est-ce possible de remplacer la boucle for par STL algorithm?

Answer 1

Les cartes n'offrent pas un meilleur accès aux éléments par index, par exemple vector ou deque. Vous pouvez le faire en utilisant std::advance, mais cela prend du temps qui est proportionnel à k. Si k est petit, il sera souvent assez rapide - cela implique essentiellement de suivre les pointeurs k. Voici un exemple:

template<typename Map> 
void erase_last_elements(Map & map, ptrdiff_t k) 
{ 
    assert(k >= 0); 
    assert(map.size() >= (size_t)k); 
    typename Map::iterator i = map.end(); 
    std::advance(i, -k); 
    map.erase(i, map.end()); 
} 

Sinon, si vous utilisez Boost, vous pouvez utiliser boost::prior:

template<typename Map> 
void erase_last_elements(Map & map, ptrdiff_t k) 
{ 
    assert(k >= 0); 
    assert(map.size() >= (size_t)k); 
    typename Map::iterator i = boost::prior(map.end(), k); 
    map.erase(i, map.end()); 
} 

Sinon, vous devrez maintenir un index séparé, ou utiliser un autre conteneur. Quelque chose comme un trié vector pourrait être approprié, si vous n'insérez pas et ne supprimez pas trop d'éléments.

Answer 2

Édition: réponse non applicable après modification du message d'origine.