Adapters. STL (part 15)

stack, programming for beginners

A separate category of standard template library are adapters. Adapters - this is not a new concept or implementation, and the adaptation of existing concepts library for specific, commonly used target. Often this is done through the adaptation restrictions the functionality of the basic concepts for the adapter requests. The library presents the container adapter, iterators and functions.

The easiest way to show, both appear adapters example containers adapters: stack (stack), queue (queue), priority_queue (priority queue). Already it is clear from their listings, what:

  • It is widely and commonly used data structures;

  • They do not need any separate implementation. To ensure their functionality can be used (adapt) as base any from STL standard containers, which provides operations such as push_back, pop_back or pop_front (depending on the type of adapter);

  • The "extra" transaction in the arsenal of the base container should be excluded adapter (not to create such temptations ..., indexing operation, if the vector is used to adapt the stack);

And, instead of cumbersome template syntax definitions (header files <stack>, <queue> and t. P.), Refer to the example…

Let's start from the stack: characterized in stack, that access its elements can only be from one end, called the top of the stack. This is a collection of data, functioning on the principle of LIFO (Last In — First Out). Here's a simple example reveals little all stack functionality:

Let us analyze the code and make some conclusions:

  • first definition stack<string> (we do not use it on) declares a variable stack, whose elements are strings. Please note, what string objects are themselves STL containers. In this way, stack can contain elements of any nesting containers (which is characteristic of, and any other STL containers).

  • This definition ( stack<string> ) you can see, a stack description in the majority of examples. Many authors are unaware, that may be different. But we will use a different definition: stack< string, vector<string> > - A stack of strings (largely equivalent to the previous), but built on the base class vector<string>. As base can be used, for example, vector, list and and, or even your own container class, expanding base. Default (since 1st determining) used deque base. Sometimes people ask: why not write (defined as in the implementation of the stack): stack< vector<string> > (removing duplicate string)? Because (and it is quite possible) This description is an entirely different type: stack vectors strings (cm. above remark on the structural nesting containers).

  • Then follows initialization initial state vector of strings. Mark, that such a trick is only valid in C ++ 11 standard.

  • Next we see almost all operations (methods), required from the stack: push() – pushing of an object on the stack, top() – obtaining a reference to an element in the top of the stack, pop() – ejection of the upper member, size() – the current size of the stack, empty() – on the void check.

  • It is easy to understand, adapter stack lost inherent base container methods (at(), [ ] and etc.), but acquired (redefinition) own (push(), pop()).

Now let's see what came of it:

stack, programming for beginners

Having dealt with a stack of elementary Now just move the analogy to all. In contrast to stack – is a collection of data, functioning according to the FIFO principle (First In — First Out). (It is such a "pipe", one end of which something flows, and then from the other end follows.)

Special leave for example the queue is almost unchanged, making changes, required language semantics:

From us demanded change:

  • The line can not be built on the base vector container that does not have a method pop_front(), but may be based on the list, and, or any other container, implements a basic set of methods (front(), push_back(), pop_front()), by default and.

  • There is no method queue adapter top(), and a method similar import front().

And as a result we get (compare the results for the stack!):

stack, programming for beginners

Newsletter of programming:

Adapters. STL (part 15)
3.8 (75%) 4 votes

About Olej

practical experience about software development 40 years. Teacher Global Logic international software company. IBM Developer Works Permanent author of publications. Scientific editor of the computer literature publishing house "Symbol-Plus", St. Petersburg.

Leave a Reply

Your email address will not be published. Required fields are marked *