How to Access the Underlying Container of Stl Container Adaptors

Is there a way to access the underlying container of STL container adaptors?

I spotted the following solution somewhere on the web and I'm using it in my projects:

template <class T, class S, class C>
    S& Container(priority_queue<T, S, C>& q) {
        struct HackedQueue : private priority_queue<T, S, C> {
            static S& Container(priority_queue<T, S, C>& q) {
                return q.*&HackedQueue::c;
            }
        };
    return HackedQueue::Container(q);
}

int main()
{
    priority_queue<SomeClass> pq;
    vector<SomeClass> &tasks = Container(pq);
    return 0;
}

Have fun :).

C++ : STL Container adapters

When to initialize to the copy of a container and when to use an underlying container?

Both of these...

std::queue<int> second(mydeck);
std::queue<int,std::list<int> > fourth(mylist);

...construct and initialise a queue by copying elements from the container specified as constructor argument (i.e. mydeck and mylist respectively).

If you mean to ask why the second specifies a second template argument of std::list<int>, that's because std::queue can store the data in any container that provides the API functions it expects. From cppreference, that second template parameter is:

Container - The type of the underlying container to use to store the elements. The container must satisfy the requirements of SequenceContainer. Additionally, it must provide the following functions with the usual semantics:

    back()
    front()
    push_back()
    pop_front() 

The standard containers std::deque and std::list satisfy these requirements.

Of these, I'd guess that std::list would typically be more efficient for one or a very few elements (exactly where the cutoff is depends on object size, memory library performance characteristics, CPU cache sizes, system load etc. - it gets complicated), then std::deque will have better average performance and memory usage for larger numbers of elements (with fewer but larger dynamic memory allocations/deallocations). But even an educated guess can go badly wrong for some specific use cases - if you care enough to consider tuning this, you should measure performance with each candidate container, and your actual data and usage, to inform your decision. Having the container be a template parameter allows the programmer to choose what's best for their needs.

The parameter also has a default...

template <class T, class Container = std::deque<T>> class queue;

...so you only need to explicit specify a container if you're not happy to have it use a std::deque.

How to change the fundamental underlying container type for the adaptor containers?

Give the required container as templatized parameter. For example:

std::stack<int,std::vector<int> > stack_using_vector_of_int;
std::stack<std::string,std::list<std::string> > stack_using_list_of_string;

If you want to make sure stack always uses list, give a type definition of list_stack that always uses std::list as container.

Adding from Jarod42's comment:

Post C++11 you can use

template <typename T>
using list_stack = std::stack<T, std::list<T>>;

By default std::stack uses std::deque as underlying container which is almost always more efficient than using std::list or std::vector.

What are Containers/Adapters? C++

<joke>C++ is technical and hard to understand :-D</joke>

Containers are data types from STL that can contain data.

Example: vector as a dynamic array

Adapters are data types from STL that adapt a container to provide specific interface.

Example: stack providing stack interface on top of the chosen container

(side note: both are actually templates not data types, but the definition looks better this way)

Can I use member function of underlying container of priority_queue

The container adapters are designed specifically to abstract away the underlying container. It provides a new abstraction on its own.

So, no, you cannot call members of the vector inside the queue. What you can do however, is call functions on the vector before it enters the queue. And then move it in place:

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

int main(){
   vector<int>   v;
   v.reserve(25);
   v.push_back(1);

    priority_queue<int , vector<int>, greater<int>> p(greater<int>(), std::move(v));

    return 0;
} 

Still no way to output the contents of a queue or stack, as you can only access the top() element (on purpose, as part of the abstraction).

Why don't the standard C++ container adaptors provide a clear function?

Well, I think this is because clear was not considered a valid operation on a queue, a priority_queue or a stack (by the way, deque is not and adaptor but a container).

The only reason to use the container
adaptor queue instead of the container
deque is to make it clear that you are
performing only queue operations, and
no other operations. (from the sgi page on queue)

So when using a queue, all you can do is push/pop elements; clearing the queue can be seen as a violation of the FIFO concept. Consequently, if you need to clear your queue, maybe it's not really a queue and you should better use a deque.

However, this conception of things is a little narrow-minded, and I think clearing the queue as you do is fair enough.

Iterating vector-based priority_queue

In short, yes.

The standard [priqueue.members] defines the operators on a priority queue in terms of push/emplace/pop_back and heap operations. It is trivial to see that the size of the underlying container will be equal to the size of the priority queue, and that elements will be stored starting from the beginning of the container.

In fact, the standard even guarantees that the underlying container will be a heap as defined by the standard make_heap algorithm.

That said, it is likely worth considering whether or not priority_queue is the best solution for your problem if iteration is required.

Why don't the standard C++ container adaptors provide a clear function?

Well, I think this is because clear was not considered a valid operation on a queue, a priority_queue or a stack (by the way, deque is not and adaptor but a container).

The only reason to use the container
adaptor queue instead of the container
deque is to make it clear that you are
performing only queue operations, and
no other operations. (from the sgi page on queue)

So when using a queue, all you can do is push/pop elements; clearing the queue can be seen as a violation of the FIFO concept. Consequently, if you need to clear your queue, maybe it's not really a queue and you should better use a deque.

However, this conception of things is a little narrow-minded, and I think clearing the queue as you do is fair enough.

Difference between sequence containers and container adaptors in c++

Sequence containers

You could see sequence container as containers "built from scratch". They use different structures to hold data and have different algorithmic time to insert, delete and retreive element.

You can find a lot of information about the algorithmic time of containers here

Container adapters

Container adapters are behavior added over sequence containers making them respect different paradigms. The added behavior can be a stricter behavior (the stack will only allow you to pop/push item on it, no random insert). They are other type of containers that did not need a new storing behavior then those already existing. As an example, a stack could be built over a vector. It would then uses the data structure of vector, but restrain the usage to a certain set of functions to mimic a stack.

Most important over all this is to make sure that you use the right container to suit your needs. A stricter container will help you prevent missuses of your datum and knowing the usage of your data will help you chose the good container to get the best performances.

More information about container adapters can be found here

What should I use most of the time?

Many experts (Scott Meyer, Bjarne Stroustrup) suggest the use of the vector by default while others (like Herb Sutter as Steve Jessop pointed out) suggest the deque. I would strongly suggest you to chose the container that best suits your need.

---

Related Topics