Most efficient way to process all items in an unknown container?

Question

I'm doing a computation in C++ and it has to be as fast as possible (it is executed 60 times per second with possibly large data). During the computation, a certain set of items have to be processed. However, in different cases, different implementations of the item storage are optimal, so i need to use an abstract class for that.

My question is, what is the most common and most efficient way to do an action with each of the items in C++? (I don't need to change the structure of the container during that.) I have thought of two possible solutions:

Make iterators for the storage classes. (They're also mine, so i can add it.) This is common in Java, but doesn't seem very 'C' to me:
```
class Iterator {
public:
    bool more() const;
    Item * next();
}
```
Add sort of an abstract handler, which would be overriden in the computation part and would include the code to be called on each item:
```
class Handler {
public:
    virtual void process(Item &item) = 0;
}
```
(Only a function pointer wouldn't be enough because it has to also bring some other data.)
Something completely different?

The second option seems a bit better to me since the items could in fact be processed in a single loop without interruption, but it makes the code quite messy as i would have to make quite a lot of derived classes. What would you suggest?

Thanks.

Edit: To be more exact, the storage data type isn't exactly just an ADT, it has means of only finding only a specific subset of the elements in it based on some parameters, which i need to then process, so i can't prepare all of them in an array or something.

Iterators aren't very C, but they are *very* C++. – David Brown Feb 06 '12 at 23:07 — David Brown, Feb 06 '12 at 23:07

score 3 · Accepted Answer · edited May 23 '17 at 11:48

3

#include <algorithm>

Have a look at the existing containers provided by the C++ standard, and functions such as for_each.

For a comparison of C++ container iteration to interfaces in "modern" languages, see this answer of mine. The other answers have good examples of what the idiomatic C++ way looks like in practice.

Using templated functors, as the standard containers and algorithms do, will definitely give you a speed advantage over virtual dispatch (although sometimes the compiler can devirtualize calls, don't count on it).

edited May 23 '17 at 11:48

Community

1
1

answered Feb 06 '12 at 23:02

Ben Voigt

277,958
43
419
720

Just to make sure, do i understand correctly that i should basically use the second approach, but use a template instead of the virtual method? – Detheroc Feb 06 '12 at 23:27
2

@Detheroc: If you implement an iterator using the same (duck-typed, not virtual via inheritance) interface as the standard containers, then you get all the existing standard algorithms, such as `for_each` and `transform` for free. That's what I would do if you really are making a container. From your question, you want a callback to be executed for a generated set of items, and in that case I'd go with #2 and accept a functor, via template if you care about performance. – Ben Voigt Feb 06 '12 at 23:35
Ok, thanks for the clarification, but there is a problem with the functor template. I cannot really pass it to the abstract container since virtual methods can't be templated. But i got some ideas on how to only call a virtual method once and not on all items, so thanks anyway. – Detheroc Feb 06 '12 at 23:59

score 3 · Answer 2 · answered Feb 06 '12 at 23:04

C++ has iterators already. It's not a particularly "Java" thing. (Note that their interface is different, though, and they're much more efficient than their Java equivalents)

As for the second approach, calling a virtual function for every element is going to hurt performance if you're worried about throughput.

If you can (pre-)sort your data so that all objects of the same type are stored consecutively, then you can select the function to call once, and then apply it to all elements of that type. Otherwise, you'll have to go through the indirection/type check of a virtual function or another mechanism to perform the appropriate action for every individual element.

score 1 · Answer 3 · answered Feb 06 '12 at 23:06

1

What gave you the impression that iterators are not very C++-like? The standard library is full of them (see this), and includes a wide range of algorithms that can be used to effectively perform tasks on a wide range of standard container types.

If you use the STL containers you can save re-inventing the wheel and get easy access to a wide variety of pre-defined algorithms. This is almost always better than writing your own equivalent container with an ad-hoc iteration solution.

answered Feb 06 '12 at 23:06

Mac

14,615
9
62
80

2

His particular iterator API is not idiomatic C++. `more` should be called `operator!=(end)` and `next` should be split into `operator*()` and `operator++()`. – Ben Voigt Feb 06 '12 at 23:08
1

@BenVoigt: not disagreeing. Iterators in C++ are definitely quite different to other languages (the OP's example is more Java-like), but do exist. The OP seemed (to me) to think that iterators (in general) are not very C++-like, but I concede he may have meant that the particular style he described is not c++-like. Regardless, the point is that the STL *does* include iterators for standard containers, and IMHO using such is always preferable to a home-brew solution (where feasible, of course). – Mac Feb 06 '12 at 23:10

score 0 · Answer 4 · answered Feb 06 '12 at 23:03

A function template perhaps:

template <typename C>
void process(C & c)
{
    typedef typename C::value_type type;
    for (type & x : c) { do_something_with(x); }
}

The iteration will use the containers iterators, which is generally as efficient as you can get.

You can specialize the template for specific containers.

Most efficient way to process all items in an unknown container?

4 Answers4