Programming Taskbook

Russian

Electronic problem book on programming

©  M. E. Abramyan (Southern Federal University, Shenzhen MSU-BIT University), 1998–2026

Application of Various C++ Standard Library Facilities: STL7Mix4

Creating a Project Template and Getting Acquainted with the Task. Additional Problem Book Window Features for Viewing File Data

The STL7Mix group is the final group included in Programming Taskbook for STL. Each of the previous groups in the problem book is dedicated to a separate part of the standard library: iterators, sequence containers, algorithms, strings, associative containers, function objects. The tasks in the STL7Mix group are designed to develop and consolidate skills in the combined use of various STL library components; when performing them, it is required to independently choose the library facilities that ensure the required result. Another distinguishing feature of the tasks in the last group is the more complex nature of the initial sequences: their elements are records consisting of several fields. These features bring the tasks of the STL7Mix group closer to real-world problems encountered when processing complex data structures.

The set of tasks included in the STL7Mix group was previously used in Programming Taskbook for LINQ as the LinqObj group. The Programming Taskbook for LINQ problem book is designed for studying the LINQ technology, available for .NET platform languages (C#, VB.NET, PascalABC.NET) and intended to simplify solving the same tasks for which the STL library was developed, namely, tasks related to sequence processing. Thanks to the matching formulations of the tasks in the STL7Mix and LinqObj groups, they can be used for practical comparative study of both technologies, which will allow for a deeper understanding of their main ideas and features. In particular, one can compare the solutions for tasks STL7Mix4 and LinqObj4 provided in the help systems of these problem books.

So, let's turn to task STL7Mix4. This is a relatively simple task related to processing a single sequence.

STL7Mix4°. The initial sequence contains information about clients of the fitness center. Each element of the sequence includes the following integer fields:

<Year> <Month number> <Session length (in hours)> <Client code>

For each client present in the source data, determine the total session length for all years (output the total length first, then the client code). The information about each client should be displayed on a new line and ordered by descending total length, and if they are equal — by ascending client code.

The project template for this task, as for any tasks performed using the Programming Taskbook problem book, should be created using the PT4Load software module. After creating this project, automatically launching the Visual Studio environment, and loading the created project into it, the file STL7Mix4.cpp will be displayed on the screen, into which the solution to the task must be entered. Let's provide the contents of this file:

#include "pt4.h"
using namespace std;

#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
struct Data
{
    int code, year, month, len;
    operator string()
    {
        ostringstream os;
        os << "{ code = " << code << ", year = " << year
            << ", month = " << month << ", len = " << len << " }";
        return os.str();
    }
};

istream& operator>>(istream& is, Data& p)
{
    return is >> p.year >> p.month >> p.len >> p.code;
}

void Solve()
{
    Task("STL7Mix4");
    string name1, name2;
    pt >> name1 >> name2;
    ifstream f1(name1);
    vector<Data> V((istream_iterator<Data>(f1)), istream_iterator<Data>());
    f1.close();
    ShowLine(V.begin(), V.end(), "V: ");

    ofstream f2(name2);

    f2.close();
}

The templates for the tasks in the STL7Mix group are even more detailed than the templates for the previous groups of the PT for STL problem book. Recall that the STL1Iter group used the simplest templates containing the minimally necessary set of #include directives and the definition of the Solve function, including only the call to the Task function. In subsequent groups, the templates included the description of the used containers and even the input of initial data into them. This freed students from standard initial actions (already practiced when performing previous tasks) and allowed them to immediately focus on the semantic part of the algorithm.

Similar goals are pursued by the detailed templates of the STL7Mix group. They not only provide input of the initial data (stored in external files) but also allow saving this data in a vector, with each data element represented as a Data structure, also defined in the template. In addition to the fields, this structure defines an operator for converting the structure to a string, which makes it possible to use the template version of the ShowLine function for quick output of the obtained sequence of structures to the debug section of the problem book window (a call to this version of the ShowLine function is already present in the template). To organize the input of initial data using file stream iterators, the program redefines the >> operator for the Data structure (note the constructor of the vector V, which contains two iterator parameters, the first of which is enclosed in additional parentheses; the reason for this is explained in the note for task STL2Seq1). Finally, the template includes all the statements that provide opening and closing of the used text files.

It should be noted that the C++11 standard introduced the possibility of using string type parameters in stream constructors; thus, in modern versions of the language, the call to the c_str function for string parameters of these constructors could be avoided.

Having such a template, we can immediately proceed to implement the substantive part of the program: processing the initial sequence (already available as a vector of type vector<Data>) to obtain the resulting sequence and output it to a text file in the required format.

After running the created program template, we will see on the screen the problem book window containing the task formulation, an example of initial data and correct results, as well as string representations of all elements of the initial set, output by the ShowLine function to the debug section.

The information panel (light blue) notes that all initial data have been input, and the results file is empty. Thus, everything is ready for implementing the algorithm for processing the initial data.

However, before proceeding to the description of the solution process itself, let's recall some capabilities of the problem book window that may be useful when analyzing initial and resulting data presented as large text files.

Each line of a text file is enclosed in quotes and displayed on a separate screen line; next to the first line of the file, its sequence number, equal to 1, is indicated. In the initial data and results sections, the file contents are highlighted in a teal color (color highlighting allows distinguishing file lines from other data, as well as from comments). In the section with the correct solution, all data is displayed in gray to distinguish it from the "real" data found by the student's program.

The window variant shown in the previous figure corresponds to the abbreviated file data display mode, in which only the initial part of the file's contents is displayed for each file (from one to five lines). The ellipsis (...) placed at the bottom of those sections that display abbreviated data indicates that part of the data is missing. This mode is convenient for initial familiarization with the task, as it allows displaying the contents of all sections in a relatively small window. For a more detailed analysis of the data, as well as when comparing the obtained erroneous results with the example of the correct solution, the full display mode for text file contents should be used.

To switch between the abbreviated and full file data display modes, it is sufficient to press the [Ins] key or double-click the mouse in one of the sections with file data. You can also click on the square marker that appears in the upper right corner of the initial data section if the window contains file data. The image on this marker serves as an indicator of the mode: the variant with the arrow pointing down denotes the abbreviated display mode (when hovering the mouse over the marker in this case, the tooltip "Expand contents of the text file (Ins)" is displayed); the variant with the arrow pointing up denotes the full display mode (associated with the tooltip "Collapse contents of the text file (Ins)").

The following figure shows the window view in the full text file display mode. In this mode, the sequence number is indicated before each file line. When the window is closed, the current display mode is remembered and restored in subsequent program runs.

In cases where the window size is insufficient to display all data, the window is equipped with a scroll bar, and, moreover, additional markers are displayed on it (see the previous figure). Scrolling the window contents is easiest to perform using the [Home], [End], [Up], [Down], [PgUp], [PgDn] keys, as well as using the mouse wheel.

The group of markers displayed in the upper left corner of the section with the task formulation is intended for quickly displaying various sections related to the task: clicking on the marker moves to the beginning of the next section (see the next figure), clicking on the marker moves to the beginning of the previous section. The sections are cycled through. The marker allows switching between the results section and the example of the correct solution if the window contains both of these sections. Instead of clicking on the indicated markers, you can press the corresponding key: [+], [–] or [/].

Note the marker that appears in the upper right corner of the section with the task formulation when a scroll bar is displayed in the window. This marker (and the associated [Del] key) allows hiding the formulation section, thereby increasing the window area for displaying data from other sections. Note that the [Del] key allows hiding the formulation section even if the marker is not displayed on the screen.

Finally, two markers that may appear in the lower left corner of the window should be mentioned. These are the and markers, which allow switching between multiple pages of the debug section. Recall (see the first figure) that by default, the debug section displays the string representations of the elements of the initial sequence. The debug section page on which data is output by the Show and ShowLine functions is associated with the marker, which is displayed on the screen only if the debug section contains another non-empty page (associated with the marker) — the page with additional notes for the task being performed. If the task contains such notes, then to view them it is sufficient to either press the [Shift]+[1] combination (corresponding to the "!" character), or press the left or right arrow key, or click the mouse on the marker. As a result, the contents of the page with the additional note will be displayed in the debug section (below is an example of the window in the abbreviated file data display mode with an additional note for task STL7Mix4):

Performing the Task

Having completed the overview of the additional capabilities of the problem book window and familiarized ourselves with task STL7Mix4, let's proceed to perform it.

During the processing of the initial sequence (which is already stored in the vector V of type vector<Data>), we must, firstly, perform grouping of the initial data by the code field (client code), determining for each client the total duration of their training ("the total session length"), and, secondly, sort the data obtained as a result of grouping by a set of keys (main key — total session length, sorted in descending order; subordinate key — client code, sorted in ascending order for equal values of the main key).

Methods of data grouping based on STL containers were analyzed in detail in the tasks of the STL5Assoc group (see the subgroup "Maps. Data Grouping and Combining", which includes tasks STL5Assoc15–STL5Assoc36). One effective grouping method is based on using a map; it is this method that the note for our task reminds about.

Let's define an auxiliary map M with a key — the client code (integer type) and a value — the total session length (also integer type):

    map<int, int> M;

To fill this map, we must iterate through all elements of the vector V and for each element e execute the following statement:

    M[e.code] += e.len;

Recall that this statement uses the following feature of the indexing operation for a map: if a map element with the specified key does not exist, it is automatically created, and its value is assigned the default value for the given type (in our case — the number 0).

Iterating through the elements of the vector V can be done in various ways. Let's describe two of the shortest and most illustrative ways, based on new features that appeared in the C++11 standard.

The first of these methods uses the for_each algorithm with a lambda expression as the function object:

    for_each(V.begin(), V.end(), [&M](Data e){M[e.code] += e.len;});

Note the first component of the lambda expression: [&M]. It means that this lambda expression captures the external variable M, and the capture is done by reference, which allows modifying this variable inside the lambda expression.

The second method is even more illustrative; it is based on a special variant of the for loop designed for iterating over the elements of a container:

    for (auto e : V)
        M[e.code] += e.len;

Instead of the auto specifier, meaning that the compiler must deduce the type of the loop parameter e based on the type of elements in the container V, an explicit Data specifier can be specified; however, the variant with auto is preferable due to its universality.

After performing the grouping, it is desirable to review its results. The easiest way is to output the obtained data to the debug section. To avoid cluttering this section with unnecessary information, let's remove the ShowLine statement added to the program template when it was created. To output the elements of the map M to the debug section, let's use a for loop (which can be placed anywhere in the program after the statements performing the grouping):

    for (auto e : M)
    {
        Show(e.second);
        ShowLine(e.first);
    }

When running the new version of the program, the contents of the map M will be output to the debug section, with the value of each element output first, and then — its key. Comparing this data with the example of the correct solution, it is easy to verify that the grouping was performed correctly (only the order of the obtained data is incorrect).

Remark. In version 4.16 of the problem book for C++, additional debugging capabilities were implemented. In particular, in this version, the Show and ShowLine functions can be used to output containers whose elements are not only numbers or strings but also pairs (also containers whose elements are themselves containers can be output). Using this new capability, we can simplify the above fragment of debug output for the map M:

    ShowLine(M.begin(), M.end());

As a result, the debug data will look as follows (now the first field is output first, and then — the second field, separated by a comma and enclosed in parentheses):

So, we have successfully passed the first stage of solving the task by performing the grouping of the initial data. It remains to sort the obtained data in accordance with the task conditions.

Since in the map container the order of elements is fixed and determined by the key values (by default, elements are arranged in ascending order of keys — see the previous figure), to change the order of elements, they must be copied into a container for which a sorting algorithm can be used, for example, into a vector V1.

The type of elements of the vector V1 must match the type of elements of the map M, i.e., pair<int, int> (for this type, it is convenient to define a shorter alias); in this case, to fill the vector with data, it is sufficient to use the constructor with two iterator parameters:

    typedef pair<int, int> p;
    vector<p> V1(M.begin(), M.end());

For the filled vector V1, the sorting algorithm must be called, passing to it as the last parameter a function object that defines the comparison relation for the pair pair<int, int>. In this case, since the elements of the vector V1 are already ordered in ascending order of keys (stored in the first field), it is convenient to apply a stable sorting algorithm stable_sort:

    stable_sort(V1.begin(), V1.end(),
    [](p e1, p e2){return e1.second > e2.second;});

This variant of the algorithm sorts the elements in descending order of the second field, and the relative arrangement of elements with equal second fields does not change (due to the stable nature of the sorting). Thus, exactly the order required in the task is ensured: elements are arranged in descending order of the second field (i.e., total session length), and elements with the same second field are arranged in ascending order of the first field (i.e., client code).

It remains to output the sorted vector V1. For this, either the for_each algorithm or a for loop can be used. Let's use the variant of the for loop that provides iteration over the sequence elements (this loop must be placed between the statement defining the stream f2 and the statement closing it f2.close()):

    for (auto e : V1)
        f2 << e.second << " " << e.first << endl;

After running this version of the program and successfully passing the required nine tests, a message will be displayed that the task has been solved.

Let's provide the Solve function with one of the variants of the correct solution, removing from it all debug output statements (the statements that were not contained in the initial template text are highlighted in bold in the function text):

void Solve()
{
    Task("STL7Mix4");
    string name1, name2;
    pt >> name1 >> name2;
    ifstream f1(name1);
    vector<Data> V((istream_iterator<Data>(f1)), istream_iterator<Data>());
    f1.close();

    map<int, int> M;
    for (auto e : V)
        M[e.code] += e.len;
    typedef pair<int, int> p;
    vector<p> V1(M.begin(), M.end());
    stable_sort(V1.begin(), V1.end(),
        [](p e1, p e2){return e1.second > e2.second;});

    ofstream f2(name2);
    for (auto e : V1)
        f2 << e.second << " " << e.first << endl;
    f2.close();
}

Other Solution Variants

The solution would be more illustrative if the fields of the vector V1 elements had, like the fields of the initial vector V, meaningful names, for example, code and sumlen (total session length). This can be achieved by introducing an auxiliary structure type with the specified fields. Additionally, in the new type (let's call it Res), additional member functions can be defined that will simplify its use.

So, let's describe the following structure:

struct Res
{
    int code, sumlen;

    Res(pair<int, int> p)
    {
        code = p.first;
        sumlen = p.second;
    }

    bool operator<(Res b) const
    {
        return this->sumlen > b.sumlen;
    }
};

ostream& operator<<(ostream& os, const Res& r)
{
    return os << r.sumlen << " " << r.code;
}

In it, besides the two fields, a constructor is defined that allows implicit conversion of a pair<int, int> to a structure of type Res, and the < operation is defined that allows comparing elements of type Res (taking into account the conditions of the task being solved, we consider that an element a of type Res is "less than" an element b of type Res if a.sumlen > b.sumlen). Moreover, we defined the << operation for the Res structure, which simplifies writing data of type Res to output streams (when defining this operation, we took into account the order of outputting fields specified in the task).

Remark. The < operation could be defined as an ordinary function (not a member function of the Res structure):

bool operator<(Res a, Res b)
{
    return a.sumlen > b.sumlen;
}

Using the Res type, we can obtain a more illustrative variant of the task solution, also getting rid of the lambda expression in the sorting algorithm (if the &lt; operation is defined for the sorted elements, then the function object does not need to be specified in the sorting algorithm: by default, the < operation will be applied for comparing elements):

void Solve()
{
    Task("STL7Mix4");
    string name1, name2;
    pt >> name1 >> name2;
    ifstream f1(name1);
    vector<Data> V((istream_iterator<Data>(f1)), istream_iterator<Data>());
    f1.close();

    map<int, int> M;
    for (auto e : V)
        M[e.code] += e.len;
    vector<Res> V1(M.begin(), M.end());
    stable_sort(V1.begin(), V1.end());

    ofstream f2(name2);
    for (auto e : V1)
        f2 << e << endl;
    f2.close();
}

For the ability to fill the vector V1 with data taken from the map M, it is necessary that the pair pair<int, int> can be implicitly converted to the Res type. We ensured this possibility by defining the corresponding constructor for the Res type.

Remark. Thanks to the redefinition of the << operation for the Res type, we can organize the writing of the obtained vector V1 to a file using the copy algorithm in combination with the ostream_iterator instead of a loop:

    copy(V1.begin(), V1.end(), ostream_iterator<Res>(f2, "\n"));

For the Res type, as for the Data type, an operation for conversion to the string type can be defined; in this case, it is convenient to use a string representation that matches the form of the data that needs to be written to the resulting file:

operator string()
{
    ostringstream os;
    os << sumlen << " " << code;
    return os.str();
}

This member function must be added to the definition of the Res structure. With its presence, the output of results can be arranged without resorting to the redefined << operation for Res, using an explicit cast to the string type:

    for (auto e : V1)
        f2 << (string)e << endl;

A similar output variant can be used in the copy algorithm:

    copy(V1.begin(), V1.end(), ostream_iterator<string>(f2, "\n"));

Moreover, the presence of the operation for converting the Res structure to the string type allows using the Show and ShowLine debug functions both for individual variables of type Res and for containers with elements of type Res, for example:

    ShowLine(V1.begin(), V1.end());

Designed by
M. E. Abramyan and V. N. Braguilevsky

Last revised:
01.01.2026