Quack - the revolutionary new data structure

I was having a chat with a friend about data structures (as you do), and that, and his love of portmanteaus meant that he came up with a Quack - A queue and a stack, stuck together in the dumbest way, as it just gives you a tuple of the front and back items. I thought that it might be at least possibly useful if it was ordered, and therefore would pair up the largest and smallest items in the structure.

If anyone can tell me a use for it, or even if it's already a thing in any incarnation (other than std::list, to some degree, I guess), I'd be pleased, as the only thing that we could come up with was matching good players on the same team as bad ones for a training .

As well as this, I spent longer than I'd like to say implementing a binary search, with the expectation of it being really quick, but it's quite a bit slower than a linear search, and I was wondering why. My guess was that the cpu can do better branch prediction on linear when it's on sorted data, but that's just a hunch.

Linear search - ~320ms to insert 10,000 random items
Binary search - ~860ms to insert 10,000 random items

Random is a simple call to rand() from cstdlib
Time is gotten from std::chrono::high_resolution_clock


Anyway, that's already too much waffle. As well as what I've already mentioned, general practice pointers would be appreciated. Bear in mind this is using C++0x. The print() function is just there so that I could get the algorithms right, and I just left it in for completeness sake. I'm planning on deleting it.

`#ifndef QUACK_H_
#define QUACK_H_

#include
#include
#include

#include

#include

template
class Quack
{
private:
std::list data;
typedef typename std::list::iterator iter;

public:
Quack();

void insert(T dat);
std::tuple poppop();
void print();
inline bool empty(){return data.empty();};
private:
iter binarySearch(T toFind, iter min, iter max);
iter linearSearch(T toFind);
};

You could use the standard library a bit better instead of reinventing half of the wheel:

-
std::tuple does not sound like a bad idea, but I would probably return std::array instead to make it obvious that there is no way the two elements could be of a different type.

-
For example, linearSearch can be trivially reimplementend with std::find:

template 
typename std::list::iterator Quack::linearSearch(T toFind)
{
    return std::find(std::begin(data), std::end(data), toFind);
}

As an added bonus, it makes it clear that std::end(data) is returned when the list is empty (list::begin returns list::end when list::empty is true).

-
By the way, the standard library function std::lower_bound returns exactly the value you need to use insert, so Quack::insert could be written as:

template 
void Quack::insert(T dat)
{
    data.insert(
        std::lower_bound(std::begin(data), std::end(data), dat),
        dat
    );
}

-
That said, this is not optimal either. If you want to maintain a sorted list of values, you probably want to use an std::multiset or a similar structure that already keeps its data sorted for you.

Never forget that the standard library is your friend and probably always has the algorithm you need to perform a known task on a linear set of data :)

That was it for the standard library usage. Now let's go for another round of comments about other parts of the code:

-
typedef is a bit old-fashioned. You coud use C++11's type aliases instead. I find their order more consistent with assignment and aliasing in the rest of the language and as an added bonus, they can be templated:

using iter = typename std::list::iterator;

-
Range-based for loops are awesome. Let's use lots of them! Instead of this:

for(iter i = data.begin(); i != data.end(); i++)
{
    std::cout << *i << " ";
}

You will probably want to write that:

for (const T& elem: data)
{
    std::cout << elem << " ";
}

-
While iter works, it could be a good idea to name it iterator and add a bunch of other subtypes so that your class works more like the standard library containers.

-
That said, instead of a container, you might want your class to be container adapter like std::queue and std::stack. That means that, instead of keeping an std::list as an implementation detail, you could make the container type a template parameter and your Quack could then use any container supporting operations on both ends instead of begin stuck with std::list:

template
> class Quack
{
    protected:
        // The name isn't great, but I chose the one used
        // by std::queue and std::stack
        Container c;

    public:
        using container_type = Container;
        using value_type = typename Container::value_type;
        using size_type = typename Container::size_type;
        using reference = typename Container::reference;
        using const_reference = typename Container::const_reference;
        using iterator = typename Container::iterator;
        using const_iterator = typename Container::const_iterator;

    // Here goes the rest of the implementation...
};

That design makes for a far more flexible Quack than what you had until there. Moreover, it won't surprise people used to the standard library container adapters.

-
The name poppop is fun, but in practice pop would be enough and terser. Note that the standard library pop functions do not return a value and let top, front and back handle that for exception safety reasons. You might want to follow this design.

-
Don't forget to const-qualify functions that to do alter your Quack so that you can also use them on a const quack instance:

inline bool empty() const { return data.empty(); }
                    ^^^^^

Note that I took the liberty to drop the stray semicolon at the end of the definition: it is not needed and your compiler would have warned you about it. I also added some spaces because I like to breath :)

-
Generally speaking, it is not idiomatic for a class to have a print method in C++ since it binds it too tightly to a specific stream, in your case std::cout. The idiomatic way to make things displayable is to overload `operator

StackExchange Code Review Q#85598, answer score: 8