Prüfen der Werte in einem vector

Hallo.

Suche nach einer Möglichkeit um zu überprüfen ob die Werte in einem std::vector stetig steigen oder fallen oder ob sie durcheinander sind?

Wie würdet ihr das am schnellsten lösen? Dazu kommt noch dass man einen Bereich angeben kann von dem man das wissen will. Also z.b. ab Index 5 - 10..

Martin Richter

Da Du sowieso jeden Wert prüfen musst hast Du O(n).
Also fängst Du unten an und gehts noch oben, ds Ganze mit 2 Iteratoren.

template<class T> bool CheckAscending(T::const_iterator next, T::const_iterator end)
{
    // Note that an empty range returns true!
    while (next!=end)
    {
        T::const_iterator prev = next++;
        // Only one item left?
        if (next!=end)    // Nachträglich korrigiert
        {
            // Compare neighbors
            if (*next<*prev)
                return false;
        }
    }
    return true;
}

Na ja fast. Jetzt weiß ich aber nur ob sie steigen. Wenn ich false erhalte weiß ich nicht ob sie fallen oder durcheinander sind.

und wieso soll prev = next++ sein. prev heißt doch previous und heißt vorher.
next++ ist doch aber der nachfolgende?

Und das hier

if (next==end)

müsste doch auch

if (next!=end)

heißen oder etwa nicht.

Martin Richter

1. Das == war ein Typo!
BTW: War einfach so reingehackt.
2. Ich benütte nextund prev ganau so wie die Variablen heißen.
Ich Merke mir den aktuellen iterator, gehe auf den nächsten, sofern der noch was gültiges ist vergleiche ich prev und next.

Aber Du kannst die Dinger nennen wie Du willst.

2. Ich benutze next und prev ganau so wie die Variablen heißen.

Ja aber du zählst doch next hoch und weißt dann dies prev zu. Dann steht in prev das selbe wie in next. Oder nicht?

Und wie unterscheide ich denn nun ob sie nun fallen oder steigen oder durcheinader sind. Also

-1 durcheinader
0 fallend
1 steigend.

das sollte ich haben.

Martin Richter

MeinFreund schrieb:

2. Ich benutze next und prev ganau so wie die Variablen heißen.

Ja aber du zählst doch next hoch und weißt dann dies prev zu. Dann steht in prev das selbe wie in next. Oder nicht?

Neee! prev = next++; speichert den aktuelen Wert von next in prev und zählt dann next um eins weiter

Ansonsten ist der Code doch absolut trivial (Code einfach nur so geschrieben ohne Test):

enum Order
{
   orderUnsorted,
   orderEqual,
   orderAscending,
   orderDescending,
 };

template<class T> Order CheckAscending(T::const_iterator next, T::const_iterator end) 
{ 
    Order currentOrder = orderEqual;

    // Note that an empty range returns true! 
    while (next!=end) 
    { 
        T::const_iterator prev = next++; 
        // Check the order we have here        
        // Only one item left? 
        if (next!=end)    
        { 
            // Compare neighbors 
            Order newOrder = orderEqual;
            if (*prev<*next) 
                newOrder = orderAscending;
            if (*prev>*next) 
                newOrder = orderDescending;

            // Any change
            if (newOrder==orderEqual || currentOrder==newOrder) // EDIT: currentOrder==newOrder hinzugefügt
                // No change;
                ;
            else if (currentOrder==orderEqual)
                // Order changes
                currentOrder = newOrder;
            else
                // New order and previous order are different
                // and the current order is not euqal.
                // must be unsorted
                return orderUnsorted;
        } 
    } 
    return currentOrder; 
}

Nö also dass funktioniert meiner Meinung nach nicht.

Martin Richter

MeinFreund schrieb:

Nö also dass funktioniert meiner Meinung nach nicht.

Begründung?

nehmen wir mal an im ersten Durchlauf ist

newOrder = orderAscending;

folgendes trifft zu

else if (currentOrder==orderEqual)

somit

currentOrder = orderAscending;

beim zweiten durchlauf ist wieder

newOrder = orderAscending;

Folgendes trifft beides nicht zu

if (newOrder==orderEqual)
   // No change;
   ;
else if (currentOrder==orderEqual)
   // Order changes
   currentOrder = newOrder;

somit

else
   return orderUnsorted;

Oder habe ich was übersehen?

Martin Richter

Stimmt.
Da fehlt nur der currentOder==newOrder!

if (newOrder==orderEqual || currentOrder==newOrder)
    // No change;
    ;