Home

sequence class template

How do we specify a container of a particular type in a generic manner? The sequence class template is the answer. C++ has a default__ container, called vector. This is typically your go-to container type in C++. It will provide the best performance, both in memory and speed, in most cases. However, there are many cases where it isn't the best choice, such as when you expect to many insertions in the middle of the container. In cases such as this, some sort of linked-list would be more efficient.

Interfacing Issue

What happens when we are not sure what is the best container to use when designing an interface? We have typically took one of two choices. We have either defaulted to vector or make the container type a policy, indicated as a template parameter. The STL has the policy approach for queue, priority_queue, and stack. This is usually a safe choice. However, there are situations where hiding an implementation is absolutely necessary (i.e. hiding proprietary business logic), so the policy approach is unavailable. In this case, we would need to choose a specific container type.

struct Foo {
    int bar = 0;
    constexpr int baz() const { return bar; }
};

struct FooProvider {
    virtual std::vector<Foo> getAllFoo() const = 0;
    virtual std::vector<Foo> getAllFooWithHighBar() const = 0;
    virtual std::vector<Foo> getAllFooWithLowBar() const = 0;
    virtual void addFoo(const Foo &foo) = 0;
};

class FooVectorProvider : public FooProvider {
    std::vector<Foo> foos; // Assume that this gets populated somehow
    int bar = 90;

public:
    FooVectorProvider(int bar_=90) :
        foos{},
        bar(bar_)
    {
    }

    virtual std::vector getAllFoo() const override {
        return foos;
    }
    virtual std::vector getAllFooWithHighBar() const override {
        // We could at least benefit NVRO
        std::vector<Foo> highFoos;
        highFoos.reserve(foos.size());
        std::copy_if(std::begin(foos), std::end(foos), std::back_inserter(highFoos),
                     [=] (const Foo &foo) { return foo.bar > bar; });
        return highFoos;
    }
    virtual std::vector getAllFooWithLowBar() const override {
        // We could at least benefit NVRO
        std::vector<Foo> lowFoos;
        lowFoos.reserve(foos.size());
        std::copy_if(std::begin(foos), std::end(foos), std::back_inserter(lowFoos),
                     [=] (const Foo &foo) { return foo.bar <= bar; });
        return lowFoos;
    }
    virtual void addFoo(const Foo &foo) override {
        foos.push_back(foo);
    }
};

The issue with this interface is that we are forced to create a std::vector<Foo> in each of the FooProvider methods. This seems like it would be a natural, simple interface to use, but this interface may be impossible to implement. Consider FooVectorProvider being used in an embedded device that has very little memory and uses a remote database for storage. We might need to store an amount of records in the result that is too much for the memory capacity of the device. Also, we need to consider an implementation that would require a different allocator than the std::allocator. It would be an impossibility to implement in this case because the interface has already determined the allocator to be used.

Creating a sequence

Let's examine the interface a bit more and consider the intent of the API designer. The return types are all std::vector<Foo>. But does the API designer really care that we're using the std::vector class template as the container type or that the container is using the std::allocator class template? Probably not. The API designer simply cares about obtaining the some sequence of Foo objects. The API designer doesn't care if the data is coming from a std::vector or another container optimized for querying (e.g. std::multiset) or if the data source is a remote database. As long the provider can give us a sequence of Foo objects, regardless of how it got them, then everything is cool.

struct FooProvider {
    virtual sequence<Foo> getAllFoo() const = 0;
    virtual sequence<Foo> getAllFooWithHighBar() const = 0;
    virtual sequence<Foo> getAllFooWithLowBar() const = 0;
    virtual void add(const Foo &foo) const = 0;
};

class FooSetProvider : public FooProvider {
    struct FooCompare {
        inline bool operator()(const Foo &l, const Foo &r) const {
            return l.bar < r.bar;
        }
    };
    struct FooAllocator {
        // typical allocator stuff
    };
    std::multiset<Foo, FooCompare, FooAllocator> foos;

public:
    FooSetProvider(int bar_=90) :
        foos(),
        bar(bar_)
    {
    }

    virtual sequence<Foo> getAllFoo() const {
        return from(foos, foos.get_allocator());
    }
    virtual sequence<Foo> getAllFooWithHighBar() const {
        return from(foos.lower_bound(Foo{bar}), std::end(foos), foos.get_allocator());
    }
    virtual sequence<Foo> getAllFooWithLowBar() const {
        return from(std::begin(foos), foos.upper_bound(Foo{bar}), foos.get_allocator());
    }
    virtual void addFoo(const Foo &foo) const override {
        foos.insert(foo);
    }
};

In the example above, we created a sequence<Foo> from a pair of iterators and from a basic container (i.e. anything that can be iterated over). We were able to switch up the implementation to using a std::multiset. Also, we were able to use an implementation defined allocator.

sequence manipulation

Using a std::multiset helped simplify our ordering issue. Another benefit of it is that we were able to take advantage of the API provided in std::mutliset so we're not having to develop a lot of custom code. Instead we used what has already been provided to us. However, a beginner not knowing what upper_bound and lower_bound do may be confused by the implementations (in fact, I actually double-checked that my assumptions were correct).

Knowing that std::multiset orders its data, we can simplify the code to make it easier to read. Also, we can get a bit more code reuse by calling getAllFoo.

auto fooIsLowBar = [=](const Foo &foo) { foo.bar <= bar; };
virtual sequence<Foo> getAllFooWithHighBar() const {
    return getAllFoo() | skip_while(fooIsLowBar);
}
virtual sequence<Foo> getAllFooWithLowBar() const {
    return getAllFoo() | take_while(fooIsLowBar);
}