Komplexer Ausdruck im vector suchen

case

Folgendes Problem:
Es existiert ein vector in dem nach folgender Bedingung gesucht werden soll:
(value_n+1 - value_n) < (value_n - value_n-1)

Hat jemand eine jede Idee welche STL-Algorithmen ich hier anwenden muss.
Ich habe mir meinen eigenen Algorithmus geschrieben, würde aber lieber mit den STL Algorithmen rumwerkeln.

icarus2

Wenn du nur einmal suchen musst, dann std::find_if .

Falls du mehrfach suchen musst zuerst mit std::sort sortieren und dann std::bsearch verwenden.

icarus2 schrieb:

Wenn du nur einmal suchen musst, dann std::find_if .

Geht nicht wenn die Bedingung von den Nachbarn abhängt.

icarus2 schrieb:

Falls du mehrfach suchen musst zuerst mit std::sort sortieren und dann std::bsearch verwenden.

bsearch? Du meinst wohl lower_bound. Geht aber nicht im Fall das OP.

@OP: Geht nicht ausschliesslich mit der STL ohne einen Hilfsvektor. Ist es ok für dich, Boost.Range zu verwenden?

case

Hallo zusammen

Vieleicht ist das ganze falsch rüber gekommen.
Value_n-1 und Value_n+1 meint die Werte rechts und links neben n.
find_if kann ich hier glaub ich nicht verwenden, da ich immer nur den aktuellen
iterator kriege und nicht rechts und links die Werte.
Boost::Range kann ich leider nicht verwenden, da ich einen uralt Compiler (Borland Cbuilder 5.0) im Einsatz habe.
Boost::bind kann ich aber benutzen.
Im Moment habe ich das Ganze so gelöst, finde ich aber nicht so toll

#include <vector>
#include <functional>
#include <iterator>
#include <iostream>
#include <boost/next_prior.hpp>

using std::vector ;
using std::back_inserter ;
using std::plus ;
using std::copy ;
using std::ostream_iterator ;
using std::cout ;

template <class InputIterator,class BinaryOperation,class CompareOperation>
  InputIterator find_difference(InputIterator first, InputIterator last,BinaryOperation binary_op,CompareOperation compare)
{
	if (first!=last)
	{				
		InputIterator next ;
		InputIterator prev=first ;
		while ((next=boost::next(first))!=last)
		{						
			if (prev!=first)
			{
				if (compare(binary_op(*next,*first),binary_op(*first,*prev)))
					return first ;
			}				
			++first ;			
			prev=boost::prior(first) ;
		}
	}
	return last ;
}

int main()
{
	vector<int> data ;
	for (int i=0;i<11 ;i++)
		data.push_back(i) ;
	data.push_back(3) ;
	data.push_back(5) ;
	data.push_back(1) ;
	copy(data.begin(),data.end(),std::ostream_iterator<int,char>(cout,",")) ;
	cout << "\n" ;

	vector<int>::iterator finditer=find_difference(data.begin(),data.end(),std::minus<int>(),std::less<int>()) ;	
	if (finditer!=data.end() && finditer!=data.begin())
		std::cout << "iter : " << *finditer << " iter-1 : " << *boost::prior(finditer) ;
	//copy(new_values.begin(),new_values.end(),std::ostream_iterator<int,char>(cout,",")) ;
}

Skym0sh0

huh schrieb:

icarus2 schrieb:

Wenn du nur einmal suchen musst, dann std::find_if .

Geht nicht wenn die Bedingung von den Nachbarn abhängt.

Frage meinerseits dabei:
Die STl-Algorithmen (in unserem Fall std::find_if) erwarten ja etwas, das wie eine Funktion aufrufbar ist. Also wenn gewünscht auch ein Funktionsobjekt, welches einen zustand speichern kann.

Könnte man dann nicht bei der ersten Iteration einfach den Wert speichern, und bei der zweiten bzw. dritten Iteration dann die jeweils alten Werte mit in die Rechnung mit einbeziehen?

Anders aufgescheieben ist das

x[n-1] - 2*x[n] + x[n+1] < 0

wobei die linke Seite einer Annäherung der zweiten Ableitung entspricht. Du suchst also Stellen mit negativer Krümmung.

Ich war kurz davor Boost's Range-Adapter vorzuschlagen, weil ich in Erinnerung hatte, dass da ein Adapter dabei ist, der zwei benachbarte Elemente auf etwas anderes mappen kann (z.B. ihre Differenz) und so damit das "Signal" 2mal hintereinander ableiten könnte. Aber es gibt leider doch nur adjacent_filtered. Schade.

Vielleicht lohnt sich ja für Dich auch eine Filter-Funktion, die einen Vektor auf einen anderen abbildet und dabei einen beliebigen linearen Filter anwenden kann (wie z.B. einen Differentiator 1. oder 2. Ordnung).

In Rust könnte man das jetzt schön mit windows machen. SCNR!

So etwas wäre in C++ natürlich auch möglich, also einen Iterator, der über alle 3-elementige Vector-Ausschnitte rüberläuft und dann die Krümmung über ein Skalarprodukt ausrechnet. Gibt's nur leider nicht eingebaut, sowas.

case

Danke an euch alle.
Lebe jetzt mit meinem oben beschriebenen Template.
Ist nicht so toll, funktioniert aber.

sollte die funktion nicht besser find_first_difference heissen?

case

Stimmt, werde ich anpassen.