Administrace komentářů

Tak tady je ještě obecnější řešení než níže uvedené. Třídit můžeš implicitně pomocí std::set a std::map. Implementace jsou vyvážené stromy a nikde tam ani náhodou nehrozí hledání v O(n). Můžeš si podle potřeby udržovat několik různě setříděných „pohledů“ do téže datové struktury.

#include <map>
#include <set>
#include <string>

struct Something {
  std::string blah;
  size_t index;
};

static std::ostream& operator <<(std::ostream &out, const Something &sth) {
  out << "{\"" << sth.blah << "\", " << sth.index << "}";
  return out;
}

struct CompareSomething {
  bool operator ()(const Something *const &left,
                   const Something *const &right) const {
    return left->blah > right->blah;
  }
};

template<template<typename ... Args> class M, typename ... Args>
static void printmap(const M<Args...> &map, const std::string &message) {
  const auto end{map.cend()};
  auto i{map.cbegin()};
  std::cout << message << std::endl << '{';
  if (i != end) {
    std::cout << '{' << i->first << ", " << i->second << '}';
    for (++i; i != end; ++i)
      std::cout << ", " << '{' << i->first << ", " << i->second << '}';
  }
  std::cout << '}' << std::endl;
}

int main() {
  std::map<size_t, Something> indexmap{
    {0, {"data 0", 0}}, {1, {"data 1", 1}}, {2, {"data 2", 2}}};
  std::set<const Something*, CompareSomething> sortedview;
  for (const auto &pair : indexmap) sortedview.insert(&pair.second);
  printmap(indexmap, "Původní stav:");

  auto first{sortedview.cbegin()};
  indexmap.erase((*first)->index);
  sortedview.erase(first);
  printmap(indexmap, "Stav po odebrání prvního podle třídění:");

  indexmap.emplace(3, Something{"data 3", 3});
  sortedview.insert(&indexmap[3]);
  printmap(indexmap, "Stav po přidání dalšího prvku:");

  auto second{sortedview.cbegin()};
  ++second;
  indexmap.erase((*second)->index);
  sortedview.erase(second);
  printmap(indexmap, "Stav po odebrání druhého podle třídění:");

  return 0;
}

Dlužno dodat, že v tomto případě by bylo výrazně jednodušší použít místo Something jednoduše rovnou std::pair<size_t, std::string>. Tím by zmizela jedna úroveň zanoření struktur. Výše uvedený program vypíše:

Původní stav:
{{0, {"data 0", 0}}, {1, {"data 1", 1}}, {2, {"data 2", 2}}}
Stav po odebrání prvního podle třídění:
{{0, {"data 0", 0}}, {1, {"data 1", 1}}}
Stav po přidání dalšího prvku:
{{0, {"data 0", 0}}, {1, {"data 1", 1}}, {3, {"data 3", 3}}}
Stav po odebrání druhého podle třídění:
{{0, {"data 0", 0}}, {3, {"data 3", 3}}}