Dotaz: Seřadit pole a udržování indexů

[Petr]

Mám pole objektů, ve kterých je potřeba pamatovat si pozici, na které jsou. Pole chci seřadit, ale při přesouvání položek potřebuju prohodit i indexy. Jde k tomu použít nějaký algoritmus ze standardní knihovny, nebo si musím napsat nějaký řadící algoritmus svůj? Příklad:

Před řazením:
{ {"data 0", 0}, {"data 1", 1}, {"data 2", 2} }

Po řazení podle toho řetězce opačně:
{ {"data 2", 0}, {"data 1", 1}, {"data 0", 2} }

Odpovědi

[Petr]

Zapomněl jsem zmínit jazyk: C++

[Kit]

Zřejmě bude nejjednodušší vytvořit nad tímto polem pole ukazatelů, napsat vhodnou funkci pro porovnání a zavolat knihovní sort.

[rastos]

Niečo mi uniká. Tak mám tri doplňujúce otázky:

a) čo je jedným prvkom poľa? Podľa zadania to vyzerá, že je to štruktúra obsahujúca jeden string a jedno číslo. Správne?

b) keď sa prvok poľa triedením dostane na iné miesto v poli, má tento prvok v sebe stále rovnaké dáta ako pred triedením? Podľa toho príkladu v otázke to tak nie je.

c) v tom príklade, ktorý si uviedol po zotriedení nemáš informáciu o tom, kde ten prvok bol pred triedením. Je tak? Znamená to, že do prvku chceme pridať ďalšiu informáciu, ktorá nám bude hovoriť, kde bol ten prvok predtým?

[Petr]

Prvkem pole je nějaká struktura s daty, která zároveň obsahuje současný index daného prvku v poli. Nazvěme třeba Prvek:

struct Prvek
{
  // nejaka data
  size_t index_v_poli;
};

Pak mám pole těch prvků, resp. v poli budou nakonec ukazatele na dané prvky, protože chci, aby se neměnila jejich adresa:

{
  { /* ... */, 0 },
  { /* ... */, 1 },
  { /* ... */, 2 },
  { /* ... */, 3 },
  { /* ... */, 4 },
}

Z pole si někam třeba uložim položku s indexem 2, dostanu Prvek*, ukazující na { /* ... */, 2 }. Pak třeba do pole něco přidám, nebo ho nějak jinak seřadím. Chci, aby se index ve vráceném prvku patřičně aktualizoval, aby měl správný index a já pak mohl říct třeba "smaž prvek Prvek*" a nemusel ho v poli vyhledávat v O(n).

[Jardík]

I když neznáš index prvku k odebrání, tak jeho vyhledání v O(n) být nemusí. Pokud stále znáš porovnávací funkci, kterou si pole řadil, tak ji můžeš použít pro hledání prvku, třeba binárním vyhledáváním. Bude to ale záviset na náročnosti té porovnávací funkce a počtu prvků v poli. U menších polích může být hledání pointeru v poli lineárně rychlejší, než použití binárního vyhledávání a porovnávání obsahů (protože ukládáš pointery, dochází k dereferenci každého porovnávaného prvku a spoustě cache miss (česky?)).

Co se týče dotazu, tak např. std::sort bude používat k prohození prvků buď std::swap (pokud provedeš specializaci, tak tam by se teoreticky indexy prohodit daly, ale pak swap nefunguje, tak jak by správně měl a zřejmě rozbiješ něco jiného), nebo bude používát move konstruktor či move operator (takže tam bys teoreticky nesměl aktualizovat ten index). A nebo by taky mohl swap použít copy konstruktor/operátor, pokud move nebude noexcept.

[lertimir]

Myslím si, že pocivé by bylo i uvádět, k čemu je potřeba používat takovou strukturu. Pokud to není školní úloha tak celé mi to připadá poněkud zvláštní. Takto se to v reálu moc nedělá. Pokud bych něco podobného potřeboval. Tak jednak bych ani nepřetřiďoval pole, ale měl jedno nebo více dalších indexních polí, které by obsahovaly pole pointerů setříděných podle specifikovaných kritérií. Přetřídění je strašně náročná operaces asymtotickou složitostí O(n*log(n)) v nejlepším případě a často spíše O(n^2). Za druhé mám pocit, že primárně jde o to vyrovbit konzistentní metodu Smaž u objektu Prvek. V popsaném a žádaném musí metoda samž zasáhnout do všech objektů v poli, které jsou v poli za smázávaným prvkem, navíc všechny objekty v poli za smazávaným prvkem musí posunout o jeden prvek. Všechno nesmírně náročné operace. Pokud tohel je otázka na skutečnou produkci s většími daty tak potěš s výkonem. Pokud mám pole stříděné (a jedno jak) Tak vyhledání je přece O(log(n)). A místo mazání bych jen nastavoval flag reprezentující smazání a ktualizoval indexy.

[Andrej]

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

[Andrej]

Ano, je na to standardní algoritmus zvaný std::sort(). Aktualizaci indexů si pak už musíš napsat sám, což ale není nijak extra těžké:

#include <algorithm>
#include <iostream>
#include <string>

struct Something {
  std::string blah;
  size_t index;
  bool operator <(const Something &right) const { return blah > right.blah; }
};

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

template<typename T, size_t N>
void printarray(const T(&array)[N], const std::string &message) {
  const auto begin{std::begin(array)}, end{std::end(array)};
  std::cout << message << std::endl << '{';
  if (begin < end) {
    std::cout << *begin;
    for (auto i{begin + 1}; i < end; ++i) std::cout << ", " << *i;
  }
  std::cout << '}' << std::endl;
}

int main() {
  Something array[]{{"data 0", 0}, {"data 1", 1}, {"data 2", 2}};
  printarray(array, "Počáteční stav:");

  std::sort(std::begin(array), std::end(array));
  printarray(array, "Stav po std::sort():");

  size_t counter{0};
  for (Something &s : array) s.index = counter++;
  printarray(array, "Stav po aktualizaci indexů:");

  return 0;
}

Výše uvedený program vypíše následující:

Počáteční stav:
{{"data 0", 0}, {"data 1", 1}, {"data 2", 2}}
Stav po std::sort():
{{"data 2", 2}, {"data 1", 1}, {"data 0", 0}}
Stav po aktualizaci indexů:
{{"data 2", 0}, {"data 1", 1}, {"data 0", 2}}