virtual template member function workaround gesucht

314159265358979

Schritt 1: Code des TE nochmal ansehen.
Schritt 2: Stichwort: Extension

GorbGorb

Versuch mal folgendes, um der rtti Beine zu machen:

inline unsigned int next_id()
{
    static unsigned int current_id = 1;

    return current_id++;
}
template< class Type >
class t_id
{
    static const unsigned int value;
};
template< class Type >
const unsigned int t_id< Type >::value = next_id();

t_id< X >::value ist jetzt für jede Klasse einzigartig (Achtung: funktioniert vermutlich nicht, wenn dlls im Spiel sind).
Jetzt kannst du noch die Suche von O( n ) auf O( 1 ) bringen:
Statt linearer Suche verwendest du ein Hilfsarray. lookup_vector[ t_id< Type >::value ] soll die Anzahl der Objekte eines bestimmten Typs beinhalten. Dazu muss sich jedes Objekt in dem lookup_vector registrieren (inklusive aller base classes!), wenn es in den Container aufgenommen wird und abmelden, wenn es entfernt wird:

template< class BaseType , class DerivedType >
class derived_helper
  : public BaseType
{
public:
    static void add_indices( std::vector< unsigned int >& lookup_vector )
    {
        ++lookup_vector[ t_id< DerivedType >::value ];
        BaseType::add_indices( lookup_vector );
    }
    static void remove_indices( ... )
    {
         ...
    }
};

Wenn du davor hattest

A;
B : A;

machst du jetzt halt

A;
B : derived_helper< A , B >

Du musst also die alte codebase verändern, darum kommst du wohl nicht rum (sind aber minimale Änderungen, denke ich).
Wenn du jetzt ein Objekt zu deinem Container hinzufügst, rufst du für den jeweiligen Type eben die add_indices funktion mit deinem std::vector< unsigned int > lookup_vector auf, wenn du eines entfernst die remove_indices funktion (Anm.: Falls du Objekte über einen base pointer übergibst muss die Funktion virtuell und nicht statisch sein).
Deine has< T > funktion wird dann einfach ein

template< class Type >
bool has()
{
    return lookup_vector[ t_id< Type >::value ] != 0;
}

Statt einem lookup_vector kann man denke ich auch eine andere Datenstruktur verwenden, beispielsweise ein set. Dadurch gewinnt man vielleicht etwas Speicher, verliert aber Zeit und hat wieder beim eine binary search drinnen, verliert also O( 1 ). Ist davon abhängig, wie viele verschiedene Typen tatsächlich im container gespeichert werden, was sinnvoller ist.

@dot: Der Code von nurf erinnert eher an etwas wie das:

#define for_each(i, l) \
    for (__decltype((l).begin()) i=(l).begin(), i##_end=(l).end();
         i != i##_end; ++i)

So nutzt nurf den Wurf:

template <typename T> bool has()
  {
    for_each(skill, skills)
    {
       // hier liegt das Problem
       if (dynamic_cast<T*>(skill) != 0 )
       { return true; } // Guck mal da: returniert aus has()
    }
    return false;
  }

dot

314159265358979 schrieb:

Schritt 1: Code des TE nochmal ansehen.
Schritt 2: Stichwort: Extension

MSVC hat keine for_each Extension, nur eine for each Extension. Das muss also irgendein Makro sein...

GorbGorb

Abgesehen davon:

main(...)

Die "..." stören niemanden oder was? Vielleicht darüber nachgedacht, dass der TE nur Pseudocode gepostet hat, um zu veranschaulichen, worum es geht? Statt Hilfe kommt nur dummes Gelaber von language lawyern (naja, eigentlich nur einem) der keinem was bringt... wirklich unnötig.

hustbaer

Nur mal so ne Idee, ungetestet (weiss nichtmal ob es 1:1 so compiliert), aber müsste so oder so ähnlich hinhauen:

class Container 
{ 
    std::vector<Skill*> skills; 

    typedef std::pair<intptr_t, intptr_t> SkillMapKey;
    typedef std::map<SkillMapKey, bool> SkillMap;  // evtl. hash_map verwenden wenns hier wirklich viele Einträge geben sollte
    SkillMap skillMap;

    SkillMapKey make_skill_map_key(Skill const* concreteSkill, type_info const& interfaceType)
    {
        return SkillMapKey(
            reinterpret_cast<intptr_t>(&typeid(*concreteSkill),
            reinterpret_cast<intptr_t>(&interfaceType));
    }

    template <typename T> bool has(Skill* concreteSkill)
    {
        SkillMapKey key = make_skill_map_key(concreteSkill, typeid(T));

        SkillMap::iterator it = skillMap.find(key);
        if (it != skillMap.end())
            return it->second;
        else
        {
            bool result = dynamic_cast<T*>(concreteSkill) != 0;
            skillMap[key] = result;
            return result;
        }
    }

    template <typename T> bool has() 
    { 
        for_each(skill, skills) 
        { 
            // hier jetzt hoffentlich schneller
            if (has<T>(skill)) 
                return true;
        } 

        return false; 
    } 
}

Wenn der Inhalt des Containers recht statisch ist könnte man natürlich noch weiter optimieren, so dass die meisten Abfragen überhaupt keine Schleife mehr brauchen.

ps: Falls "Skill" Objekte in DLLs/SOs implementiert sind, die dynamisch geladen ~~oder~~ und entladen werden könnte das Probleme machen. Davon abgesehen müsste es mMn. funktionieren.

dot

GorbGorb schrieb:

Statt Hilfe kommt nur dummes Gelaber von language lawyern (naja, eigentlich nur einem) der keinem was bringt... wirklich unnötig.

Ja. Das Problem ist nur, dass man hier ohne genauere Information über die konkrete Anwendung keine hilfreiche Antwort geben kann. Denn eine gute Lösung für das Problem würde vermutlich eine grundlegende Änderung des Designs bedeuten. Und wie diese jetzt genau aussehen könnte kann man so allgemein nicht sagen...

GorbGorb

dot schrieb:

GorbGorb schrieb:

Statt Hilfe kommt nur dummes Gelaber von language lawyern (naja, eigentlich nur einem) der keinem was bringt... wirklich unnötig.

Ja. Das Problem ist nur, dass man hier ohne genauere Information über die konkrete Anwendung keine hilfreiche Antwort geben kann. Denn eine gute Lösung für das Problem würde vermutlich eine grundlegende Änderung des Designs bedeuten. Und wie diese jetzt genau aussehen könnte kann man so allgemein nicht sagen...

Brauchst dich nicht angegriffen fühlen, ich hab dich ja gar nicht gemeint
Der TE meinte ja, es sei ein gewachsenes System, er kann vom design her wohl nicht viel ändern ohne Arbeit. Sein Problem ist diese Funktion, und ich denke da kann man ja was tun (siehe hustbaers und meine Vorschläge).

EDIT: hustbaer, wenn ich das richtig verstanden habe spart has(Skill* concreteSkill) den dynamic cast, wenn concreteSkill eines der gesuchten Objekte ist, oder? Dürften nicht vielmehr die dynamic_casts mit negativem Ergebnis das bottleneck sein?

dot

Ich fühl mich auch nicht angegriffen, ich wollt eher indirekt dem Threadersteller sagen, das er uns konkrete Information geben soll, wenn er konkrete Antworten will

hustbaer

Muaha.
Hier stand Müll

hustbaer

GorbGorb schrieb:

EDIT: hustbaer, wenn ich das richtig verstanden habe spart has(Skill* concreteSkill) den dynamic cast, wenn concreteSkill eines der gesuchten Objekte ist, oder? Dürften nicht vielmehr die dynamic_casts mit negativem Ergebnis das bottleneck sein?

Nö, nicht ganz.
Der dynamic_cast wird pro Kombination aus konkreter Skill-Klasse und Skill-Interface nur 1x ausgeführt.

Wenn also die Anfrage reinkommt "hat Objekt a das Interface X?".
Dann hole ich mir per typeid der "most derived Type" von a - nennen wir den "A".

Dann gucke ich ob ich die Kombination "A, X" schon mit dynamic_cast ausprobiert wurde.
Wenn ja gibt es einen Eintrag in der map, der Wert ist dann das Ergebnis (also true heisst A erbt von X, false heisst A erbt nicht von X).

Wenn nicht, dann wird das Ergebnis über dynamic_cast ermittelt, und in der Map eingetragen.

Der "Trick" (Hack) dabei ist nun dass ich intptr_t eintrage, die aus der Adresse der über typeid() ermittelten type_info Instanz erzeugt werden.

Das setzt natürlich voraus, dass a) beim reinterpret_cast keine Informationen verloren gehen. Genau dafür ist intptr_t aber da, d.h. das müsste hinhauen.
Weiters setzt es voraus, dass an einer Adresse einer type_info Instanz in Zukunft nie nie niemals eine andere type_info Instanz stehen kann.
Der Standard garantiert das soweit ich weiss nicht, aber so lange man keine DLLs/SOs dynamisch entlädt funktioniert es in der Praxis zuverlässig.

hustbaer

So, 2. Versuch ohne Template Bloat:

class Container 
{ 
    std::vector<Skill*> skills; 

    typedef std::pair<intptr_t, intptr_t> SkillMapKey;
    typedef std::map<SkillMapKey, bool> SkillMap;  // evtl. hash_map verwenden wenns hier wirklich viele Einträge geben sollte
    SkillMap skillMap;

    template <typename T> static bool interface_test(Skill* concreteSkill)
    {
        return dynamic_cast<T*>(concreteSkill) != 0;
    }

    typedef bool interface_test_fun(Skill*);

    bool has_impl(Skill* concreteSkill, intptr_t interfaceTypeID, interface_test_fun* tester)
    {
        SkillMapKey key(reinterpret_cast<intptr_t>(&typeid(*concreteSkill), interfaceTypeID);

        SkillMap::iterator it = skillMap.find(key);
        if (it != skillMap.end())
            return it->second;
        else
        {
            bool result = tester(concreteSkill);
            skillMap[key] = result;
            return result;
        }
    }

    bool has_impl(type_info const& interfaceType, interface_test_fun* tester)
    {
        intptr_t interfaceTypeID = reinterpret_cast<intptr_t>(&interfaceType);

        for_each(skill, skills) 
        { 
            // hier jetzt hoffentlich schneller
            if (has_impl(skill, interfaceTypeID, tester)) 
                return true;
        } 

        return false; 
    } 

    template <typename T> bool has() 
    {
        return has_impl(typeid(T), &Container::interface_test<T>);
    } 
}

C++ kennt kein for_each als Sprachkonstrukt und main muss int zurückgeben. Hässlicher MSVC Schrott.

Das bezog sich auch auf for_each du Pfeife. Lern Texte verstehen.

Lern du erstmal Texte schreiben, du Pfeife.

Relevant: http://xkcd.com/1028/

nurf

Danke schonmal für die vielen Anregungen.
Das mit dem for_each hatte ich nur zur anschaulichen Vereinfachung eingebaut.

Mir schwebt eigentlich eher sowas vor, wie jeder Klasse eine eindeutige ID/Enum zu geben. Dann könnte man sowas machen wie:

template <typename T> bool has() const
{
  return (T::ID == this->ID());
}

Mit dem Ziel die ID zur Compile-Zeit zu vergeben (notfalls muss man die Klassen-IDs in einem anderen Header pflegen, als Enum).

Über die "letzte" Idee von hustbär hatte ich auch schon nachgedacht, das Problem von virtual templates durch eine weitere Indirektion zu lösen.

Wenn der Lookup der typeid schneller ist als dynamic_cast, kann man für eine reine has-Prüfung auch auf die typeid umsteigen.

dot

Erklär uns doch mal, um was für eine konkrete Problemstellung es da eigentlich geht...

wxSkip

//TypeID.hpp
extern int t_id_counter;

template<typename T> int GetTypeID()
{
    static int i = -1;
    if(i == -1) i = t_id_counter++;
    return i;
}

//TypeID.cpp
#include "TypeID.hpp"
int t_id_counter = 0;

EDIT: Ist zwar nicht Compile-Zeit, dafür aber der Runtime-Aufwand zu vernachlässigen. Eine Compilezeit-ID wird wohl nur mit irgendwelchem typeid()-Kram (und damit nicht standardkonform) generierbar sein (vielleicht erst mit C++11), aber dann auch nur, wenn man aus typeid(T).name() eine eindeutige ID generiert, die demzufolge länger als int wäre...

Und was spricht gegen einen Referenzzähler?

GorbGorb

nurf schrieb:

Mir schwebt eigentlich eher sowas vor, wie jeder Klasse eine eindeutige ID/Enum zu geben. Dann könnte man sowas machen wie:
template <typename T> bool has() const
{
  return (T::ID == this->ID());
}

dynamic_cast tut aber mehr, als nur eine id vergleichen. Folgendes Szenario:

A
B : A
C : B

container.add( C() );
container.has< B >();

Wird mit dieser Methode false ergeben. Was du tun könntest, ist ein bitset zu verwenden, in das sich jede base class an der Stelle Base::ID einträgt. Dazu müsstest du aber wieder die alten header files verändern oder jede Vererbungsbeziehnung manuell irgendwie neu bekannt machen (um diesen Schritt kommst du aber nicht rum, wenn du rtti komplett ersetzen willst, du musst über die Vererbungsbeziehnungen irgendwie Bescheid wissen).

Shade Of Mine

GorbGorb schrieb:

Wird mit dieser Methode false ergeben. Was du tun könntest, ist ein bitset zu verwenden,

Oder noch einfacher:
Statt getID() eine Funktion hasID() verwenden die an den parent weiter reicht wenn false rauskommt

Aber wir brauchen eine genaue definition der Anforderung um eine gute Antwort geben zu koennen.

nurf

Shade Of Mine schrieb:

Aber wir brauchen eine genaue definition der Anforderung um eine gute Antwort geben zu koennen.

Prinzipiell stehen die Anforderungen im ersten Post.
Das Kind ist in den Brunnen gefallen, weil das ganze Design und nun außerdem die Performance schlecht ist. Profiling-Analyse sagt dynamic_cast zieht zu viel CPU-Last.
Wie erwähnt geht um viele Klassen, die in 2. oder 3. Stufe von der Basis-Klasse abgeleitet sind.
**Ziel:**Performance verbessen, bspw. den dynamic_cast irgendwie obsolete machen. Weitere Ziele wären: möglichst viel zur Compile-Zeit (boost::is_same<A,B>) oder möglichst anfängersicher.
Eine realistische absolut häßliche Möglichkeit wäre es auch alle Class-Test-Routinen in die Basis-Klasse zu verlagern und dann bei Bedarf zu überschreiben.

class BaseSkill 
{
  virtual bool hasASkill() { return false; }
  virtual bool hasBSkill() { return false; }
}
class ASkill : public BaseSkill
{
  virtual bool hasASkill() { return true; }
}

Ob nun templatisiert oder nicht spielt für den eigentlichen C++-Business-Code keine direkte Rolle, ob nun

if(unit->has<ASkill>()) ...
if(unit->hasASkill()) ...

Deswegen bin ich für gute Ideen weitestgehend offen.

wxSkip

wxSkip schrieb:

Und was spricht gegen einen Referenzzähler?