Gibts ne Typenerkennung fuer Iteratoren ???

Segmentation Faulter

moin,

habn template geschrieben, dass in std::map und std::multimap das letzte
Auftreten (typename S) im X.second eines uebergebenen Wertes (auch typename S)
ermittelt. Uebergabe ist folgende:

template<typename InIt, typename K, typename S>
        InIt find_in(InIt BEG, InIt FIN, const S LAST_OPEN)

wobei InIt sowohl ein Iteraror als auch ein Reverse_Iterator sein kann.
Beim Reverse_Iterator habe ich nur das Problem, dass die Schleife bei Fund
abgebrochen weden muss (letzter Fund), beim Iterator aber nicht.
Dazu sollte ich eben an der Stelle wissen, um welchen Iterator es sich handelt.
typeid(InIt) schein nicht zu gehn, vielleicht hab ich's aber auch nur falsch angegangen...

SF

davie

zur laufzeit willst du feststellen, ob dein iterator ein reverse iterator ist?
das geht nicht besonders gut über typeid, da dein reverse_iterator vom normalen iterator abhängt, der von dem typ des containers abhängt. das simpelste und unsicherste mit rtti wäre

template <class It>
void foo (It it) {
  if (strstr(typeid(It).name(), "reverse")) {
    cout << "It ist wahrscheinlich ein reverse-iterator!\n";
  } else {
    cout << "It  ist wahrscheinlich kein reverse-iterator.\n";
  }
}

aber dir genügt wahrscheinlich eine compile-time lösung:

template <class It>
void foo (It it) {
   cout << "It ist ein normaler iterator.\n";
}

template <class It>
void foo (reverse_iterator<It> it) {
   cout << "foo mit einem reverse-iterator aufgerufen!\n";
}

Segmentation Faulter

hi,

die compile-time-Loesung reicht leider nicht, da es wie gesagt in einer
template-Funktion mal ein iterator, und mal ein reverse_iterator sein kann

Der Vorschlag:

if (strstr(typeid(It).name(), "reverse"))

klingt zwar recht nett, aber ich hab folgendes mal versucht,

const char* AKT = typeid(InIt).name();

naja, da kam dann IMMER:
AKT = 0x432bcc "St16reverse_iteratorSt17_Rb_tree_iteratorISt4pairKjSsERS3_PS3_EE
bei raus, egal ob ein iterator oder ein reverse_iterator uebgergeben wurde,
uebrigens das gleiche wie beim Vergleichswert:

const char* REV = typeid(std::map<K,S>::reverse_iterator).name();

Man muss ja nich immer alles verstehn

Jetzt haeng ich die Sache eh fuer ne Woche ann Nagel, und dann mal guggn.

Trotzdem Danke
SF

davie

Segmentation Faulter schrieb:

die compile-time-Loesung reicht leider nicht, da es wie gesagt in einer
template-Funktion mal ein iterator, und mal ein reverse_iterator sein kann

? zeig mal mehr code!

Gerard

Segmentation Faulter schrieb:

die compile-time-Loesung reicht leider nicht, da es wie gesagt in einer
template-Funktion mal ein iterator, und mal ein reverse_iterator sein kann

ich glaube da irs du dich, denn templates werden auch zu compilier zeit instanziert.
davie's compilier-zeit lösung sollte hier passen

Segmentation Faulter

davie schrieb:

? zeig mal mehr code!

ok, hier die template-Funktion find_in() [sollte eigentlich find_last_in() heissen]:

template<typename InIt, typename K, typename S>
        InIt find_in(InIt BEG, InIt FIN, const S LAST_OPEN){
            InIt RESULT = FIN;

            //type_info Tests
            const char* AKT = typeid(InIt).name();
            const char* REV = typeid(std::map<K,S>::reverse_iterator).name();
            //type_info Tests END

            while(BEG != FIN){
                    if(strcmp((*BEG).second.c_str(), LAST_OPEN.c_str()) == 0)
                        RESULT = BEG;
                        // hier sollte im Fall von reverse_iterator ein break; rein
                    ++BEG;
            }   
            return RESULT;
        }

Gerard schrieb:

ich glaube da irs du dich, denn templates werden auch zu compilier zeit instanziert.
davie's compilier-zeit lösung sollte hier passen

hmm, schon, aber der o.g. break sollte beim reverse_iterator schon rein, da
sonst ein reverse_iterator auf das erste Vorkommen anstatt des letzten zurueckgegeben wird, oder hab ich da jetzt nen Denkfehler?

SF

davie

bei dir steht doch eh schon zur Compilezeit fest, welchen Typ der iterator hat.
Wie wär's mit einem

template <class It>
inline bool is_reverse (It) { return false; }

template <class It>
inline bool is_reverse (reverse_iterator<It>) { return true; }

oder

template <class T>
struct IsReverse {
	static const bool value = false;
};

template <class T>
struct IsReverse <reverse_iterator<T> > {
	static const bool value = true;
};

für ein

if (is_reverse(iterator)) {
//bzw ein
if (IsReverse(IT)) {

wozu verwendest du überhaupt templates? du hast es doch hauptsächlich auf map iteratoren abgesehen.

Segmentation Faulter

davie schrieb:

bei dir steht doch eh schon zur Compilezeit fest, welchen Typ der iterator hat.

noe, tut's net, ich kann's ja mit beiden folgenden Argumenten aufrufen:

std::map<std::size_t,string>::iterator ERGEBNIS;
ERGEBNIS = find_in(map.begin(), map.end(), DieserString);
// oder
std::map<std::size_t,string>::reverse_iterator R_ERGEBNIS;
R_ERGEBNIS = find_in(map.rbegin(), map.rend(), DieserString);

davie schrieb:

wozu verwendest du überhaupt templates? du hast es doch hauptsächlich auf map iteratoren abgesehen.

Weil es auch eine MultiMap, und der Key Typ ein anderer sein kann:

std::multimap<unsigned long,string>::iterator ERGEBNIS;
ERGEBNIS = find_in(multimap.begin(), multimap.end(), DieserString);
// oder
std::multimap<unsigned long,string>::reverse_iterator R_ERGEBNIS;
R_ERGEBNIS = find_in(multimap.rbegin(), multimap.rend(), DieserString);

Bei den Beispielen mit dem

struct IsReverse { 
    static const bool value = false; 
};

versteh versteh ich jetzt den Sinn nicht so ganz (liegt aber eher an mir...)
Soll das erkennen, ob iterator oder reverse_iterator?

SF

Jester

Segmentation Faulter schrieb:

davie schrieb:

bei dir steht doch eh schon zur Compilezeit fest, welchen Typ der iterator hat.

noe, tut's net, ich kann's ja mit beiden folgenden Argumenten aufrufen:
[cpp]
std::mapstd::size_t,string::iterator ERGEBNIS;
ERGEBNIS = find_in(map.begin(), map.end(), DieserString);
// oder
std::mapstd::size\_t,string::reverse_iterator R_ERGEBNIS;
R_ERGEBNIS = find_in(map.rbegin(), map.rend(), DieserString);

Und jetzt beantworte folgende Frage: Wenn das in Deinem Source steht, ist dann zur Compile-Zeit festgelegt oder nicht?

Segmentation Faulter

also gut, aber das eine mal eben iterator, das andere mal reverse_iterator, und
diesen Unterschied muss ich doch in der Schleife durch den Container im Falle eines
reverse_iterators mit nem break quitieren.
Da hab ich u.U. ja auch ein generelles Verstaendnisproblem, von wegen zur
Compile-Zeit bzw zur Laufzeit:
Wird denn die template-Funktion fuer verschiedene Aufrufe anders compiliert?
Dann ist ja ne template-Funktion nur'n hack fuer'n programisten, und compiliert
gibt's die Funktion dann sooft, wie sie aufgerufen wird??
Diese Antworten wuerden mir wirklich weiter helfen, so zum Verstaednis eben...

SF

Jester

Die template-Funktion wird mehrfach instanziiert, für jede Kombination von Typen mindestens einmal.

Wenn Du

Funktion<int>(); schreibst, dann wird Funktion mit dem Typ int instanziiert und aufgerufen. Das instanziieren passiert zur Compilezeit.
Schreibst Du jetzt Funktion<float> dann wird eine neue Funktion generiert mit float als Parameter. usw.
Es wird nicht die gleiche Funktion wiederverwendet. Das template ist eine Vorlage, sozusagen eine Bauanleitung für Klassen/Funktionen bei denen noch ein paar Sachen offen gelassen wurden (die template-Parameter). Wenn Du die jetzt angibst, dann werden die entsprechenden Funktionen generiert. Aber dieses einfügen kann nur zur Compilezeit geschehen. Es gibt keine Syntax die es ermöglicht das erst zur Laufzeit zu tun, ginge ja auch nicht.

MfG Jester

Segmentation Faulter

Ok, das hab ich nun verstanden; ist es denn in diesem Fall besser, nur EINE
template-Funktion zu benutzen, in der ich dann zur "Compile-Zeit" im Falle eines
reverse_iterators bei Fund die Schleife durch den entsprechenden Container
abbreche, oder eine "normale" ueberladene Funktion zu schreiben, die dann aber
doppelt so oft geschrieben werden muss, wie es verschiedene Container bzw.
verschiedene Key-types gibt?
Was ist der bessere oder sinnvollere Programmierweg?

SF

Jester

Die Funktion als template zu schreiben ist natürlich sinnvoll, Du sagst ja selbst, man muß die Funktion nicht mehrmals schreiben. Und mit den oben gezeigten Tricks von davie kann man die Funktionen sogar abhängig vom Parameter leicht modifizieren.

templates sind oft gut geeignet wenn man eine Funktion mehrmals schreiben müßte, jedesmal nur mit kleinen Unterschieden.

Segmentation Faulter

Na dann war ich immerhin schon aufm richtigen Weg
Jetzt muss ich dann nur noch davies methode zu Erennung des reverse_iterators
begreifen, aber heut nicht mehr.
Danke soweit mal, frag dann wieder wenn ich richtig vor meinem Code sitz und's
nich mehr blick

Schoenen Abend
SF

Segmentation Faulter

Nabend,

hab's jetzt folgendermasen geloest:

template <typename K, typename S>
        inline bool REV_IT(std::map<K,S>::iterator it){
            return false;
        }

    template <typename K, typename S>
        inline bool REV_IT(std::multimap<K,S>::iterator it){
            return false;
        }

    template <typename K, typename S>
        inline bool REV_IT(std::map<K,S>::reverse_iterator it) {
           return true;
        }

    template <typename K, typename S>
        inline bool REV_IT(std::multimap<K,S>::reverse_iterator it) {
           return true;
        }
// und der Aufruf:
    template<typename InIt, typename K, typename S>
        InIt find_in(InIt BEG, InIt FIN, const S LAST_OPEN){
            InIt RESULT = FIN;
            while(BEG != FIN){
                    if(strcmp((*BEG).second.c_str(), LAST_OPEN.c_str()) == 0){
                        RESULT = BEG;
                        if(REV_IT<K,S>(BEG) == true)
                            break;
                    }
                    ++BEG;
            }   
            return RESULT;
        }

Mit davie's Vorschlag:

template <class It> 
inline bool is_reverse (It) { return false; } 

template <class It> 
inline bool is_reverse (reverse_iterator<It>) { return true; }

gab's nen Parse Error vor dem ">"-Zeichen in der hier letzten Zeile. War denn
sein Vorschlag nur schematisch, oder fehlt mir fuer das Argument: (reverse_iterator<It>)
was includiertes (und das Verstaendnis ).

Trotzdem funktioniert die o.g. ueberladene Funktion REV_IT, und wenn ich's richtig
verstanden hab, muesste ich sie bezueglich map und multimap garnicht ueberladen, da
sich die Iteratoren der sehr aehnlichen Container vermutlich von ihrer Struktur her
nicht unterscheiden?

Vielen Dank fuer alle Tips und Erklaerungen

SF

Jester

Nimm mal noch ein

#include<iterator>

dazu. und denk dran, daß das reverse_iterator-template in std íst.
Eine ganz waschechte Compile-time Lösung ist da übrigens nicht, aber die Entscheidung wird wahrscheinlich dann rausoptimiert.

MfG Jester

Segmentation Faulter

Hallo Jester,

das war der genau richtige Tip(std::reverse_iterator), somit funktioniert es auf alle Faelle ohne dass fuer map und multimap ueberladen werden muss.

Was meinst denn mit

Jester schrieb:

...aber die Entscheidung wird wahrscheinlich dann rausoptimiert.

Dass der Compiler dieses macht

Danke nochmal, schoenen Abend

SF

idefix

na, bist du ein Stück weiter gekommen. Freud mich für dich.

Habe mal'ne Frage zur Funktion find_in

also angenommen (position eintrag)
0 A, 1 B,2 C, 3 C, 4 D, 5 D, 6 E sind in der Mapppe.
suche C vorwärts würde position 3 ergeben
suche C rückwärts würde position 3 ergeben

Also soll die Funktion den letzten in vorwärts Richtung finden
und den ersten in rückwärts Richtung.

hätte da noch ein Vorschlag zu machen
partielle Spezialisierung von Templates
Na ja, guck es dir an vielleicht hilft es ja

template<class C>  C find_in(C first,C last,const string& s)
{
	std::cout<<"basis"<<std::endl;
	return first;
}
template<class C> C::iterator find_in(C::iterator first,C::iterator last,const string& s)
{
	std::cout<<"iterator"<<std::endl;

	C::iterator RetIter;
	while(first!=last)
	{
		if(first->second==s)
			RetIter=first;

		first++;
	}
	return RetIter;
}
template<class C> C::reverse_iterator find_in(C::reverse_iterator first,C::reverse_iterator last,const string& s)
{
	std::cout<<"reverse_iterator"<<std::endl;

	while(first!=last)
	{
		if(first->second==s)
			return first;

		first++;
	}
	return first;
} 
typedef std::multimap<int,string> MINT;

int main(int argc, char* argv[])
{
	MINT m_Int;
	MINT::reverse_iterator rIter;
	MINT::iterator Iter;

	m_Int.insert(MINT::value_type(0,"a"));
	m_Int.insert(MINT::value_type(1,"b"));
	m_Int.insert(MINT::value_type(2,"c"));
	m_Int.insert(MINT::value_type(3,"c"));
	m_Int.insert(MINT::value_type(4,"d"));
	m_Int.insert(MINT::value_type(5,"d"));
	m_Int.insert(MINT::value_type(6,"e"));

	Iter=find_in<MINT>(m_Int.begin(),m_Int.end(),"c");
	rIter=find_in<MINT>(m_Int.rbegin(),m_Int.rend(),"c");

	if(Iter!=m_Int.end())
	std::cout<<Iter->first<<Iter->second<<std::endl;
	if(rIter!=m_Int.rend())
	std::cout<<rIter->first<<rIter->second<<std::endl;
return 0;
}

Segmentation Faulter

hi,

idefix schrieb:

Habe mal'ne Frage zur Funktion find_in

also angenommen (position eintrag)
0 A, 1 B,2 C, 3 C, 4 D, 5 D, 6 E sind in der Mapppe.
suche C vorwärts würde position 3 ergeben
suche C rückwärts würde position 3 ergeben

Also soll die Funktion den letzten in vorwärts Richtung finden
und den ersten in rückwärts Richtung.

Ja, die Funktion soll in jedem Fall die letzte Uebereinstimmung (von vorne her gesehen) finden;
Aber vielleicht hab ich ja da mal wieder ein grundlegendes Verstaendisproblem, ich dachte, dass bei der Suche mit nem iterator von vorne, und mit nem reverse_iterator eben von hinten "gesucht" wird, so dass die iterator-Variante bei Deinem Beispiel die "Zeile:" 3 C, und bei der reverse_iterator-Variante die "Zeile:" 2 C zurueckgeben taete, wohlbemerkt ohne die break-Version bei der reverse_iterator-Variante.

Bei Deinem Vorschlag mit der ueberladenen Version wird bei der reverse_iterator-Variante schon beim ersten Fund returned, was (eigentlich sollte die Funktion
find_last_in(X,Y,S) statt find_in(X,Y,S) heissen) dann latuernich genauso den gewuenschten Effekt erzielt.

Ab hier wird's meines Erachtens philosophisch, bzw. es geht dann halt um Programmierstil. Zum Vergleich hier nochmal meine komplette Version:

template <class It>
     inline bool REV_IT(It){
         return false;
     }

template <class It>
     inline bool REV_IT(std::reverse_iterator<It>) {
         return true;
     }

template<typename InIt, typename K, typename S>
     InIt find_in(InIt BEG, InIt FIN, const S LAST_OPEN){
     InIt RESULT = FIN;
     while(BEG != FIN){
         if(strcmp((*BEG).second.c_str(), LAST_OPEN.c_str()) == 0){
             RESULT = BEG;
             if(REV_IT(BEG))
                 break;
         }
         ++BEG;
     }
     return RESULT;
}

21 zu 27 Zeilen, oder 485 zu 633 Bytes
Aber Spass beiseite, ich bin latuernich als Anfaenger auch an einer Bewertung der Programmierstils interessiert, hier in meinem Kaemmerchen die Dinge wertfrei nur so zu laufen zu bekommen kann's ja auch nicht sein, und Bytes bzw. Zeilen zu zaehlen scheint mir doch auch ein wenig zu lapidar.

Also bitte, keine Scheu vor Bewertung...

solong
SF