Sign in to follow this  
imi

Fast STL-container concatination iterator?

Recommended Posts

Hi, has anyone an iterator template lying around his toolbox which iterates over two STL containers? Couldn't find one in boost, but I haven't understood everything of boost::range yet.. Basically, I want to use one for-loop to iterate over two identical-typed containers in one go. (Wouldn't harm if it supports more than two non-identical containers ;) ) I came up with a version of myself (only supporting plain iteration without const, reverse iteration and everything). Warning: It is HORRIBLE fragile in usage. Sneeze and you get a segfault. But it should have only one boolean compare per operator++ overhead. If I understand it correctly, this is the smallest overhead possible without changing the container before and after the iteration. (Anyone has a concatination iterator template that *does* change the container and so achieve better performance for containers where it's possible to do so?) Anyway, here is my version:
template<class Container>
struct combine
{
    typedef typename Container::iterator CIt;
    struct It : CIt
    {
        CIt end1_, begin2_;
        bool withinC2_;
        It(const CIt& it, const CIt& end1, const CIt& begin2, bool withinC2)
            : CIt(it), end1_(end1), begin2_(begin2), withinC2_(withinC2) {}
        It& operator++()
        {
            CIt::operator++();
            if (!withinC2_ && static_cast<const CIt&>(*this) == end1_)
            {
                CIt::operator=(begin2_);
                withinC2_=true;
            }
            return *this;
        }
        bool operator==(const It& rhs) const { return withinC2_ == rhs.withinC2_ && static_cast<const CIt&>(*this) == rhs; }
        bool operator!=(const It& rhs) const { return withinC2_ != rhs.withinC2_ || static_cast<const CIt&>(*this) != rhs; }
    private:
        It operator++(int); // undefined
    };
    typedef It iterator;

    Container &c1_, &c2_;
    combine(Container& c1, Container& c2) : c1_(c1), c2_(c2) {}
    It begin()
    {
        if (c1_.empty())
            return It(c2_.begin(), c1_.end(), c2_.begin(), true);
        return It(c1_.begin(), c1_.end(), c2_.begin(), false);
    }
    It end() { return It(c2_.end(), c1_.end(), c2_.begin(), true); }
};

// some performance measurement
int main()
{
    list<int> l(10000000), l2(10000000);
    long before, after;
    
    before = clock();
    for(auto it = l.begin(), e = l.end(); it != e; ++it)
        *it = rand();
    for(auto it = l2.begin(), e = l2.end(); it != e; ++it)
        *it = rand();
    after = clock();
    cout << after-before << endl;

    before = clock();
    combine<list<int>> c(l,l2);
    for(auto it = c.begin(), e = c.end(); it != e; ++it)
        *it = rand();
    after = clock();
    cout << after - before << endl;
}

Ciao, Imi.

Share this post


Link to post
Share on other sites
Quote:

If I understand it correctly, this is the smallest overhead possible without changing the container before and after the iteration.


With a std::list in particular you could use splice to concatenate and take the lists apart. With other containers it's not possible efficiently, without copying everything.

I'm not very sure if it is such a good idea to inherit from the iterator, rather than having them as members. For example, as it is I could make it iterate vectors, and use it += 1, which compiles but obviously won't work.

You could check out boost's iterator library to make implementing iterators less tedious.

Share this post


Link to post
Share on other sites
Quote:
I want to use one for-loop to iterate over two identical-typed containers in one go

template < class P, class Q, class Visitor >
void iterate(P p, Q q, Visitor v) {
std::for_each(p.begin(), p.end(), v);
std::for_each(q.begin(), q.end(), v);
}

Share this post


Link to post
Share on other sites
Quote:
Original post by Antheus
Quote:
I want to use one for-loop to iterate over two identical-typed containers in one go

template < class P, class Q, class Visitor >
void iterate(P p, Q q, Visitor v) {
std::for_each(p.begin(), p.end(), v);
std::for_each(q.begin(), q.end(), v);
}


This doesn't allow your visitor to access both items at the same time.

That being said, std::transform() has exactly what you're looking for, an overload that takes 2 input iterators and calls a functor with both items at the same time. If you don't actually want to transform anything but just treat it more as a for_each, then just make a simple output iterator class that is a nop.

Share this post


Link to post
Share on other sites
Quote:
Original post by Antheus
template < class P, class Q, class Visitor >
void iterate(P p, Q q, Visitor v) {
std::for_each(p.begin(), p.end(), v);
std::for_each(q.begin(), q.end(), v);
}


That'll be handy once lambda-functions don't generate an function call on my compiler anymore. Until then, it's just too slow.

Ciao, Imi.

Share this post


Link to post
Share on other sites
Quote:
Original post by imi

That'll be handy once lambda-functions don't generate an function call on my compiler anymore. Until then, it's just too slow.


Often these days, calling a function is faster than making method inline due to better icache. And iterating over a std::list incurs a 100-cycle penalty anyway, so the 3 cycles needed for function call are free.

The iterator in original example also has an extra branch to test.

And the original example also doesn't reflect real world usage, since it allocates nodes without interference, in any other example, the fragmentation from that would increase running time by a factor of 10 vs. vector, in which case the function call cost no longer matters.

The test example might also suffer from constant folding.

And under MVC, not disabling both iterator tests adds another 5-20x to running time.

So yea, it's not really a simple problem.

IMHO:
Quote:
It is HORRIBLE fragile in usage. Sneeze and you get a segfault.

Get it right.
Then, if during testing in real application it shows up in profile, then make it fast where needed.

Share this post


Link to post
Share on other sites
Quote:
That'll be handy once lambda-functions don't generate an function call on my compiler anymore. Until then, it's just too slow.


It doesn't take a lambda function - it takes any type that can be called using (). If you pass it a struct with an inline operator() the compiler can inline the call, and will if its heuristics indicate that doing so would be an optimization.

Share this post


Link to post
Share on other sites
Quote:
Original post by Antheus
Quote:
Original post by cache_hit

This doesn't allow your visitor to access both items at the same time.

Which is not required.
Huh? Maybe not in his example, but how do you know what the original poster really intends to use this for?

Perhaps it is used in an algorithm where it is vital that both items be processed together. E.g. they may be lists of full paths to files whose contents need to be compared, with the filenames that didn't appear on both sides already filtered out.

Share this post


Link to post
Share on other sites
Quote:
Original post by Antheus
And the original example also doesn't reflect real world usage, since it allocates nodes without interference, in any other example, the fragmentation from that would increase running time by a factor of 10 vs. vector, in which case the function call cost no longer matters.


Yes, I am sorry. I wasn't comparing to my class example above but to the normal "just write two for-loops".

I can't use vector in my normal code. The objects are linked using good old "prev/next" pointers, but I still found the function call of lambda relevant in performance. Well, said that, maybe I should measure again - I spent only a couple of minutes to profiling and was very quick in blaming function calls..


Actually I even don't use my own example, because it's just too bad written. It was some kind of 10 minutes one-shot and then I lost attention.

Since there is a lot of quality library code around that works with the STL iterator stuff, I was hoping for some quick tip ala "use library foobar" or "you can do this with boost::barfoo when typedef'ing blab to balb" or so.


Ciao, Imi.

Share this post


Link to post
Share on other sites
Quote:
Original post by Nitage
Quote:
That'll be handy once lambda-functions don't generate an function call on my compiler anymore. Until then, it's just too slow.


It doesn't take a lambda function - it takes any type that can be called using (). If you pass it a struct with an inline operator() the compiler can inline the call, and will if its heuristics indicate that doing so would be an optimization.


I know, but I hate to write these one-liner struct-functors all over the place.

And either the body of the loop is small and trivial so it deserves inlining - then I also can just write those damn two for loops - it's not a big deal. Or it is so complicated and large that inlining is not appropiate. Then I can swallow the pride and accept one stupid function call overhead and use lambdas.

Ciao, Imi.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this