cp-library

競技プログラミング用 C++ ライブラリ

View the Project on GitHub qandori/cp-library

:heavy_check_mark: 非負整数の一括出力

components/fast_io_output.hpp · GitHub で見る

共通ページ

uint32_t の整数を、決まった個数ずつまとめて出力します。Fast I/O の FastOutput を使い、Mac を含むすべての対応環境で利用できます。入力処理も必要なら 一括入出力 を include すると、この部品も読み込まれます。

#include "lib/components/fast_io_output.hpp"
#include <array>
#include <cstddef>
#include <cstdint>

int main() {
	const std::array<std::uint32_t, 2> rows[] = {
		{0, 7}, {12, 34}, {4294967295u, 0}
	};
	FastOutput out;
	write_unsigned_records<2>(out, 3, [&](std::size_t i) {
		return rows[i];
	});
	return out.flush() ? 0 : 1;
}

出力は次のとおりです。

0 7
12 34
4294967295 0
操作 内容・返り値 計算量
write_unsigned_records<Fields>(out,count,read) FastOutput& out へ、read(i) が返す Fields 個の整数を size_t count 組出力する。返り値は void \(O(L)\) ＋コールバックの処理時間

引数の順序は出力先・組数・コールバックです。既定引数はありません。Fields はコンパイル時の定数で、1 <= Fields <= numeric_limits<size_t>::max()/11 とします。

read(i) は i=0,1,...,count-1 の順に 1 回ずつ呼ばれます。std::array<uint32_t, Fields> や span など、添字 0 以上 Fields 未満を参照できる値を返してください。各要素は uint32_t に変換でき、値が 0 以上 4294967295 以下であることを前提とします。参照するデータは、その組の出力が終わるまで有効にしてください。

各組を十進整数の空白区切りで出力し、組の末尾に改行を付けます。値の順序と重複はそのまま保ちます。count=0 は何も出力せず、read も呼びません。read 内から同じ out を使わないでください。

通常の out.write・out.println と混在できます。出力はバッファに残る場合があるため、最後に out.flush() を呼ぶか、out を破棄します。バッファを空ける処理で書き込みに失敗すると std::runtime_error を送出します。最後の flush() は成功時に true を返します。同じ FastOutput を複数スレッドから同時に使わないでください。

出力文字数を \(L\) として時間は \(O(L)\)、追加空間は一組の戻り値と出力バッファを含めて \(O(\mathrm{Fields})\) です。コールバック自身の処理時間・空間は別途必要です。

依存ライブラリ

検証コード

コード

#ifndef FAST_IO_OUTPUT_HPP
#define FAST_IO_OUTPUT_HPP

#include "fast_io.hpp"
#include <limits>
#include <utility>

namespace fast_io_detail {
struct BulkOutput {
	static char *small(char *out, std::uint32_t value) {
		unsigned n = 1 + (value >= 10) + (value >= 100) + (value >= 1000);
		if constexpr (std::endian::native == std::endian::little) {
			std::uint32_t word;
			std::memcpy(&word, FastOutput::quads[value].data(), 4);
			word >>= (4 - n) * 8;
			std::memcpy(out, &word, 4);
		} else std::memcpy(out, FastOutput::quads[value].data() + 4 - n, n);
		return out + n;
	}
	static char *number(char *out, std::uint32_t value) {
		if (value >= 100000000) {
			out = small(out, value / 100000000);
			value %= 100000000;
			std::memcpy(out, FastOutput::quads[value / 10000].data(), 4);
			std::memcpy(out + 4, FastOutput::quads[value % 10000].data(), 4);
			return out + 8;
		}
		if (value >= 10000) {
			out = small(out, value / 10000);
			std::memcpy(out, FastOutput::quads[value % 10000].data(), 4);
			return out + 4;
		}
		return small(out, value);
	}
	template<std::size_t Fields, class Read>
#if defined(__GNUC__) || defined(__clang__)
	[[gnu::noinline]]
#endif
	static void records(FastOutput &out, std::size_t count, Read read) {
		constexpr auto bytes = 11 * Fields;
		constexpr auto block = std::max<std::size_t>(1, (1 << 16) / bytes);
		for (std::size_t base = 0; base < count;) {
			const auto n = std::min(count - base, block);
			char *begin = out.reserve(n * bytes), *p = begin;
			for (std::size_t i = 0; i < n; ++i) {
				auto values = read(base + i);
				for (std::size_t j = 0; j < Fields; ++j) {
					p = number(p, std::uint32_t(values[j]));
					*p++ = j + 1 == Fields ? '\n' : ' ';
				}
			}
			out.length += p - begin;
			base += n;
		}
	}
	static void write(FastOutput &out, std::string_view text) {
		if (text.size() <= (1 << 16)) return out.write(text);
		if (out.length && !out.flush()) throw std::runtime_error("output failed");
		std::size_t done = 0;
		while (done < text.size()) {
			const auto written = std::fwrite(text.data() + done, 1, text.size() - done, out.file);
			if (!written) throw std::runtime_error("output failed");
			done += written;
		}
	}
};

}

template<std::size_t Fields, class Read>
void write_unsigned_records(FastOutput &output, std::size_t count, Read read) {
	static_assert(Fields > 0 && Fields <= std::numeric_limits<std::size_t>::max() / 11);
	fast_io_detail::BulkOutput::records<Fields>(output, count, std::move(read));
}

#endif
Back to top page