Knowledge reserve of C + + system R & D Engineer

Object oriented and generic programming

(2) Algorithm

Various commonly used algorithms, such as sort, find, copy and for_each et al

Basic concepts

  • Algorithms: limited steps to solve logical or mathematical problems
  • Classification of algorithms
    • Qualitative change algorithm: refers to the content of elements in the interval that will be changed during operation. For example, copy, replace, delete and so on.
    • Non qualitative algorithm: it means that the element content in the interval will not be changed during the operation, such as finding, counting, traversing, finding extreme values, etc. The algorithm is mainly composed of header files.

inorder traversal

    for_each(iterator beg, iterator end, _func);//Traversal container
    transform(iterator beg1, iterator end1, iterator beg2, _func); //Transport container to another container

Search algorithm

    find(iterator beg, iterator end, value);//Find element
    find_if(iterator beg, iterator end, _Pred); //Find elements by criteria
    adjacent_find(iterator beg, iterator end); //Find adjacent duplicate elements
    bool binary_search(iterator beg, iterator end, value); //Binary search method, not available in unordered sequence
    count(iterator beg, iterator end, value);//Number of statistical elements
    count_if(iterator beg, iterator end, _Pred); //Count the number of elements by condition

Sorting algorithm

    sort(iterator beg, iterator end, _Pred); //Sort the elements in the container
    random_shuffle(iterator beg, iterator end); //Shuffle the elements in the specified range to adjust the order randomly
    merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest); // Container elements are merged and stored in another container
    reverse(iterator beg, iterator end);// Inverts the elements of the specified range

Copy and replace algorithm

    copy(iterator beg, iterator end, iterator dest); // Copy the specified range of elements in the container to another container
    replace(iterator beg, iterator end, oldvalue, newvalue); // Modify the old element of the specified range in the container to a new element
    rreplace(iterator beg, iterator end, oldvalue, newvalue);// Replace the elements that meet the conditions of the specified range in the container with new elements
    swap(container c1, container c2);// Swap elements of two containers

Arithmetic generation algorithm #include

    accumulate(iterator beg, iterator end, value); // Calculate the cumulative sum of container elements
    fill(iterator beg, iterator end, value);// Add element to container

Set algorithm

    set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);// Find the intersection of two containers. The two sets must be an ordered sequence
    set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);// Find the union of two containers. The two sets must be an ordered sequence
    set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest); // Find the difference set of two containers. The two sets must be an ordered sequence

(3) Iterator

Acts as the glue between the container and the algorithm.

Basic concepts

  • A method is provided to enable it to search the elements contained in a container in order without exposing the internal representation of the container.
  • Each container has its own iterator. The use of iterators is very similar to pointers. At the beginning of learning, we can understand that iterators are pointers. (the algorithm can access the container only through the iterator)


(4) Imitation function (function object)

The behavior is similar to the function, which can be used as a strategy of the algorithm. (note Lambda expression)

Basic concepts

  • Concept:
    • The class of overloaded function call operator () whose object is often called function object;
    • When a function object uses overloaded (), its behavior is similar to that of a function call, which is also called an imitation function
  • Essence: a function object is a class, not a function
  • characteristic:
    • When a function object is used, it can be called like an ordinary function, with parameters and return values;
    • Function object is beyond the concept of ordinary function, and function object can have its own state; Function objects can be passed as arguments
  • Predicate:
    • Functions that return bool types are called predicates;
    • If operator() accepts a parameter, it is called a unary predicate;
    • If operator() accepts two parameters, it is called a binary predicate

(5) Adapter

Something used to decorate a container or an interface to a functor or iterator.

(6) Space configurator: responsible for space configuration and management.

STL memory allocation mechanism, capacity expansion mechanism and so on

1. Memory allocation mechanism of STL container itself

  • Basic concepts

    • It is implemented through a default allocator provided by STL. This allocator is a memory manager composed of two-level allocators.
    • When the requested memory size is greater than 128 bytes, the first level allocator is started to allocate the heap space of the system directly through malloc
    • If the requested memory size is less than 128byte, start the second level allocator to take a piece of memory from a pre allocated memory pool and deliver it to the user.

    This memory pool consists of 16 free lists of different sizes (multiple of 8, 8 ~ 128bytes). The allocator will take the header block from the corresponding free block list to the user according to the size of the requested memory (round up the size to multiple of 8).

  • Advantages of this approach:
    1) Fast allocation and release of small objects. When a fixed size memory pool is pre allocated at one time, the operation of allocating and releasing small memory less than 128 bytes is only some basic pointer operations, which is less expensive than calling malloc/free directly. Small objects are allocated from the memory pool. This memory pool is used by the system to allocate a large enough area to the program for standby. When the memory pool is exhausted, a new area is applied to the system.
    2) The generation of memory fragments is avoided. The allocation of small objects in the program is easy to cause memory fragments, which brings great pressure to the memory management of the operating system. The increase of fragments in the system will not only affect the speed of memory allocation, but also greatly reduce the utilization of memory. The memory pool is used to organize the memory of small objects. From the perspective of the system, it is only a large memory pool, and the allocation and release of memory of small objects cannot be seen.
    3) Maximize memory utilization as much as possible. When the free area in the memory pool is not enough to allocate the required size, the allocation algorithm will link it to the corresponding free list, and then try to find out whether there is an area of appropriate size from the free list. However, this memory allocator is limited to STL containers and is not suitable for a general memory allocation. Because it requires that when releasing a memory block, the size of the memory block must be provided to determine which free list to recycle to

2. When STL adds an element, do you add a pointer to the element or copy the value

  • STL containers only support "value" semantics and not "reference (&)" semantics, not because the template type parameter cannot be a reference, but because if the container element is a reference type, there will be "referenced reference", "referenced pointer" and other languages and semantics not supported by C + + language.
  • Smart pointer is an object that simulates the behavior of the original pointer, so it can also be used as an element of a container in theory, just as the original pointer can be used as a container element. However, smart pointers are special objects after all. They add the ability to automatically destroy real valued objects on the basis of the original pointer's ability to share real valued objects. If they are used as elements of containers, it may lead to the sharing of element object real values between containers, which not only does not conform to the concept and "value" semantics of stl containers, but also has potential security risks, but also has many application limitations, especially like auto in STL_ PTR is a smart pointer.

3. How to expand memory when the container is full

  • 0.5x, 1.5x or 2x expansion

Tags: C++ Interview

Posted by foyer on Sat, 26 Mar 2022 13:30:00 +0300