String handling

Applications with a graphical user interface (and games surely fall into this category) are able to interact with users by displaying text and by expecting textual input from the user. We have already scratched the surface of this topic in the previous chapters using the QString class. Now, we will go into further detail.

String encodings

The C++ language does not specify encoding of strings. Thus, any char* array and any std::string object can use an arbitrary encoding. When using these types for interaction with native APIs and third-party libraries, you have to refer to their documentation to find out which encoding they use. The encoding used by native APIs of the operating system usually depends on the current locale. Third-party libraries often use the same encoding as native APIs, but some libraries may expect another encoding, for example, UTF-8.

A string literal (that is, each bare text you wrap in quotation marks) will use an implementation defined encoding. Since C++11, you have an option to specify the encoding your text will have:

u8"text" will produce a UTF-8 encoded const char[] array
u"text" will produce a UTF-16 encoded const char16_t[] array
U"text" will produce a UTF-32 encoded const char32_t[] array

Unfortunately, the encoding used for interpreting the source files is still implementation defined, so it’s not safe to put non-ASCII symbols in string literals. You should use escape sequences (such as \unnnn) to write such literals.

Text in Qt is stored using the QString class that uses Unicode internally. Unicode allows us to represent characters in almost all languages spoken in the world and is the de facto standard for native encoding of text in most modern operating systems. There are multiple Unicode-based encodings. Memory representation of the content of QString resembles UTF-16 encoding. Basically, it consists of an array of 16-bit values where each Unicode character is represented by either 1 or 2 values.

When constructing a QString from a char array or an std::string object, it’s important to use a proper conversion method that depends on the initial encoding of the text. By default, QString assumes UTF-8 encoding of the input text. UTF-8 is compatible with ASCII, so passing UTF-8 or ASCII-only text to QString(const char *str) is correct. QString provides a number of static methods to convert from other encodings such as QString::fromLatin1() or QString::fromUtf16()QString::fromLocal8Bit() method assumes the encoding corresponding to the system locale.

If you have to combine both QString and std::string in one program, QString offers you the toStdString() and fromStdString() methods to perform a conversion. These methods also assume UTF-8 encoding of std::string, so you can’t use them if your strings are in another encoding.

Default representation of string literals (for example, "text") is not UTF-16, so each time you convert it to a QString, an allocation and conversion happens. This overhead can be avoided using the QStringLiteral macro:

QString str = QStringLiteral("I'm writing my games using Qt"); 

QStringLiteral does two things:

  • It adds a u prefix to your string literal to ensure that it will be encoded in UTF-16 at compile time
  • It cheaply creates a QString and instructs it to use the literal without performing any allocation or encoding conversion

It’s a good habit to wrap all your string literals (except the ones that need to be translated) into QStringLiteral but it is not required, so don’t worry if you forget to do that.

QByteArray and QString

QString always contains UTF-16 encoded strings, but what if you have data in an unknown (yet) encoding? Also, what if the data is not even text? In these cases, Qt uses the QByteArray class. When you read data directly from a file or receive it from a network socket, Qt will return the data as a QByteArray, indicating that this is an arbitrary array of bytes without any information about the encoding:

QFile file("/path/to/file");
file.open(QFile::ReadOnly);
QByteArray array = file.readAll();

The closest equivalent of QByteArray in the standard library would be std::vector<char>. As the name implies, this is just an array of bytes with some helpful methods. In the preceding example, if you know that the file you read is in UTF-8, you can convert the data to a string, as follows:

QString text = QString::fromUtf8(array);

If you have no idea what encoding the file uses, it may be best to use the system encoding, so QString::fromLocal8Bit would be better. Similarly, when writing to a file, you need to convert the string to a byte array before passing it to the write() function:

QString text = "new file content\n";
QFile file("/path/to/file");
file.open(QFile::WriteOnly);
QByteArray array = text.toUtf8();
file.write(array);

Basic string operations

The most basic tasks that involve text strings are the ones where you add or remove characters from the string, concatenate strings, and access the string’s content. In this regard, QString offers an interface that is compatible with std::string, but it also goes beyond that, exposing many more useful methods.

Adding data at the beginning or at the end of the string can be done using the prepend() and append() methods. Inserting data in the middle of a string can be done with the insert() method that takes the position of the character where we need to start inserting as its first argument and the actual text as its second argument. All these methods have a couple of overloads that accept different objects that can hold textual data, including the classic const char* array.

Removing characters from a string is similar. The basic way to do this is to use the remove() method that accepts the position at which we need to delete characters, and the number of characters to delete is as shown:

QString str = QStringLiteral("abcdefghij");
str.remove(2, 4); // str = "abghij" 

There is also a remove() overload that accepts another string. When called, all its occurrences are removed from the original string. This overload has an optional argument that states whether comparison should be done in the default case-sensitive (Qt::CaseSensitive) or case-insensitive (Qt::CaseInsensitive) way:

QString str = QStringLiteral("Abracadabra");
str.remove(QStringLiteral("ab"), Qt::CaseInsensitive);
// str = "racadra"

To concatenate strings, you can either simply add two strings together, or you can append one string to the other:

QString str1 = QStringLiteral("abc");
QString str2 = QStringLiteral("def");
QString str1_2 = str1 + str2;
QString str2_1 = str2;
str2_1.append(str1); 

Accessing strings can be divided into two use cases. The first is when you wish to extract a part of the string. For this, you can use one of these three methods—left()right(), and mid()—that return the given number of characters from the beginning or end of the string or extract a substring of a specified length, starting from a given position in the string:

QString original = QStringLiteral("abcdefghij");
QString l = original.left(3); // "abc"
QString r = original.right(2); // "ij"
QString m = original.mid(2, 5); // "cdefg" 

The second use case is when you wish to access a single character of the string. The use of the index operator works with QString in a similar fashion as with std::string, returning a copy or non-const reference to a given character that is represented by the QChar class, as shown in the following code:

QString str = "foo";
QChar f = str[0]; // const
str[0] = 'g'; // non-const 
QChar f = str.at(0); 

The string search and lookup

The second group of functionalities is related to searching for the string. You can use methods such as startsWith()endsWith(), and contains() to search for substrings in the beginning or end or in an arbitrary place in the string. The number of occurrences of a substring in the string can be retrieved using the count() method.

If you need to know the exact position of the match, you can use indexOf() or lastIndexOf() to receive the position in the string where the match occurs. The first call works by searching forward, and the other one searches backwards. Each of these calls takes two optional parameters—the second one determines whether the search is case-sensitive (similar to how remove works). The first one is the position in the string where the search begins. It lets you find all the occurrences of a given substring:

int pos = -1;
QString str = QStringLiteral("Orangutans like bananas.");
do {
    pos = str.indexOf("an", pos + 1);
    qDebug() << "'an' found starts at position" << pos;
} while(pos != -1); 

Dissecting strings

There is one more group of useful string functionalities that makes QString different from std::string, that is, cutting strings into smaller parts and building larger strings from smaller pieces.

Very often, a string contains substrings that are glued together by a repeating separator (for example, "1,4,8,15"). While you can extract each field from the record using functions that you already know (for example, indexOf), an easier way exists. QString contains a split() method that takes the separator string as its parameter and returns a list of strings that are represented in Qt by the QStringList class. Then, dissecting the record into separate fields is as easy as calling the following code:

QString record = "1,4,8,15,16,24,42";
QStringList items = record.split(",");
for(const QString& item: items) {
    qDebug() << item;
}

The inverse of this method is the join() method present in the QStringList class, which returns all the items in the list as a single string merged with a given separator:

QStringList fields = { "1", "4", "8", "15", "16", "24", "42" };
QString record = fields.join(","); 

Converting between numbers and strings

QString also provides some methods for convenient conversion between textual and numerical values. Methods such as toInt()toDouble(), or toLongLong() make it easy to extract numerical values from strings. All such methods take an optional bool *ok parameter. If you pass a pointer to a bool variable as this parameter, the variable will be set to true or false, depending on whether the conversion was successful or not. Methods returning integers also take the second optional parameter that specifies the numerical base (for example, binary, octal, decimal, or hexadecimal) of the value:

bool ok;
int v1 = QString("42").toInt(&ok, 10);
// v1 = 42, ok = true
long long v2 = QString("0xFFFFFF").toInt(&ok, 16);
// v2 = 16777215, ok = true
double v3 = QString("not really a number").toDouble(&ok);
//v3 = 0.0, ok = false

A static method called number() performs the conversion in the other direction—it takes a numerical value and number base and returns the textual representation of the value:

QString txt = QString::number(42); // txt = "42" 

This function has some optional arguments that allow you to control the string representation of the number. For integers, you can specify the numerical base. For doubles, you can choose the scientific format 'e' or the conventional format 'f' and specify the number of digits after the decimal delimiter:

QString s1 = QString::number(42, 16); // "2a"
QString s2 = QString::number(42.0, 'f', 6); // "42.000000"
QString s3 = QString::number(42.0, 'e', 6); // "4.200000e+1"
QString str;
str.setNum(1234);       // str == "1234"

Other Useful Fuctions

QString str;
QString csv = "forename,middlename,surname,phone";
QString path = "/usr/local/bin/myapp"; // First field is empty
QString::SectionFlag flag = QString::SectionSkipEmpty;

str = csv.section(',', 2, 2);   // str == "surname"
str = path.section('/', 3, 4);  // str == "bin/myapp"
str = path.section('/', 3, 3, flag); // str == "myapp"
str = csv.section(',', -3, -2);  // str == "middlename,surname"
str = path.section('/', -1); // str == "myapp"
QString str = "  lots\t of\nwhitespace\r\n ";
str = str.simplified();
// str == "lots of whitespace";

and are there iterator functions like begin and end

QString x = "Say yes!";
QString y = "no";
x.replace(4, 3, y);
// x == "Say no!"
QString s = "Banana";
s.replace(QRegExp("a[mn]"), "ox");
// s == "Boxoxa"
QString str = "colour behaviour flavour neighbour";
str.replace(QString("ou"), QString("o"));
// str == "color behavior flavor neighbor"
QString str("LOGOUT\r\n");
str.chop(2);//remove n characters from the end 
// str == "LOGOUT"
QString str = "Vladivostok";
str.truncate(4);
// str == "Vlad"

Using arguments in strings

const int fieldWidth = 4;
qDebug() << QStringLiteral("%1 | %2").arg(5, fieldWidth).arg(6, fieldWidth);
qDebug() << QStringLiteral("%1 | %2").arg(15, fieldWidth).arg(16, fieldWidth);
// output:
// "   5 |    6"
// "  15 |   16"
QString str = tr("Copying file %1 of %2").arg(current).arg(total); 

Regular expressions

QRegularExpression regex("[1-9]\\d{0,2}\\s*(mg|g|kg)");
regex.setPatternOptions(QRegularExpression::CaseInsensitiveOption);
qDebug() << regex.match("100 kg").hasMatch();       // true
qDebug() << regex.match("I don't know").hasMatch(); // false
QRegularExpression regex("[1-9]\\d{0,2}\\s*(mg|g|kg)",
     QRegularExpression::CaseInsensitiveOption);

When we need to test an input, all we have to do is call match(), passing the string we would like to check against it. In return, we get an object of the QRegularExpressionMatch type that contains all the information that is further needed—and not only to check the validity. With QRegularExpressionMatch::hasMatch(), we then can determine whether the input matches our criteria, as it returns true if the pattern could be found. Otherwise, of course, false is returned.

After we have checked that the sent guess is well formed, we have to extract the actual weight from the string. In order to be able to easily compare the different guesses, we further need to transform all values to a common reference unit. In this case, it should be a milligram, the lowest unit. So, let’s see what QRegularExpressionMatch can offer us for this task.

With capturedTexts(), we get a string list of the pattern’s captured groups. In our example, this list will contain “23kg” and “kg”. The first element is always the string that was fully matched by the pattern. The next elements are all the substrings captured by the used brackets. Since we are missing the actual number, we have to alter the pattern’s beginning to ([1-9]\d{0,2}). Now, the list’s second element is the number, and the third element is the unit. Thus, we can write the following:

int getWeight(const QString &input) {
    QRegularExpression regex("\\A([1-9]\\d{0,2})\\s*(mg|g|kg)\\z");
    regex.setPatternOptions(QRegularExpression::CaseInsensitiveOption);
    QRegularExpressionMatch match = regex.match(input);
    if(match.hasMatch()) {
        const QString number = match.captured(1);
        int weight = number.toInt();
        const QString unit = match.captured(2).toLower();
        if (unit == "g") {
            weight *= 1000;
        } else if (unit == "kg") {
            weight *= 1000000 ;
        }
        return weight;
    } else {
        return -1;
    }
}

In the function’s first two lines, we set up the pattern and its option. Then, we match it against the passed argument. If QRegularExpressionMatch::hasMatch() returns true, the input is valid and we extract the number and unit. Instead of fetching the entire list of captured text with capturedTexts(), we query specific elements directly by calling QRegularExpressionMatch::captured(). The passed integer argument signifies the element’s position inside the list. So, calling captured(1) returns the matched digits as a QString.

Lastly, let’s take a final look at how to find, for example, all numbers inside a string, even those leading with zeros:

QString input = QStringLiteral("123 foo 09 1a 3");
QRegularExpression regex("\\b\\d+\\b");
QRegularExpressionMatchIterator i = regex.globalMatch(input);
while (i.hasNext()) {
    QRegularExpressionMatch match = i.next();
    qDebug() << match.captured();
}

very important point you can use regular expression with almost functions of QString like split , indexof , contains , count, replace, remove and section

List Of String

filter by sub string or regular expression

QStringList list;
    list << "Bill Murray" << "John Doe" << "Bill Clinton";

    QStringList result;
    result = list.filter("Bill");
    // result: ["Bill Murray", "Bill Clinton"]

indexOf and lastIndexOf by full string or regular expression also join and removeDuplicate and replaceInStrings

QStringList list;
    list << "alpha" << "beta" << "gamma" << "epsilon";
    list.replaceInStrings("a", "o");
    // list == ["olpho", "beto", "gommo", "epsilon"]
 QStringList list;
    list << "alpha" << "beta" << "gamma" << "epsilon";
    list.replaceInStrings(QRegularExpression("^a"), "o");
    // list == ["olpha", "beta", "gamma", "epsilon"]

and sort

void QStringList::sort(Qt::CaseSensitivity cs = Qt::CaseSensitive)

QStringRef 

The QStringRef class provides a thin wrapper around QString substrings.
and you can get it from QString by

leftRef(int n) const
midRef(int position, int n = -1)
rightRef(int n) const
splitRef(const QString &sep, Qt::SplitBehavior behavior = Qt::KeepEmptyParts, Qt::CaseSensitivity cs = Qt::CaseSensitive) const
QStringRef(const QString *string, int position, int length)

Chrono in C++

Chrono library is used to deal with date and time. This library was designed to deal with the fact that timers and clocks might be different on different systems and thus to improve over time in terms of precision. The unique thing about chrono is that it provides a precision-neutral concept by separating duration and point of time (“timepoint”) from specific clocks.

chrono is the name of a header and also of a sub-namespace: All the elements in this header (except for the common_type specializations) are not defined directly under the std namespace (like most of the standard library) but under the std::chrono namespace.
The elements in this header deal with time. This is done mainly by means of three concepts:

Duration

std::chrono::nanoseconds
std::chrono::microseconds

using namespace std::chrono;
using namespace std;
template <typename T>
void duration_int(duration<long long,T> d){
    qDebug()<<d.count();
}

template <typename T>
void duration_float(duration<float,T> d){
    qDebug()<<d.count();
}
int main(int argc, char *argv[])
{
    QCoreApplication app(argc, argv);
    duration_int(100ms);//T=std::milli == std::chrono::milliseconds
    duration_int(345us);//T=std::micro ==std::chrono::microseconds
    duration_int(5ns);//T=std::nano =std::chrono::nanoseconds
    duration_int(345s);//std::chrono::seconds
    duration_int(35h);//T=ratio<3600> =std::chrono::hours

    duration_float<std::ratio<60,10>>(6500s);//minutes*10 (6500/60)*10=1083.333

    return app.exec();
}
constexpr auto year = 31556952ll; // seconds in average Gregorian year
 
int main()
{
    using shakes = std::chrono::duration<int, std::ratio<1, 100000000>>;
    using jiffies = std::chrono::duration<int, std::centi>;
    using microfortnights = std::chrono::duration<float, std::ratio<14*24*60*60, 1000000>>;
    using nanocenturies = std::chrono::duration<float, std::ratio<100*year, 1000000000>>;
 
    std::chrono::seconds sec(1);
 
    std::cout << "1 second is:\n";
 
    // integer scale conversion with no precision loss: no cast
    std::cout << std::chrono::microseconds(sec).count() << " microseconds\n"
              << shakes(sec).count() << " shakes\n"
              << jiffies(sec).count() << " jiffies\n";
 
    // integer scale conversion with precision loss: requires a cast
    std::cout << std::chrono::duration_cast<std::chrono::minutes>(sec).count()
              << " minutes\n";
 
    // floating-point scale conversion: no cast
    std::cout << microfortnights(sec).count() << " microfortnights\n"
              << nanocenturies(sec).count() << " nanocenturies\n";
}

Clock

A clock consists of a starting point (or epoch) and a tick rate. For example, a clock may have an epoch of February 22, 1996 and tick every second. C++ defines three clock types:

  • system_clock-It is the current time according to the system (regular clock which we see on the toolbar of the computer). It is written as- std::chrono::system_clock
  • steady_clock-It is a monotonic clock that will never be adjusted.It goes at a uniform rate. It is written as- std::chrono::steady_clock
  • high_resolution_clock– It provides the smallest possible tick period. It is written as-std::chrono::high_resolution_clock
now[static]returns a std::chrono::time_point representing the current point in time
(for all three types)
to_time_t[static]converts a system clock time point to std::time_t
(system_clock)
from_time_t[static]converts std::time_t to a system clock time point
(system_clock)
#include <iostream> 
#include <chrono> 
#include <ctime> 
  
// Function to calculate 
// Fibonacci series 
long fibonacci(unsigned n) 
{ 
    if (n < 2) return n; 
    return fibonacci(n-1) + fibonacci(n-2); 
} 
  
int main() 
{ 
    // Using time point and system_clock 
    std::chrono::time_point<std::chrono::system_clock> start, end; 
  
    start = std::chrono::system_clock::now(); 
    std::cout << "f(42) = " << fibonacci(42) << '\n'; 
    end = std::chrono::system_clock::now(); 
  
    std::chrono::duration<double> elapsed_seconds = end - start; 
    std::time_t end_time = std::chrono::system_clock::to_time_t(end); 
  
    std::cout << "finished computation at " << std::ctime(&end_time) 
              << "elapsed time: " << elapsed_seconds.count() << "s\n";
}
auto start = std::chrono::high_resolution_clock::now();
...
auto elapsed = std::chrono::high_resolution_clock::now() - start;
long long microseconds = std::chrono::duration_cast<std::chrono::microseconds>(elapsed).count();
std::chrono::system_clock::time_point now = std::chrono::system_clock::now();
std::time_t t_c = std::chrono::system_clock::to_time_t(now - std::chrono::hours(24));
std::cout << "24 hours ago, the time was "
          << std::put_time(std::localtime(&t_c), "%F %T") << '\n';
 
std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
std::cout << "Hello World\n";
std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
std::cout << "Printing took "
          << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count()
          << "us.\n";

Permutation And Numeric Algorithms

Permutations

std::prev_permutation and std::next_permutation return the previous smaller or next bigger permutation of the newly ordered range. If a smaller or bigger permutation is not available, the algorithms return false. Both algorithms need bidirectional iterators. Per default the predefined sorting criterion std::less is used. If you use your sorting criterion, it has to obey the strict weak ordering. If not, the program is undefined.

std::vector<int> myInts{1, 2, 3};
do{
  for (auto i: myInts) std::cout << i;
  std::cout << " ";
} while(std::next_permutation(myInts.begin(), myInts.end())); 
                                    // 123 132 213 231 312 321 

std::reverse(myInts.begin(), myInts.end());
do{
  for (auto i: myInts) std::cout << i;
  std::cout << " ";
} while(std::prev_permutation(myInts.begin(), myInts.end()));
                                    // 321 312 231 213 132 123

Min and Max

You can determine the minimum, the maximum and the minimum and maximum pair of a range with the algorithms std::min_elementstd::max_element and std::minmax_element. Each algorithm can be configured with a binary predicate.

int toInt(const std::string& s){
  std::stringstream buff;
  buff.str("");
  buff << s;
  int value;
  buff >> value;
  return value;
}

std::vector<std::string> myStrings{"94", "5", "39", "-4", "-49", "1001", "-77",
                                   "23", "0", "84", "59", "96", "6", "-94"};
auto str= std::minmax_element(myStrings.begin(), myStrings.end());
std::cout << *str.first << ":" << *str.second;              // -4:96

auto asInt= std::minmax_element(myStrings.begin(), myStrings.end(),
            [](std::string a, std::string b){ return toInt(a) < toInt(b); });
std::cout << *asInt.first << ":" << *asInt.second;          // -94:1001

Numeric

std::accumulate without callable uses the following strategy

result = init;
result += *(first+0);
result += *(first+1);
...

std::adjacent_difference without callable uses the following strategy:

*(result) = *first;
*(result+1) = *(first+1) - *(first);
*(result+2) = *(first+2) - *(first+1);
...

std::partial_sum without callable uses the following strategy:

*(result) = *first;
*(result+1) = *first + *(first+1);
*(result+2) = *first + *(first+1) + *(first+2)
...
std::array<int, 9> arr{1, 2, 3, 4, 5, 6, 7, 8, 9};
std::cout << std::accumulate(arr.begin(), arr.end(), 0);               // 45
std::cout << std::accumulate(arr.begin(), arr.end(), 1,
                             [](int a, int b){ return a*b; } );        // 362880
							 
std::vector<int> vec{1, 2, 3, 4, 5, 6, 7, 8, 9};
std::vector<int> myVec;
std::adjacent_difference(vec.begin(), vec.end(),
                 std::back_inserter(myVec), [](int a, int b){ return a*b; });
for (auto v: myVec) std::cout << v << " ";            // 1 2 6 12 20 30 42 56 72
std::cout << std::inner_product(vec.begin(), vec.end(), arr.begin(), 0);  // 285

myVec= {};
std::partial_sum(vec.begin(), vec.end(), std::back_inserter(myVec));
for (auto v: myVec) std::cout << v << " ";            // 1 3 6 10 15 21 28 36 45

std::vector<int> myLongVec(10);
std::iota(myLongVec.begin(), myLongVec.end(), 2000);
for (auto v: myLongVec) std::cout << v << " ";    
                            // 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009

binary heap

binary heap is a heap data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority queues.[1]:162–163 The binary heap was introduced by J. W. J. Williams in 1964, as a data structure for heapsort.[2]

A binary heap is defined as a binary tree with two additional constraints:[3]

  • Shape property: a binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
  • Heap property: the key stored in each node is either greater than or equal to (≥) or less than or equal to (≤) the keys in the node’s children, according to some total order.

Heaps where the parent key is greater than or equal to (≥) the child keys are called max-heaps; those where it is less than or equal to (≤) are called min-heaps. Efficient (logarithmic time) algorithms are known for the two operations needed to implement a priority queue on a binary heap: inserting an element, and removing the smallest or largest element from a min-heap or max-heap, respectively. Binary heaps are also commonly employed in the heapsort sorting algorithm, which is an in-place algorithm because binary heaps can be implemented as an implicit data structure, storing keys in an array and using their relative positions within that array to represent child-parent relationships.

insert

  1. Add the element to the bottom level of the heap at the most left.
  2. Compare the added element with its parent; if they are in the correct order, stop.
  3. If not, swap the element with its parent and return to the previous step.
This image has an empty alt attribute; its file name is 2-18.pngThis image has an empty alt attribute; its file name is 3-10.pngThis image has an empty alt attribute; its file name is 4-4.png
Insert “15”

Remove

  1. Replace the root of the heap with the last element on the last level.
  2. Compare the new root with its children; if they are in the correct order, stop.
  3. If not, swap the element with one of its children and return to the previous step. (Swap with its smaller child in a min-heap and its larger child in a max-heap.)
This image has an empty alt attribute; its file name is 5-3.pngThis image has an empty alt attribute; its file name is 6-3.pngThis image has an empty alt attribute; its file name is 7-3.png
extract “11”

Heap in C++

You can create with std::make_heap a heap. You can push with std::push_heap new elements on the heap. On the contrary, you can pop the largest element with std::pop_heap from the heap. Both operations respect the heap characteristics. std::push_heap moves the last element of the range on the heap; std::pop_heap moves the biggest element of the heap to the last position in the range. You can check with std::is_heap if a range is a heap. You can determine with std::is_heap_until until which position the range is a heap. std::sort_heap sorts the heap.

std::vector<int> vec{4, 3, 2, 1, 5, 6, 7, 9, 10};
std::make_heap(vec.begin(), vec.end());
for (auto v: vec) std::cout << v << " ";                   // 10 9 7 4 5 6 2 3 1
std::cout << std::is_heap(vec.begin(), vec.end());         // true

vec.push_back(100);
std::cout << std::is_heap(vec.begin(), vec.end());         // false
std::cout << *std::is_heap_until(vec.begin(), vec.end());  // 100
for (auto v: vec) std::cout << v << " ";                   // 10 9 7 4 5 6 2 3 1 100

std::push_heap(vec.begin(), vec.end());
std::cout << std::is_heap(vec.begin(), vec.end());        // true
for (auto v: vec) std::cout << v << " ";                  // 100 10 7 4 9 6 2 3 1 5

std::pop_heap(vec.begin(), vec.end());
for (auto v: vec) std::cout << v << " ";                  // 10 9 7 4 5 6 2 3 1 100
std::cout << *std::is_heap_until(vec.begin(), vec.end()); // 100

vec.resize(vec.size()-1);
std::cout << std::is_heap(vec.begin(), vec.end());        // true
std::cout << vec.front() << std::endl;                    // 10

Sort, Binary Search, Merge Algorithms

Sort And Partial Sort

You can sort a range with std::sort or std::stable_sort or sort until a position with std::partial_sort. In addition std::partial_sort_copy copies the partially sorted range. With std::nth_element you can assign an element the sorted position in the range. You can check with std::is_sorted if a range is sorted. If you want to know until which position a range is sorted, use std::is_sorted_until.

std::string str{"RUdAjdDkaACsdfjwldXmnEiVSEZTiepfgOIkue"};
std::cout << std::is_sorted(str.begin(), str.end());        // false

std::partial_sort(str.begin(), str.begin()+30, str.end());
std::cout << str;           // AACDEEIORSTUVXZaddddeeffgiijjkwspnmluk

auto sortUntil= std::is_sorted_until(str.begin(), str.end());
std::cout << *sortUntil;                                   // s
for (auto charIt= str.begin(); charIt != sortUntil; ++charIt) 
    std::cout << *charIt;           // AACDEEIORSTUVXZaddddeeffgiijjkw

std::vector<int> vec{1, 0, 4, 3, 5};
auto vecIt= vec.begin();
while(vecIt != vec.end()){
  std::nth_element(vec.begin(), vecIt++, vec.end());
  std::cout << std::distance(vec.begin(), vecIt) << "-th ";
  for (auto v: vec) std::cout << v << "/";
}
// 1-th 01435/2-th 01435/3-th 10345/4-th 30145/5-th 10345
struct A{
    int v;
    bool operator<(const A& other){
        return this->v<other.v;
    }
};
int main(int argc, char *argv[])
{
    QCoreApplication a(argc,argv);
    QList<A> list{{8},{2},{3},{6},{5}};
    sort(list.begin(),list.end());
    for(const A& a:list){
        qDebug()<<a.v;
    }//2 3 5 6 8
    return a.exec();
}

Binary Search

Binary Search

The binary search algorithms use the fact that the ranges are already sorted. To search for an element, use std::binary_search. With std::lower_bound you get an iterator for the first element, being no smaller than the given value. With std::upper_bound you get an iterator back for the first element, which is bigger than the given value. std:::equal_range combines both algorithms.

binary_search : Searches the element val in the range
lower_bound : Returns the position of the first element of the range, being not smaller than val
upper_bound : Returns the position of the first element of the range, being bigger than val
equal_range  : Returns the pair std::lower_bound and std::upper_bound for the element val

bool isLessAbs(int a, int b){
  return abs(a) < abs(b);
}
vector<int> vec{-3, 0, -3, 2, -3, 5, -3, 7, -0, 6, -3, 5, 
                -6, 8, 9, 0, 8, 7, -7, 8, 9, -6, 3, -3, 2};

sort(vec.begin(), vec.end(), isLessAbs);
for (auto v: vec) cout << v << " "; 
     // 0 0 0 2 2 -3 -3 -3 -3 -3 3 -3 5 5 -6 -6 6 7 -7 7 8 8 8 9 9
cout << binary_search(vec.begin(), vec.end(), -5, isLessAbs); // true
cout << binary_search(vec.begin(), vec.end(), 5, isLessAbs);  // true

auto pair= equal_range(vec.begin(), vec.end(), 3, isLessAbs);
cout << distance(vec.begin(), pair.first);                    // 5
cout << distance(vec.begin(), pair.second)-1;                 // 11

for (auto threeIt= pair.first;threeIt != pair.second; ++threeIt) 
     cout << *threeIt << " ";              // -3 -3 -3 -3 -3 3 -3

Merge Operation

Merge operations empower you to merge sorted ranges in a new sorted range. The algorithm requires that the ranges and the algorithm use the same sorting criterion. If not, the program is undefined. Per default the predefined sorting criterion std::less is used. If you use your sorting criterion, it has to obey the strict weak ordering. If not, the program is undefined.

You can merge two sorted ranges with std::inplace_merge and std::merge. You can check with std::includes if one sorted range is in another sorted range. You can merge with std::set_differencestd::set_intersectionstd::set_symmetric_difference and std::set_union two sorted ranges in a new sorted range.

inplace_merge : Merges in place two sorted sub ranges [first, mid) and [mid, last)
merge : Merges two sorted ranges and copies the result to result
includes: Checks if all elements of the second range are in the first range
set_difference : Copies these elements of the first range to result, being not in the second range
set_intersection : Determines the intersection of the first with the second range and copies the result to result
set_symmetric_difference :  Determines the symmetric difference of the first with the second range and copies the result to result
set_union : Determines the union of the first with the second range and copies the result to result

std::vector<int> vec1{1, 1, 4, 3, 5, 8, 6, 7, 9, 2};
std::vector<int> vec2{1, 2, 3};

std::sort(vec1.begin(), vec1.end());
std::vector<int> vec(vec1);

vec1.reserve(vec1.size() + vec2.size());
vec1.insert(vec1.end(), vec2.begin(), vec2.end());
for (auto v: vec1) std::cout << v << " ";       // 1 1 2 3 4 5 6 7 8 9 1 2 3

std::inplace_merge(vec1.begin(), vec1.end()-vec2.size(), vec1.end());
for (auto v: vec1) std::cout << v << " ";       //  1 1 1 2 2 3 3 4 5 6 7 8 9

vec2.push_back(10);
for (auto v: vec) std::cout << v << " ";        // 1 1 2 3 4 5 6 7 8 9
for (auto v: vec2) std::cout << v << " ";       // 1 2 3 10

std::vector<int> res;
std::set_symmetric_difference(vec.begin(), vec.end(), vec2.begin(), vec2.end(), 
                              std::back_inserter(res));
for (auto v : res) std::cout << v << " ";       // 1 4 5 6 7 8 9 10

res= {};
std::set_union(vec.begin(), vec.end(), vec2.begin(), vec2.end(),
std::back_inserter(res));
for (auto v : res) std::cout << v << " ";       // 1 1 2 3 4 5 6 7 8 9 10

Modifying Algorithms

Copy Elements and Ranges

You can copy ranges forward with std::copy, backward with std::copy_backward and conditionally with std::copy_if. If you want to copy n elements, you can use std::copy_n.

std::vector<int> myVec{0, 1, 2, 3, 4, 5, 6, 7, 9};
std::vector<int> myVec2(10);

std::copy_if(myVec.begin(), myVec.end(), myVec2.begin()+3,
             [](int a){ return a%2; });
			 
for (auto v: myVec2) std::cout << v << " ";    // 0 0 0 1 3 5 7 9 00

std::string str{"abcdefghijklmnop"};
std::string str2{"---------------------"};

std::cout << str2;                             // ---------------------
std::copy_backward(str.begin(), str.end(), str2.end());
std::cout << str2;                             // -----abcdefghijklmnop
std::cout << str;                              // abcdefghijklmnop

std::copy_backward(str.begin(), str.begin() + 5, str.end());
std::cout << str;                              // abcdefghijkabcde

Replace Elements and Ranges

You have with std::replacestd::replace_ifstd::replace_copy and std::replace_copy_if four variations to replace elements in a range. The algorithms differ in two aspects. First, does the algorithm need a predicate? Second, does the algorithm copy the elements in the destination range?

std::string str{"Only for testing purpose."};
std::replace(str.begin(), str.end(), ' ', '1');
std::cout << str; // Only1for1testing1purpose.

std::replace_if(str.begin(), str.end(), [](char c){ return c == '1'; }, '2'); 
std::cout << str; // Only2for2testing2purpose.

std::string str2;
std::replace_copy(str.begin(), str.end(), std::back_inserter(str2), '2', '3');
std::cout << str2; // Only3for3testing3purpose.

std::string str3;
std::replace_copy_if(str2.begin(), str2.end(),
std::back_inserter(str3), [](char c){ return c == '3'; }, '4');
std::cout << str3; // Only4for4testing4purpose.

Remove Elements and Ranges

The four variations std::remove, std::remove_if, std::remove_copy and std::remove_copy_if support two kinds of operations. On one hand, remove elements with and without a predicate from a range. On the other hand, copy the result of your modification to a new range.

std::vector<int> myVec{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
auto newIt= std::remove_if(myVec.begin(), myVec.end(), 
                          [](int a){ return a%2; });
for (auto v: myVec) std::cout << v << " ";   // 0 2 4 6 8 5 6 7 8 9
myVec.erase(newIt, myVec.end());
for (auto v: myVec) std::cout << v << " ";   // 0 2 4 6 8
std::string str{"Only for Testing Purpose."};
str.erase( std::remove_if(str.begin(), str.end(),
          [](char c){ return std::isupper(c); }, str.end() ) );
std::cout << str << std::endl;               // nly for esting urpose.

Fill and Create Ranges

You can fill a range with std::fill and std::fill_n; you can generate new elements with std::generate and std::generate_n.

int getNext(){
  static int next{0};
  return ++next;
}

std::vector<int> vec(10);
std::fill(vec.begin(), vec.end(), 2011);
for (auto v: vec) std::cout << v << " ";
                      // 2011 2011 2011 2011 2011 2011 2011 2011 2011 2011
					
std::generate_n(vec.begin(), 5, getNext);
for (auto v: vec) std::cout << v << " ";
                      // 1 2 3 4 5 2011 2011 2011 2011 2011

Move Ranges

std::move moves the ranges forward; std::move_backward moves the ranges backwards.

std::vector<int> myVec{0, 1, 2, 3, 4, 5, 6, 7, 9};
std::vector<int> myVec2(myVec.size());
std::move(myVec.begin(), myVec.end(), myVec2.begin());
for (auto v: myVec2) std::cout << v << " ";    // 0 1 2 3 4 5 6 7 9 0

std::string str{"abcdefghijklmnop"};
std::string str2{"---------------------"};
std::move_backward(str.begin(), str.end(), str2.end());
std::cout << str2;                             // -----abcdefghijklmnop

Swap Ranges

std::swap and std::swap_ranges can swap objects and ranges.

std::vector<int> myVec{0, 1, 2, 3, 4, 5, 6, 7, 9};
std::vector<int> myVec2(9);
std::swap(myVec, myVec2);
for (auto v: myVec) std::cout << v << " ";    // 0 0 0 0 0 0 0 0 0
for (auto v: myVec2) std::cout << v << " ";   // 0 1 2 3 4 5 6 7 9

std::string str{"abcdefghijklmnop"};
std::string str2{"---------------------"};
std::swap_ranges(str.begin(), str.begin()+5, str2.begin()+5);
std::cout << str << std::endl;                // -----fghijklmnop
std::cout << str2 << std::endl;               // -----abcde-----------

Transform Ranges

The std::transform algorithm applies a unary or binary callable to a range and copies the modified elements to the destination range.

std::string str{"abcdefghijklmnopqrstuvwxyz"};
std::transform(str.begin(), str.end(), str.begin(),
               [](char c){ return std::toupper(c); });
std::cout << str;         // ABCDEFGHIJKLMNOPQRSTUVWXYZ

std::vector<std::string> vecStr{"Only", "for", "testing", "purpose", "."};
std::vector<std::string> vecStr2(5, "-");
std::vector<std::string> vecRes;
std::transform(vecStr.begin(), vecStr.end(), 
               vecStr2.begin(), std::back_inserter(vecRes),
               [](std::string a, std::string b){ return std::string(b)+a+b; });
for (auto str: vecRes) std::cout << str << " ";  
                           // -Only- -for- -testing- -purpose- -.-

Reverse Ranges

std::reverse and std::reverse_copy invert the order of the elements in their range.

std::string str{"123456789"};
std::reverse(str.begin(), str.begin()+5);
std::cout << str;           // 543216789

Randomly Shuffle Ranges

You can randomly shuffle ranges with std::random_shuffle and std::shuffle.

using std::chrono::system_clock;
using std::default_random_engine;
std::vector<int> vec1{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
std::vector<int> vec2(vec1);

std::random_shuffle(vec1.begin(), vec1.end());
for (auto v: vec1) std::cout << v << " ";     // 4 3 7 8 0 5 2 1 6 9

unsigned seed= system_clock::now().time_since_epoch().count();
std::shuffle(vec2.begin(), vec2.end(), default_random_engine(seed));
for (auto v: vec2) std::cout << v << " ";     // 4 0 2 3 9 6 5 1 8 7

Remove Duplicates

With the algorithms std::unique and std::unique_copy you have more opportunities to remove adjacent duplicates. This can be done with and without a binary predicate.

std::vector<int> myVec{0, 0, 1, 1, 2, 2, 3, 4, 4, 5, 
                       3, 6, 7, 8, 1, 3, 3, 8, 8, 9};

myVec.erase(std::unique(myVec.begin(), myVec.end()), myVec.end());
for (auto v: myVec) std::cout << v << " ";     // 0 1 2 3 4 5 3 6 7 8 1 3 8 9 

std::vector<int> myVec2{1, 4, 3, 3, 3, 5, 7, 9, 2, 4, 1, 6, 8, 
                        0, 3, 5, 7, 8, 7, 3, 9, 2, 4, 2, 5, 7, 3};
std::vector<int> resVec;
resVec.reserve(myVec2.size());
std::unique_copy(myVec2.begin(), myVec2.end(), std::back_inserter(resVec),
                 [](int a, int b){ return (a%2) == (b%2); } );
for(auto v: myVec2) std::cout << v << " "; 
                      // 1 4 3 3 3 5 7 9 2 4 1 6 8 0 3 5 7 8 7 3 9 2 4 2 5 7 3
for(auto v: resVec) std::cout << v << " ";       // 1 4 3 2 1 6 3 8 7 2 5

Partition

std::partition and std::stable_partition partition a range and returns the partition point. With std::partition_point you can get the partition point of a partition. Afterwards you can check the partition with std::is_partitioned or copy it with std::partition_copy.

bool isOdd(int i){ return (i%2) == 1; }
vector<int> vec{1, 4, 3, 4, 5, 6, 7, 3, 4, 5, 6, 0, 4, 
                8, 4, 6, 6, 5, 8, 8, 3, 9, 3, 7, 6, 4, 8};

auto parPoint= partition(vec.begin(), vec.end(), isOdd);
for (auto v: vec) cout << v << " ";
                    // 1 7 3 3 5 9 7 3 3 5 5 0 4 8 4 6 6 6 8 8 4 6 4 4 6 4 8
					
for (auto v= vec.begin(); v != parPoint; ++v) cout << *v << " ";
                    // 1 7 3 3 5 9 7 3 3 5 5
for (auto v= parPoint; v != vec.end(); ++v) cout << *v << " ";
                    // 4 8 4 6 6 6 8 8 4 6 4 4 6 4 8
					
cout << is_partitioned(vec.begin(), vec.end(), isOdd);     // true
list<int> le;
list<int> ri;
partition_copy(vec.begin(), vec.end(), back_inserter(le), back_inserter(ri),
               [](int i) { return i < 5; });
for (auto v: le) cout << v << " ";    // 1 3 3 3 3 0 4 4 4 4 4 4
for (auto v: ri) cout << v << " ";    // 7 5 9 7 5 5 8 6 6 6 8 8 6 6 8