Container interface rationale?

Hello,
I'm curious as to what the rationale was behind making the NxOgre Container template not conform to the STL container protocol.

There are huge codebases (especially generic libraries) out there that rely on said protocol, not to mention a large amount of algorithms in the Standard C++ Library itself! Not conforming to the interface means that either
a) algorithms have to be duplicated
b) uses of the Container have to access the inner STL container if one is present; this may no longer be the case if Container is changed and the Container's internal state will potentially become inconsistent
c) all idiomatic uses of algorithms must be abandoned and instead the boiler-plate code written out by hand.

I argue that none of these three options are desirable. This is not a huge problem in itself as it seems the Container class is not used pervasively in NxOgre, but I suspect a lot of code built on top of NxOgre will end up using the new non-standard protocol, as there are no doubt many people learning C++ "on the go" while doing a fun game project with OGRE/NxOgre.

I believe the current interface is also very limiting because it does not support the idea of ranges. One of the key strengths of C++ compared to other languages is the ability to create elegant and efficient code through algorithmic generic abstraction, especially with respect to collections of objects and ranges of objects in said collections.

Let's turn this thread into something useful. I've decided to drop STL from NxOgre. I have my reasons, one of them is I want NxOgre to be truly multiplatform, and I can't rely on it existing on said platform. The other reason is I find the STL system although quite powerful - ugly to look at.

I've started development on the Containers; in a separate application first - so NxOgre isn't affected - yet.

In theory there will be three (or six depending on how you look at it); List, Map, and Multimap. Lists are plain lists with no identifier, Maps are a simple key to value list, and Multimaps are single keys to multiple values.

I've only done the List, so I'll explain that.

typedef SharedList<Actor> Actors;
Actors actors;


We have the standard STL functions, if you have to use them.
actors.push_back(new Actor());
actors.pop_back();
actors.push_front(new Actor());

Then we have the more readable functions.
actors.insert(new Actor());
actors.remove(4);
actors.remove(actor)

The List in question is "shared", which means the list can be passed around and copied and all of the data is the same. You adjust one list, everyone else is adjusted as well. Second it has garbage collection. Shared-Containers can only handle pointers (because of the garbage collection), but none shared can do either; Thats why there are six instead of three.

Next we have something in the Containers, which you don't see in the STL ones; Iterating through a list and doing something to them without a for loop.

actors.each(&Actor::wakeUp);
actors.each<Vector3>(&Actor::addForce, Vector3(3,0,0));
actors.each<Scene*, Scene*>(&Scene::exportTo, myScene, otherScene);


I'm not joking here, that actually works. There is a single internal while loop which does each actors, there's no overhead of calling and fetching variables, so in theory it's faster than a for-loop, and it's more damned readable than a iterator.

Well that's that for now. More coding to be done.

I'm slightly hesitant for what the OP will say, but I will say this - I prefer readable, business logic style code and STL doesn't provide that and I would be perfectly happy if I could iterate through a list without typing the word "iterator".

I agree with you regarding STL's uglyness, but once you've got used to it, I think you just don't care that much. At least, that was true with me - I refused to use the STL because I saw it as unnecessarily complex and uncomfortable to use, but then I saw a lot of code using it and the advantages of using tried and tested code that you know just works.

By the way, the STL has a similar feature for iterating without for loops and iterators: the for_each algorithm.

for_each(v.begin(), v.end(), doSomething);

Yes, it's a bit more complex, but at least you don't have to type "iterator"

Alright, I've done a bit of a test with the SharedList and the STL Container. The results are quite surprising.

I've tested each type of container; which creates, stores and destroys 10,000 objects, and performs this test eight times and records the times and creates an average.

Vector: 118.125 ms
Container: 101.5 ms


Not bad.

Oh did I point out, that Containers can work of the same source; one affects another, and it has inbuilt garbage collection?

While it is good to make things like for_each, it's better left up to the programmer to do the iteration. I might not want to iterator through the list at once, but split them up into seperate update threads so would still need the iterator.

I have my reasons, one of them is I want NxOgre to be truly multiplatform, and I can't rely on it existing on said platform.
I agree that on some platforms it is difficult if not impossible to use the STL, but does not OGRE itself use the STL pervasively? Also, for platforms where no STL is provided directly, there are other options, such as STLPort, which is an excellent cross-platform STL implementation.

Next we have something in the Containers, which you don't see in the STL ones; Iterating through a list and doing something to them without a for loop.

actors.each(&Actor::wakeUp);
actors.each<Vector3>(&Actor::addForce, Vector3(3,0,0));
actors.each<Scene*, Scene*>(&Scene::exportTo, myScene, otherScene);

Consider:
for_each(actors.begin(), actors.end(), mem_fun(&Actor::wakeUp));
Certainly this is more verbose, but it is also simple to create a function that forwards a container's full range to std::for_each:
template <typename Container, typename Fn>
void for_each(Container &cont, Fn fn) { std::for_each(cont.begin(), cont.end(), fn); }

// Call:
for_each(actors, mem_fun(&Actor::wakeUp));

For more complex expressions, there is also boost::bind which can be extracted from Boost like any other Boost library with the bcp utility (see http://www.boost.org/tools/bcp/bcp.html for more information.) Clearly, Boost uses the STL, but since OGRE does too, I don't see any problem unless it is indeed the case that you are going for pluggability of the rendering engine as well.
for_each(actors.begin(), actors.end(), bind(&Actor::addForce, _1, Vector3(3, 0, 0)); // No for loops, no iterators! Also:
for_each(actors, bind(&Actor::addForce, _1, Vector3(3, 0, 0)); // Even further, in C++09:
for(Actor *a : actors) a->addForce(Vector3(3, 0, 0)); // This relies on there being a range abstraction

I'm slightly hesitant for what the OP will say, but I will say this - I prefer readable, business logic style code and STL doesn't provide that and I would be perfectly happy if I could iterate through a list without typing the word "iterator".
As seen above, it is possible, and frequently done in code where the programmer is aware of the possibilities the STL provides.

I have recently had to work with Java and C# and while there are many annoyances in both languages, the one that most irritates me and hinders my work is the lack of proper algorithmic abstraction, and in that context, specifically the lack of ranges.
The range abstraction is an incredibly powerful abstraction as it allows for a set of algorithms completely decoupled from the containers of said ranges.

Consider that you have a list of objects and you wish to perform various operations on only a certain subset of them. You could create a function that checks each object to see if it is applicable and then performs the operations on the object, and then pass this function to .each. What if you wish to do something in the function that returns a result dependent on all objects, such as an accumulator? Say, you wish to calculate the number of red and green balls in a scene, where you have a single container for all the balls. This would require the ability to pass an arbitrary function object that can contain state to .each, which I suspect is not (currently?) possible. If you wish to support such a possibility, you would need to add an overload to every container's every template overload of .each that takes an arbitrary callable object (function pointer, functor, etc).

Now consider this problem with ranges and algorithms in the STL - a single call to std::partition with a predicate (color == red) will separate the red balls from the rest into a single continuous range, on which you can then perform any operations from the plethora of algorithms available - you can for example further sort the range by some other predicate (std::sort) and later perhaps merge multiple such sorted ranges into a single sorted range (std::merge).

The algorithms here are the same code called for different types of containers and ranges and do not require code duplication.

I just realized I am ranting - perhaps because I am expecting yet another day of working with Java and C# - but please consider, even if you wish to abandon the STL, not abandoning the power that ranges and algorithmic abstraction can give you.

While it is good to make things like for_each, it's better left up to the programmer to do the iteration. I might not want to iterator through the list at once, but split them up into seperate update threads so would still need the iterator.

Already in:

SharedList<A*> aList;
...
for (A* aItem = aList.begin(); aItem = aList.next();) {
aItem->doThings;
}

There's also a reverse version of that, and I'll probably cook up some code for ranges.

Clearly, Boost uses the STL, but since OGRE does too, I don't see any problem unless it is indeed the case that you are going for pluggability of the rendering engine as well.

That may actually happen. I'll answer the rest of your post in a bit. You've given me some more ideas about SharedList as well.

Here is the latest copy of "Betajaen's Container Classes". Have a look at it, perhaps submit some of your classes to it. Go on give it a test run. If your computer explodes I would be glad to know why.

BetajaenCC.h

Just a quick post. Guess who got STL style maps working?

Betajaen::SharedMap<std::string, A> a;

a.Insert("Five", new A("5"));
a.Insert("Four", new A("4"));
a.Insert("Two", new A("2"));
a.Insert("Eight", new A("8"));

A* four = a["Four"];

std::cout << four << std::endl;
four->wobble();


Like the STL map both use binary trees for it to work. It's very fast and completely different on how I thought they worked. Still lots to do though such as removing/destroying items in the map, and the iteration interface. Then some optimisation.

Alright, I've done a bit of a test with the SharedList and the STL Container. The results are quite surprising.

I've tested each type of container; which creates, stores and destroys 10,000 objects, and performs this test eight times and records the times and creates an average.

Vector: 118.125 ms
Container: 101.5 ms


Not bad.

Oh did I point out, that Containers can work of the same source; one affects another, and it has inbuilt garbage collection?
Sorry if that's old, but I'd like to know if those times consider random insertion/deletion or just add 10k objects and then delete them all. I'm not really fond of STL either and your results are indeed interesting, so I want to know how distant from a real life situation is your test.

It's now used in "Bleeding" (the ultra-hip new version of NxOgre, which is too cool for some people), and it's works fine. I didn't do any benchmarking before and after I replace the code, but it works the same speed if not a tiny bit faster, and it's used a LOT in NxOgre at least 60 times a second.