Hello,

I'm still learning C++, and I have a question that I'm not even sure how to search for it, so sorry if this is a repeat.

The thing is that I'm trying to make, for a project a-for lack of a better word-memory manager. I want to have kind of a "database" or something of all "actors", but I want to be able to ask for things like:
"I want all actors that are of type SOMETYPE and intersect SOMECONVEX and that have SOMEFLAG set". And of course, it would be great if the actors would be dynamic_cast down to SOMETYPE, since I use a lot of inheritance.

Of course, sometimes I'll want ALL actors, and sometimes I'll want all actors of SOMETYPE that have SOMEFLAG, but not care about what they intersect and so on.

What would be a clean (probably using templates?) way to design such a system? Or if it's already designed, like a "database" or something like that, where would I find something simple?

I can see a very ugly way to design this, which is to save a bunch of different list<Actor> and list<SomeDeriveClass> and so on, and have a ton of different functions.

Is there a clean way?

Anyway, thanks for any advice.

Is this operation being performed on Actors only? Do you have a list of Actors available to apply the filtering?

Yes, of course, I have a list of Actor's, but some of them are actually derived classes (actually, all of them, since Actor is an abstract class). They have different flags and types, and I want a clean interface. For example, I want to be able to do:
ActorManager::GiveMeAllActorsOfTypeMobileWithFlagDead() and it should return a list<Mobile
>, which is a derived class of Actor*.

What about a filtered iterator?

Here is what I mean:

template <typename BaseIterator, typename OutputType>
struct ActorIteratorImpl {
  public:
    // the set of required typedefs:
    typedef ActorIteratorImpl<BaseIterator,OutputType> self;
    typedef OutputType* value_type;
    typedef OutputType* const & reference;
    typedef typename std::iterator_traits<BaseIterator>::difference_type difference_type;
    typedef OutputType* const * pointer;
    typedef input_iterator_tag iterator_category;

  private:
    ActorFlag required_flag; 

    BaseIterator cur_it;
    BaseIterator end_it;

    // this function seeks the next valid base-iterator
    void seekValidIterator() {
      while(cur_it != end_it) {
        OutputType* tmp_ptr = dynamic_cast<OutputType*>( *cur_it );
        if((tmp_ptr) && (tmp_ptr->hasFlag( required_flag )))
          break;
        ++cur_it;
      };
    };

  public:

    // constructor (not to be called directly by user).
    ActorIteratorImpl(ActorFlag aRequiredFlag, BaseIterator aCurrentIter, BaseIterator aEndIter) :
                      required_flag(aRequiredFlag), cur_it(aCurrentIter), end_it(aEndIter) {
      seekValidIterator();
    };
    ActorIteratorImpl() : required_flag(), cur_it(), end_it() { };

    // define an equal operator for the base-iterator:
    friend bool operator==(const self& lhs, BaseIterator rhs) { return (lhs.cur_it == rhs); };
    friend bool operator==(BaseIterator lhs, const self& rhs) { return (lhs == lhs.cur_it); };
    friend bool operator!=(const self& lhs, BaseIterator rhs) { return (lhs.cur_it != rhs); };
    friend bool operator!=(BaseIterator lhs, const self& rhs) { return (lhs != lhs.cur_it); };

    // then, the standard iterator operations:
    self& operator++() {
      ++cur_it;
      seekValidIterator();
      return *this;
    };
    self operator++(int) {
      self result(*this);
      ++(*this);
      return result;
    };

    friend bool operator==(const self& lhs, const self& rhs) { return (lhs.cur_it == rhs.cur_it); };
    friend bool operator!=(const self& lhs, const self& rhs) { return (lhs.cur_it != rhs.cur_it); };

    value_type operator*() const {
      return dynamic_cast<value_type>(*cur_it);
    };
    value_type operator->() const {
      return dynamic_cast<value_type>(*cur_it);
    };

};

Note that you could fairly easily make this a bidirectional iterator too (random-access might be a bit more challenging).

With the above iterator, you can have a pointer manager class that would be something like this:

template <typename DerivedClass>
struct ActorIterator { 
  typedef ActorIteratorImpl< std::vector< Actor* >::const_iterator, DerivedClass> type;
};


class ActorManager {
  private:
    std::vector< Actor* > actors;

  public:
    typedef std::vector< Actor* >::const_iterator iterator;

    // ... some code ...

    template <typename DerivedClass>
    friend
    typename ActorIterator<DerivedClass>::type 
      begin(const ActorManager& aMng, ActorFlag aRequiredFlag) {
      return ActorIteratorImpl<iterator, DerivedClass>(aRequiredFlag, 
                                                       aMng.actors.begin(), aMng.actors.end());
    };

    friend
    iterator end(const ActorManager& aMng) {
      return aMng.actors.end();
    };
};

Then, you can use it is as so:

ActorManager my_mng;

for(ActorIterator<Mobile>::type it = begin<Mobile>(my_mng, FLAG_DEAD); it != end(my_mng); ++it)
  (*it)->doSomethingSpecificToMobile();

Or, if you have C++11 compiler:

for(auto it = begin<Mobile>(my_mng, FLAG_DEAD); it != end(my_mng); ++it)
  (*it)->doSomethingSpecificToMobile();

That is pretty much as easy as it gets for the user of the manager class. Of course, this is limited to traversing the elements of it. You can't modify the pointers (but only the pointees), which is intentional, as it is not something you want to allow the user to do. This solution is pretty classic, and is really nice as it avoids reconstruction of a new list (as you suggested returning a new std::Vector< Mobile* >, which would be wasteful).

P.S.: You should consider using smart-pointers instead of raw pointers. Raw pointers are usually the main loop-hole and usability terror of most interfaces. They are not recommended anywhere near the interface of any class or library.

Wow, that looks interesting. Of course, iterators, I never thought of that. That makes a lot of sense.

It will take me a while to fully understand all your code, but I think I get the idea.

Thank you!

If you are going to go the iterator route, then you might as well make it stl compatiable and inherit from `std::iterator'.

Another option is to simply have a filter function like so:

template<typename Container, typename FilterCondition>
std::vector<typename Container::value_type> filter(const Container& cont, const FilterCondition& cond){
 std::vector<typename Container::value_type> filteredList;
 for(int i = 0; i < cont.size(); ++i){
    if(cond( cont[i] )) filteredList.push_back( cont[i] );
 }
 return filteredList;
}

bool isDead(const Actor& actor){ return actor.isDead(); }
bool isChildActor(const Actor& actor){ return actor.age() < 18;}
bool isGirlActor(const Actor& actor){ return actor.type == Actor::GIRL_ACTOR: }
int main(){
  ActorList actors = getActors();
  ActorList childActors = filter( actors , isChildActor );
  ActorList childActorWhoAreGirls = filter( childActors, isGirlActor );
  //..and so on

Warning, syntax is probably wrong somewhere, but the general advice should help.

Thanks for the suggestion. Using function pointers... sure, that kind of makes sense, except it would probably be slower since it has to go over the list for each condition, and make a copy each time. I'll try the iterator thing and if I'm not happy with that, I'll end up with this filter idea.

Thanks again!

No need for copies or iterating over multiple condition. There can be perfect forwarding,references or pointers, if needed. And you can combine multiple functors into one if you only want to run through the list once. I just think this would be the better option of the two and a lot less code

Edited 3 Years Ago by firstPerson

There is also an implementation of the filtered_iterator as part of the Boost.Iterator library. This one is generic to any predicate (a function object that determines whether an element is valid) and skips any element that doesn't satisfy the predicate. This might be an easier off-the-shelf thing to use if you don't want to implement this yourself.

This article has been dead for over six months. Start a new discussion instead.