Tips labb 3

Prioritetsköer

En prioritetskö är en datastruktur där man kan fråga efter det element som är störst (eller minst) på ett effektivt sätt. (Ni som tidigare läst datastrukturer och algoritmer är redan bekanta med detta).

Ex:

priority_queue my_int_pq;  // [] tom
my_int_pq.push(5);         // [5] ett element
my_int_pq.push(9);         // [9, 5] två element
my_int_pq.push(7);         // [9, 5, 7] tre element, högsta först.

// Skriver ut 9,  [9, 5, 7] kvar i kön. top() tar inte bort något.
std::cout << my_int_pq.top() << '\n'; 

// Skriver ut 9,  [7, 5] kvar i kön efter pop().
std::cout << my_int_pq.pop() << '\n';

Detta illustrerar en max-kö, en min-kö (vilket du förmodligen vill använda i labben) har omvänd ordning.

Insättning av element i en prioritetskö är lite krångligare om man vill att insättningarna ska gå jättesnabbt, om man inte bryr sig om det kan man helt enkelt sortera datat så rätt element ligger först (eller sist) i containern.

Om man bryr sig om att insättning ska gå jättesnabbt bygger man prioritetskön som en heap-struktur. Se ex std::push_heap och std::pop_heap.

Prioritetskön i labben

I labben ska kön kunna hantera godtyckliga objekt, i synnerhet en struct som representerar en köporder eller en säljorder. Då måste vi berätta för kön hur den ska lagra sådana objekt och hur den kan ordna sådana objekt.

Då behöver vi förbereda oss med några extra delar.

struct order{};

Med lämpliga medlemmar och medlemsfunktioner.

Nu kan vi berätta för prioritetskön hur den kan lagra våra objekt.

pq pq;

Tyvärr har kön ingen aning om hur den ska ordna objekten inuti kön.

Här finns det många alternativ. Samtliga alternativ innefattar någon slags funktion som beskriver den inbördes ordningen mellan två ordrar. Vilken order är störst eller minst?

• Som funktionsobjekt

  struct comp_order{ bool operator()(const order& lhs, const order rhs){
      // returnera true om de är i ordning, annars false.}
  

• Som lambda

  auto comp_order = [](const order& lhs, const order rhs){
      // returnera true om de är i ordning, annars false.}
  

• Som fri funktion

  bool comp_order(const order& lhs, const order& rhs){
      // returnera true om de är i ordning, annars false.}
  

• Som överlagrad medlemsoperator

  bool order::operator<(const order& rhs){ // tidigare lhs är nu this.}
  

Första och andra alternativet är enklast. Den fria funktionen ger lite bökig syntax eftersom funktionsnamnet ses som en funktionspekare och inte en direkt hänvisning till funktionen. Den överlagrade medlemsoperatorn är bekymmerssam eftersom den beskriver en naturlig ordning mellan orderobjekt. Någon sådan ordning finns inte. En överlagrad fri operator har samma problem. En medlemsfunktion är också ett alternativ, men den medför en massa syntaktiskt krångel och man vinner inget på det.

Så för alternativ ett landar man i att skapa en kö som kan ordna objekten på följande vis

pq pq;

Eller (detta är användbart om jämförelsen måste veta nåt på förhand, det behöver inte vår jämförelse)

comp_order comp;
pq

Tillbaka till prioritetskön

template
class pq{
    std::vector data;
...

template
class pq{
    std::vector data;
    COMP comp;

if(comp(element1, element2))...

Köp             Sälj
17 JVA          16 Pendel
18 Pendel       17 JVA
20 JVA          21 Wallenburg
22 Wallenburg   22 Pendel

JVA köper av Pendel(16) för 17.
Pendel köper av JVA(17) för 18.
Wallenburg köper av Wallenburg(21) för 22.