Basic concepts of the standard C ++ library

    This article defines the basic concepts of the standard C ++ library. It is provided to refer to it in the future.

    The largest part of the standard C ++ library is the STL (Standard Template Library). The STL library contains five main types of components:

    • container (container) : manages a set of objects in memory.
    • iterator (iterator) : provides for the algorithm means to access the contents of the container.
    • algorithm (algorithm) : determines the computational procedure.
    • function object : encapsulates a function in an object for use by other components.
    • adapter (adapter) : adapts the component to provide a different interface.



    All components satisfy a number of requirements, therefore they are in good agreement with each other.

    It follows from the definition of a container that any user data structure is a container. In our case, containers have standard data structures , such as a list (list), a vector (vector), a dictionary (map), and many others. Formal requirements for containers are quite extensive, but the basic rule is access to the elements. Access to container elements is carried out through special objects - iterators(see below). You may not know how the elements of the container are located in memory, but you know for sure that iterators can be iterated sequentially, and each of them will provide access to the element. An iterator pointing to the first element can be obtained using the iterator begin () method ; container. The iterator pointing to the last element can be obtained using the method iterator end (); container. In other words, iterators are located in a semi-interval (or half -cut), which can be formally written as [begin, end). Sample container declaration:

    structa_container {structan_iterator;an_iterator begin();
        an_iterator end();
    };

    In the expected standard C ++ 20, it is proposed to use a structure that encapsulates semi-intervals - ranges


    Iterator - an object that provides access to the elements of the container and allows them to iterate. The iterator is a container property. In the first implementations of the standard C ++ library, the iterator was implemented as a pointer to a container element. In modern implementations, this is a class that encapsulates a pointer to a container object.

    The main requirements for iterators are the presence of dereference operators and increments. Below is the container declaration with an iterator.

    template<typename TYPE>
    structa_container {structan_iterator {voidoperator++();
            TYPE& operator*();
        };
        an_iterator begin();
        an_iterator end();
    };

    I can not give a better definition of the algorithm than the standard one: the algorithm is a sequence of actions that leads in a finite number of steps to the desired result .

    In the case of STL, algorithms are implemented by template functions, which take as input parameters half-intervals of iterators. The general signature of these algorithms is described as follows:

    template<typename ITERATOR, typename RESULT>
    RESULT an_algorithm(ITERATOR first, ITERATOR last, ...);

    In the class declaration, you can override the operator (). If this operator is redefined in a class, then the objects of this class get the properties of functions (they can be used as functions). Such objects are called functional or functors . It is convenient to use functors when a function must have a “memory”, and also as a replacement for pointers to functions.
    Starting with the standard C ++ 11, there is the possibility of briefly writing functors - lambda functions.
    There are no special requirements for functors. Unless inheritance from the function functor can sometimes be required (up to the standard C ++ 11 - unary_function or binary_function). A small example of the implementation of the functor:

    template<typename TYPE>
    structplus{TYPE operator()(const TYPE& p1, const TYPE& p2)const{
            return p1 + p2;
        }
    };

    STL also offers a number of classes and functions (fukntory) that convert the interface to the desired. In particular, there is the stack adapter, which is container-based implements, respectively, the stack. As an example, consider a binary function adapter to a unary function (at the moment this function is declared obsolete in the C ++ standard):

    template<typename BIDIRECTIONAL_FUNCTION, typename TYPE>
    classbind1st {
        BIDIRECTIONAL_FUNCTION _bf;
        TYPE _first;
    public:
        bind1st(BIDIRECTIONAL_FUNCTION bf, TYPE first): _bf(bf), _first(first) {}
        TYPE operator()(const TYPE& p)const{
            return _bf(_first, p);
        }
    };

    For self-reading


    1. Draft standard C ++ 20 on github
    2. C ++ Reference
    3. C ++ Application Development
    4. Range-v3, suggestion for standard

    Also popular now: