Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

Ignore:
Timestamp:
Mar 10, 2008, 12:27:30 AM (17 years ago)
Author:
landauf
Message:

std::set instead of std::list for Identifier-lists (parents, children, …) for faster accessing by key ( std::set::find(xyz) )

Location:
code/branches/core2/src/orxonox/core
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • code/branches/core2/src/orxonox/core/ClassTreeMask.cc

    r871 r876  
    327327        {
    328328            // No it's not: Search for classes inheriting from the given class and add the rules for them
    329             for (std::list<const Identifier*>::const_iterator it = subclass->getDirectChildrenBegin(); it != subclass->getDirectChildrenEnd(); ++it)
     329            for (std::set<const Identifier*>::const_iterator it = subclass->getDirectChildrenBegin(); it != subclass->getDirectChildrenEnd(); ++it)
    330330                if ((*it)->isA(this->root_->getClass()))
    331331                    if (overwrite || (!this->nodeExists(*it))) // If we don't want to overwrite, only add nodes that don't already exist
     
    422422    void ClassTreeMask::addSingle(const Identifier* subclass, bool bInclude, bool clean)
    423423    {
    424         for (std::list<const Identifier*>::const_iterator it = subclass->getDirectChildrenBegin(); it != subclass->getDirectChildrenEnd(); ++it)
     424        for (std::set<const Identifier*>::const_iterator it = subclass->getDirectChildrenBegin(); it != subclass->getDirectChildrenEnd(); ++it)
    425425            this->add(*it, this->isIncluded(*it), false, false);
    426426
  • code/branches/core2/src/orxonox/core/Identifier.cc

    r871 r876  
    5151        this->factory_ = 0;
    5252
    53         this->children_ = new std::list<const Identifier*>();
    54         this->directChildren_ = new std::list<const Identifier*>();
     53        this->children_ = new std::set<const Identifier*>();
     54        this->directChildren_ = new std::set<const Identifier*>();
    5555
    5656        // Use a static variable because the classID gets created before main() and that's why we should avoid static member variables
     
    7272        @param parents A list containing all parents
    7373    */
    74     void Identifier::initialize(std::list<const Identifier*>* parents)
     74    void Identifier::initialize(std::set<const Identifier*>* parents)
    7575    {
    7676        COUT(4) << "*** Identifier: Initialize " << this->name_ << "-Singleton." << std::endl;
     
    8383
    8484            // Iterate through all parents
    85             for (std::list<const Identifier*>::iterator it = parents->begin(); it != parents->end(); ++it)
     85            for (std::set<const Identifier*>::iterator it = parents->begin(); it != parents->end(); ++it)
    8686            {
    8787                // Tell the parent we're one of it's children
     
    8989
    9090                // Erase all parents of our parent from our direct-parent-list
    91                 for (std::list<const Identifier*>::const_iterator it1 = (*it)->getParents().begin(); it1 != (*it)->getParents().end(); ++it1)
     91                for (std::set<const Identifier*>::const_iterator it1 = (*it)->getParents().begin(); it1 != (*it)->getParents().end(); ++it1)
    9292                {
    9393                    // Search for the parent's parent in our direct-parent-list
    94                     for (std::list<const Identifier*>::iterator it2 = this->directParents_.begin(); it2 != this->directParents_.end(); ++it2)
     94                    for (std::set<const Identifier*>::iterator it2 = this->directParents_.begin(); it2 != this->directParents_.end(); ++it2)
    9595                    {
    9696                        if ((*it1) == (*it2))
     
    105105
    106106            // Now iterate through all direct parents
    107             for (std::list<const Identifier*>::iterator it = this->directParents_.begin(); it != this->directParents_.end(); ++it)
     107            for (std::set<const Identifier*>::iterator it = this->directParents_.begin(); it != this->directParents_.end(); ++it)
    108108            {
    109109                // Tell the parent we're one of it's direct children
     
    149149    bool Identifier::isA(const Identifier* identifier) const
    150150    {
    151         return (identifier == this || this->identifierIsInList(identifier, this->parents_));
     151        return (identifier == this || (this->parents_.find(identifier) != this->children_->end()));
    152152    }
    153153
     
    167167    bool Identifier::isChildOf(const Identifier* identifier) const
    168168    {
    169         return this->identifierIsInList(identifier, this->parents_);
     169        return (this->parents_.find(identifier) != this->children_->end());
    170170    }
    171171
     
    176176    bool Identifier::isDirectChildOf(const Identifier* identifier) const
    177177    {
    178         return this->identifierIsInList(identifier, this->directParents_);
     178        return (this->directParents_.find(identifier) != this->children_->end());
    179179    }
    180180
     
    185185    bool Identifier::isParentOf(const Identifier* identifier) const
    186186    {
    187         return this->identifierIsInList(identifier, *this->children_);
     187        return (this->children_->find(identifier) != this->children_->end());
    188188    }
    189189
     
    194194    bool Identifier::isDirectParentOf(const Identifier* identifier) const
    195195    {
    196         return this->identifierIsInList(identifier, *this->directChildren_);
     196        return (this->directChildren_->find(identifier) != this->children_->end());
    197197    }
    198198
     
    221221    }
    222222
    223     /**
    224         @brief Searches for a given identifier in a list and returns whether the identifier is in the list or not.
    225         @param identifier The identifier to look for
    226         @param list The list
    227         @return True = the identifier is in the list
    228     */
    229     bool Identifier::identifierIsInList(const Identifier* identifier, const std::list<const Identifier*>& list)
    230     {
    231         for (std::list<const Identifier*>::const_iterator it = list.begin(); it != list.end(); ++it)
    232             if (identifier == (*it))
    233                 return true;
    234 
    235         return false;
    236     }
    237 
    238     std::ostream& operator<<(std::ostream& out, const std::list<const Identifier*>& list)
    239     {
    240         for (std::list<const Identifier*>::const_iterator it = list.begin(); it != list.end(); ++it)
     223    std::ostream& operator<<(std::ostream& out, const std::set<const Identifier*>& list)
     224    {
     225        for (std::set<const Identifier*>::const_iterator it = list.begin(); it != list.end(); ++it)
    241226            out << (*it)->getName() << " ";
    242227
  • code/branches/core2/src/orxonox/core/Identifier.h

    r871 r876  
    5252#define _Identifier_H__
    5353
    54 #include <list>
     54#include <set>
    5555#include <map>
    5656#include <string>
     
    115115
    116116            /** @brief Returns the parents of the class the Identifier belongs to. @return The list of all parents */
    117             inline const std::list<const Identifier*>& getParents() const { return this->parents_; }
     117            inline const std::set<const Identifier*>& getParents() const { return this->parents_; }
    118118            /** @brief Returns the begin-iterator of the parents-list. @return The begin-iterator */
    119             inline std::list<const Identifier*>::const_iterator getParentsBegin() const { return this->parents_.begin(); }
     119            inline std::set<const Identifier*>::const_iterator getParentsBegin() const { return this->parents_.begin(); }
    120120            /** @brief Returns the end-iterator of the parents-list. @return The end-iterator */
    121             inline std::list<const Identifier*>::const_iterator getParentsEnd() const { return this->parents_.end(); }
     121            inline std::set<const Identifier*>::const_iterator getParentsEnd() const { return this->parents_.end(); }
    122122
    123123            /** @brief Returns the children of the class the Identifier belongs to. @return The list of all children */
    124             inline const std::list<const Identifier*>& getChildren() const { return (*this->children_); }
     124            inline const std::set<const Identifier*>& getChildren() const { return (*this->children_); }
    125125            /** @brief Returns the begin-iterator of the children-list. @return The begin-iterator */
    126             inline std::list<const Identifier*>::const_iterator getChildrenBegin() const { return this->children_->begin(); }
     126            inline std::set<const Identifier*>::const_iterator getChildrenBegin() const { return this->children_->begin(); }
    127127            /** @brief Returns the end-iterator of the children-list. @return The end-iterator */
    128             inline std::list<const Identifier*>::const_iterator getChildrenEnd() const { return this->children_->end(); }
     128            inline std::set<const Identifier*>::const_iterator getChildrenEnd() const { return this->children_->end(); }
    129129
    130130            /** @brief Returns the direct parents of the class the Identifier belongs to. @return The list of all direct parents */
    131             inline const std::list<const Identifier*>& getDirectParents() const { return this->directParents_; }
     131            inline const std::set<const Identifier*>& getDirectParents() const { return this->directParents_; }
    132132            /** @brief Returns the begin-iterator of the direct-parents-list. @return The begin-iterator */
    133             inline std::list<const Identifier*>::const_iterator getDirectParentsBegin() const { return this->directParents_.begin(); }
     133            inline std::set<const Identifier*>::const_iterator getDirectParentsBegin() const { return this->directParents_.begin(); }
    134134            /** @brief Returns the end-iterator of the direct-parents-list. @return The end-iterator */
    135             inline std::list<const Identifier*>::const_iterator getDirectParentsEnd() const { return this->directParents_.end(); }
     135            inline std::set<const Identifier*>::const_iterator getDirectParentsEnd() const { return this->directParents_.end(); }
    136136
    137137            /** @brief Returns the direct children the class the Identifier belongs to. @return The list of all direct children */
    138             inline const std::list<const Identifier*>& getDirectChildren() const { return (*this->directChildren_); }
     138            inline const std::set<const Identifier*>& getDirectChildren() const { return (*this->directChildren_); }
    139139            /** @brief Returns the begin-iterator of the direct-children-list. @return The begin-iterator */
    140             inline std::list<const Identifier*>::const_iterator getDirectChildrenBegin() const { return this->directChildren_->begin(); }
     140            inline std::set<const Identifier*>::const_iterator getDirectChildrenBegin() const { return this->directChildren_->begin(); }
    141141            /** @brief Returns the end-iterator of the direct-children-list. @return The end-iterator */
    142             inline std::list<const Identifier*>::const_iterator getDirectChildrenEnd() const { return this->directChildren_->end(); }
     142            inline std::set<const Identifier*>::const_iterator getDirectChildrenEnd() const { return this->directChildren_->end(); }
    143143
    144144            /** @brief Returns true, if a branch of the class-hierarchy is being created, causing all new objects to store their parents. @return The status of the class-hierarchy creation */
     
    159159            virtual XMLPortObjectContainer* getXMLPortObjectContainer(const std::string& sectionname) = 0;
    160160            virtual void addXMLPortObjectContainer(const std::string& sectionname, XMLPortObjectContainer* container) = 0;
    161 
    162             static bool identifierIsInList(const Identifier* identifier, const std::list<const Identifier*>& list);
    163161
    164162        private:
     
    166164            Identifier(const Identifier& identifier) {} // don't copy
    167165            virtual ~Identifier();
    168             void initialize(std::list<const Identifier*>* parents);
     166            void initialize(std::set<const Identifier*>* parents);
    169167
    170168            /** @brief Returns the children of the class the Identifier belongs to. @return The list of all children */
    171             inline std::list<const Identifier*>& getChildrenIntern() const { return (*this->children_); }
     169            inline std::set<const Identifier*>& getChildrenIntern() const { return (*this->children_); }
    172170            /** @brief Returns the direct children of the class the Identifier belongs to. @return The list of all direct children */
    173             inline std::list<const Identifier*>& getDirectChildrenIntern() const { return (*this->directChildren_); }
     171            inline std::set<const Identifier*>& getDirectChildrenIntern() const { return (*this->directChildren_); }
    174172
    175173            /**
     
    191189            }
    192190
    193             std::list<const Identifier*> parents_;                      //!< The parents of the class the Identifier belongs to
    194             std::list<const Identifier*>* children_;                    //!< The children of the class the Identifier belongs to
    195 
    196             std::list<const Identifier*> directParents_;                //!< The direct parents of the class the Identifier belongs to
    197             std::list<const Identifier*>* directChildren_;              //!< The direct children of the class the Identifier belongs to
     191            std::set<const Identifier*> parents_;                      //!< The parents of the class the Identifier belongs to
     192            std::set<const Identifier*>* children_;                    //!< The children of the class the Identifier belongs to
     193
     194            std::set<const Identifier*> directParents_;                //!< The direct parents of the class the Identifier belongs to
     195            std::set<const Identifier*>* directChildren_;              //!< The direct children of the class the Identifier belongs to
    198196
    199197            std::string name_;                                          //!< The name of the class the Identifier belongs to
     
    206204    };
    207205
    208     std::ostream& operator<<(std::ostream& out, const std::list<const Identifier*>& list);
     206    std::ostream& operator<<(std::ostream& out, const std::set<const Identifier*>& list);
    209207
    210208
     
    231229
    232230        public:
    233             ClassIdentifier<T>* registerClass(std::list<const Identifier*>* parents, const std::string& name, bool bRootClass);
     231            ClassIdentifier<T>* registerClass(std::set<const Identifier*>* parents, const std::string& name, bool bRootClass);
    234232            void addObject(T* object);
    235233            void removeObjects() const;
     
    273271    */
    274272    template <class T>
    275     ClassIdentifier<T>* ClassIdentifier<T>::registerClass(std::list<const Identifier*>* parents, const std::string& name, bool bRootClass)
     273    ClassIdentifier<T>* ClassIdentifier<T>::registerClass(std::set<const Identifier*>* parents, const std::string& name, bool bRootClass)
    276274    {
    277275        COUT(5) << "*** ClassIdentifier: Register Class in " << name << "-Singleton." << std::endl;
  • code/branches/core2/src/orxonox/core/OrxonoxClass.h

    r871 r876  
    3737#define _OrxonoxClass_H__
    3838
    39 #include <list>
     39#include <set>
    4040#include <string>
    4141
     
    6767
    6868            /** @brief Returns the list of all parents of the object. @return The list */
    69             inline std::list<const Identifier*>* getParents() const { return this->parents_; }
     69            inline std::set<const Identifier*>* getParents() const { return this->parents_; }
    7070
    7171            /** @brief Creates the parents-list. */
    72             inline void createParents() { this->parents_ = new std::list<const Identifier*>(); }
     72            inline void createParents() { this->parents_ = new std::set<const Identifier*>(); }
    7373
    7474            /** @brief Returns the MetaObjectList of the object, containing a link to all ObjectLists and ObjectListElements the object is registered in. @return The list */
     
    157157        private:
    158158            Identifier* identifier_;                    //!< The Identifier of the object
    159             std::list<const Identifier*>* parents_;     //!< List of all parents of the object
     159            std::set<const Identifier*>* parents_;     //!< List of all parents of the object
    160160            MetaObjectList metaList_;                   //!< MetaObjectList, containing all ObjectLists and ObjectListElements the object is registered in
    161161    };
Note: See TracChangeset for help on using the changeset viewer.