Fast Input and Output: Why Contest Code Starts the Same Way

Kenji's program reads a million numbers and prints each one back. It is correct, yet on the judge it gets Time Limit Exceeded. Kenji, who optimises early, starts rewriting his loop. The loop is fine. The time goes into reading and printing, and two lines at the top of main fix it. This lesson measures how much.

A buffer, a sync and a tie

A buffer is a block of memory where characters wait. The program collects output there and hands it to the operating system in big batches, not one character at a time. Handing the waiting characters over is called a flush. Input works the same way: a big batch comes in, and reads take from it.

By default, C++ makes two promises that cost time. The first is the sync: std::cin and std::cout stay in step with C's stdin and stdout. Every character goes through C's input and output functions, so printf and std::cout can take turns safely. You pay for that safety on every character, even if you never call printf.

The second is the tie: std::cin is tied to std::cout, so std::cout is flushed before every read. At a keyboard, that makes a question like "Enter n:" appear before the program waits. A judge reads no questions.

std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);

#include <iostream>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int price = 0;
    int count = 0;

    std::cin >> price >> count;
    std::cout << price * count << '\n';
    return 0;
}

100

So the first line gives C++ streams their own buffers, and the second stops the flush before every read.

std::endl is '\n' plus a flush

std::endl sends a newline and then flushes std::cout. '\n' only sends the newline. The characters that come out are the same.

#include <iostream>

int main()
{
    std::cout << "first line" << std::endl;
    std::cout << "second line" << '\n';
    return 0;
}

first line
second line

You cannot see the flush in the output, only in the time. A flush is a trip to the operating system, and a trip per line adds up. std::endl is the right tool when a line must leave now. One case is an interactive judge waiting for your question. Another is a line you must see even if the program crashes a moment later. So the output is identical; std::endl only changes when it leaves.

Measured: a million numbers in and out Intermediate

Four programs read n = 1,000,000 and then a million integers, and print each one back on its own line. They differ only in the two lines and the line ending. Here is the fastest, with the timer around the work.

#include <chrono>
#include <cstdio>
#include <iostream>

int main()
{
    std::freopen("out.txt", "w", stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n = 0;

    auto start = std::chrono::steady_clock::now();
    std::cin >> n;
    for (int i = 0; i < n; i++) {
        int x = 0;
        std::cin >> x;
        std::cout << x << '\n';
    }
    std::cout.flush();
    auto stop = std::chrono::steady_clock::now();

    long long ms = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start).count();
    std::FILE* f = std::fopen("out.txt", "r");
    std::fseek(f, 0, SEEK_END);
    std::cerr << n << " numbers, " << std::ftell(f) << " bytes written, " << ms << " ms\n";
    return 0;
}

Three details need a word. Compiler Explorer stops a program after 32 KB of output, so std::freopen sends stdout into a file, out.txt, before the streams start. The std::chrono lines read a clock before and after the loop; auto lets the compiler write the long type, and lesson 04 explains it. The last lines measure the file and print the result to stderr, the error stream.

The other three programs remove the two lines, or change '\n' to std::endl, or both. Each was run once on Compiler Explorer, x86-64 GCC 12.2, with the runner's command line, g++ -O2 -std=c++17. The input held a million integers from 0 to 99, ten per line, 2,893,323 bytes in all. Every program wrote the same 2,893,315 bytes.

D, with both changes, took 58 ms against A's 750 ms, about 13 times faster. The middle two show why you need both. In C, the lines are in, but std::endl flushes once per line: a million trips to the operating system. In B, the line ending is '\n', but the tie still flushes std::cout before every read, and the program reads once per line.

Five more runs of each split the two lines apart, on the same site and input. The sync line alone, with '\n', took 433 to 2,158 ms, because the tie still flushes before every read. The tie line alone took 128 to 193 ms: no flush per read, but every character still goes through C's functions. Only with all three changes do reads and writes both work in big batches.

These runs share a busy machine, and the Playground's runner is another one. Re-runs moved A, B and C by hundreds of milliseconds, even swapping their order, while D stayed at 58 to 66 ms. Trust D's lead, not the exact milliseconds. So the two lines and '\n' belong together. Drop any one of the three, and the program ran at least twice as slow, in most runs over seven times.

Reading until the input ends: while (std::cin >> x)

Many inputs never say how many values are coming. You read until the input runs out. std::cin >> x gives back std::cin itself, which is how the chains of lesson 01 work. A stream used as a condition is true while its last read succeeded.

So while (std::cin >> x) reads a value, tests whether the read worked, and runs the body only for a value that really arrived. A read fails at the end of the input, or at something that is not a number. Then the loop ends. Zara counts the days below zero in her temperature log.

#include <iostream>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int x = 0;
    int below = 0;

    while (std::cin >> x) {
        if (x < 0) {
            below++;
        }
    }
    std::cout << "days below zero: " << below << '\n';
    return 0;
}

days below zero: 2

At a keyboard you end the input yourself: Ctrl+D on Linux and macOS, or Ctrl+Z and then Enter on Windows. On the Playground, the input ends where the text in the input box ends. So the loop runs once per number that arrived, and the read that fails is the one that ends it.

Whole lines: std::getline and the leftover newline

>> stops at every space, so it cannot read a book title. std::getline(std::cin, line) reads every character up to the next newline into a std::string, spaces included. It throws the newline itself away. An empty line gives an empty string.

Like >>, it gives back the stream, so while (std::getline(std::cin, line)) reads line by line until the input ends. Now the trap. Maria's library input has a count on the first line and a title on the next.

#include <iostream>
#include <string>

int main()
{
    int copies = 0;
    std::string title;

    std::cin >> copies;
    std::getline(std::cin, title);
    std::cout << "copies: " << copies << '\n';
    std::cout << "title: [" << title << "]\n";
    return 0;
}

copies: 3
title: []

That output is for the input 3 and The Little Prince on two lines. The title is empty. >> stopped right after the 3 and left the newline of that line in the stream. std::getline then read up to that newline: an empty line, which was the rest of the first one.

The fix is to finish the number's line before you read the next line. One more std::getline into a string you never use does it, and it also eats any spaces after the number.

#include <iostream>
#include <string>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n = 0;
    std::string rest;
    std::string title;

    std::cin >> n;
    std::getline(std::cin, rest);
    for (int i = 1; i <= n; i++) {
        std::getline(std::cin, title);
        std::cout << i << ". " << title << " (" << title.size() << " characters)\n";
    }
    return 0;
}

1. The Little Prince (17 characters)
2. Matilda (7 characters)
3. Treasure Island (15 characters)

So after >> reads the last number on a line, one std::getline finishes that line, and the next one reads a real line.

Walking a line one character at a time

A std::string can be read like a C array of char. line.size() is how many characters it holds, and line[i] is the character at index i, from 0. That is enough to find the words in a line, the way you would in C.

Here a word is a run of characters that are not spaces. A word starts at index i when line[i] is not a space, and either i is 0 or line[i - 1] is a space. That test ignores runs of two or more spaces, and spaces at the start or the end.

#include <iostream>
#include <string>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::string line;

    while (std::getline(std::cin, line)) {
        std::string initials;
        for (int i = 0; i < (int)line.size(); i++) {
            bool starts = line[i] != ' ' && (i == 0 || line[i - 1] == ' ');
            if (starts) {
                initials += line[i];
            }
        }
        std::cout << initials << '\n';
    }
    return 0;
}

tlotr
atwied

atotc

So a line is an array of characters you can walk, and a word starts where a non-space follows a space or the start.

printf and std::cout after the sync is off

Bob keeps writing scanf and printf, and sometimes he adds the two lines out of habit. With the sync off, each family keeps its own buffer, and nobody keeps them in order.

#include <cstdio>
#include <iostream>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::printf("1. printf\n");
    std::cout << "2. cout\n";
    std::printf("3. printf\n");
    std::cout << "4. cout\n";
    return 0;
}

Here is what two systems printed. Neither is the order in the code.

Each buffer is emptied when the program ends, and which one goes first depends on the library underneath. So the same program can look right on your machine and come out scrambled on the judge. The rule is one family per program. If you want scanf and printf, use them everywhere and leave the two lines out; they are fast already. So once the sync is off, the order of mixed output is not yours to choose.

Numbers inside a string: a pointer at std::istringstream

Sometimes the numbers you want are already inside a std::string, such as one line from std::getline. std::istringstream, from the header <sstream>, is a stream that reads from a string instead of from stdin. >> works on it exactly as on std::cin.

#include <iostream>
#include <sstream>
#include <string>

int main()
{
    std::string prices = "12 7 30";
    std::istringstream in(prices);
    int x = 0;

    while (in >> x) {
        std::cout << "price " << x << '\n';
    }
    return 0;
}

price 12
price 7
price 30

Module 3 teaches string streams properly. For now: any >> loop you can write for std::cin also works on a string.

while (!std::cin.eof()) {
    std::cin >> x;
    if (x < 0) {
        below++;
    }
}

for (int i = 0; i < n; i++) {
    std::cin >> x;
    std::cout << x << std::endl;
}

std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> a;
std::scanf("%d", &b);

#include <iostream>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int total = 0;
    int players = 0;

    std::cin >> total >> players;
    std::cout << "total score: " << total << '\n';
    std::cout << "per player: " << total / players << '\n';
    return 0;
}

#include <iostream>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    // Read integers until the input ends. Print their sum and how many
    // there were, on one line, separated by one space.

    return 0;
}

#include <iostream>
#include <string>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::string line;
    int lines = 0;
    int words = 0;

    // Read the input line by line with std::getline until it ends.
    // Count every line, and every word inside every line.

    std::cout << lines << ' ' << words << '\n';
    return 0;
}

#include <iostream>
#include <string>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n = 0;
    std::cin >> n;

    // Read the n lines of text that follow with std::getline.
    // For every word, print the number of its line (1 to n),
    // one space and the word, one word per output line.

    return 0;
}

#include <iostream>
#include <sstream>
#include <string>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    // Read the input line by line until it ends. Print the total of each
    // line on its own line, then one last line: the word total, one
    // space, and the total of every number in the input.

    return 0;
}

Next, Maria's swap with pointers becomes a swap with no stars at all, and lesson 03 explains the & that now means something new.