Thanks for using Compiler Explorer
Sponsors
Jakt
C++
Ada
Analysis
Android Java
Android Kotlin
Assembly
C
C3
Carbon
C++ (Circle)
CIRCT
Clean
CMake
CMakeScript
COBOL
C++ for OpenCL
MLIR
Cppx
Cppx-Blue
Cppx-Gold
Cpp2-cppfront
Crystal
C#
CUDA C++
D
Dart
Elixir
Erlang
Fortran
F#
Go
Haskell
HLSL
Hook
Hylo
ispc
Java
Julia
Kotlin
LLVM IR
LLVM MIR
Modula-2
Nim
Objective-C
Objective-C++
OCaml
OpenCL C
Pascal
Pony
Python
Racket
Ruby
Rust
Snowball
Scala
Solidity
Spice
Swift
LLVM TableGen
Toit
TypeScript Native
V
Vala
Visual Basic
Zig
Javascript
GIMPLE
c++ source #1
Output
Compile to binary object
Link to binary
Execute the code
Intel asm syntax
Demangle identifiers
Verbose demangling
Filters
Unused labels
Library functions
Directives
Comments
Horizontal whitespace
Debug intrinsics
Compiler
6502-c++ 11.1.0
ARM GCC 10.2.0
ARM GCC 10.3.0
ARM GCC 10.4.0
ARM GCC 10.5.0
ARM GCC 11.1.0
ARM GCC 11.2.0
ARM GCC 11.3.0
ARM GCC 11.4.0
ARM GCC 12.1.0
ARM GCC 12.2.0
ARM GCC 12.3.0
ARM GCC 13.1.0
ARM GCC 13.2.0
ARM GCC 13.2.0 (unknown-eabi)
ARM GCC 14.1.0
ARM GCC 4.5.4
ARM GCC 4.6.4
ARM GCC 5.4
ARM GCC 6.3.0
ARM GCC 6.4.0
ARM GCC 7.3.0
ARM GCC 7.5.0
ARM GCC 8.2.0
ARM GCC 8.5.0
ARM GCC 9.3.0
ARM GCC 9.4.0
ARM GCC 9.5.0
ARM GCC trunk
ARM gcc 10.2.1 (none)
ARM gcc 10.3.1 (2021.07 none)
ARM gcc 10.3.1 (2021.10 none)
ARM gcc 11.2.1 (none)
ARM gcc 5.4.1 (none)
ARM gcc 7.2.1 (none)
ARM gcc 8.2 (WinCE)
ARM gcc 8.3.1 (none)
ARM gcc 9.2.1 (none)
ARM msvc v19.0 (WINE)
ARM msvc v19.10 (WINE)
ARM msvc v19.14 (WINE)
ARM64 Morello gcc 10.1 Alpha 2
ARM64 gcc 10.2
ARM64 gcc 10.3
ARM64 gcc 10.4
ARM64 gcc 10.5.0
ARM64 gcc 11.1
ARM64 gcc 11.2
ARM64 gcc 11.3
ARM64 gcc 11.4.0
ARM64 gcc 12.1
ARM64 gcc 12.2.0
ARM64 gcc 12.3.0
ARM64 gcc 13.1.0
ARM64 gcc 13.2.0
ARM64 gcc 14.1.0
ARM64 gcc 4.9.4
ARM64 gcc 5.4
ARM64 gcc 5.5.0
ARM64 gcc 6.3
ARM64 gcc 6.4
ARM64 gcc 7.3
ARM64 gcc 7.5
ARM64 gcc 8.2
ARM64 gcc 8.5
ARM64 gcc 9.3
ARM64 gcc 9.4
ARM64 gcc 9.5
ARM64 gcc trunk
ARM64 msvc v19.14 (WINE)
AVR gcc 10.3.0
AVR gcc 11.1.0
AVR gcc 12.1.0
AVR gcc 12.2.0
AVR gcc 12.3.0
AVR gcc 13.1.0
AVR gcc 13.2.0
AVR gcc 14.1.0
AVR gcc 4.5.4
AVR gcc 4.6.4
AVR gcc 5.4.0
AVR gcc 9.2.0
AVR gcc 9.3.0
Arduino Mega (1.8.9)
Arduino Uno (1.8.9)
BPF clang (trunk)
BPF clang 13.0.0
BPF clang 14.0.0
BPF clang 15.0.0
BPF clang 16.0.0
BPF clang 17.0.1
BPF clang 18.1.0
BPF gcc 13.1.0
BPF gcc 13.2.0
BPF gcc trunk
EDG (experimental reflection)
EDG 6.5
EDG 6.5 (GNU mode gcc 13)
EDG 6.6
EDG 6.6 (GNU mode gcc 13)
FRC 2019
FRC 2020
FRC 2023
KVX ACB 4.1.0 (GCC 7.5.0)
KVX ACB 4.1.0-cd1 (GCC 7.5.0)
KVX ACB 4.10.0 (GCC 10.3.1)
KVX ACB 4.11.1 (GCC 10.3.1)
KVX ACB 4.12.0 (GCC 11.3.0)
KVX ACB 4.2.0 (GCC 7.5.0)
KVX ACB 4.3.0 (GCC 7.5.0)
KVX ACB 4.4.0 (GCC 7.5.0)
KVX ACB 4.6.0 (GCC 9.4.1)
KVX ACB 4.8.0 (GCC 9.4.1)
KVX ACB 4.9.0 (GCC 9.4.1)
KVX ACB 5.0.0 (GCC 12.2.1)
M68K gcc 13.1.0
M68K gcc 13.2.0
M68K gcc 14.1.0
M68k clang (trunk)
MRISC32 gcc (trunk)
MSP430 gcc 4.5.3
MSP430 gcc 5.3.0
MSP430 gcc 6.2.1
MinGW clang 14.0.3
MinGW clang 14.0.6
MinGW clang 15.0.7
MinGW clang 16.0.0
MinGW clang 16.0.2
MinGW gcc 11.3.0
MinGW gcc 12.1.0
MinGW gcc 12.2.0
MinGW gcc 13.1.0
RISC-V (32-bits) gcc (trunk)
RISC-V (32-bits) gcc 10.2.0
RISC-V (32-bits) gcc 10.3.0
RISC-V (32-bits) gcc 11.2.0
RISC-V (32-bits) gcc 11.3.0
RISC-V (32-bits) gcc 11.4.0
RISC-V (32-bits) gcc 12.1.0
RISC-V (32-bits) gcc 12.2.0
RISC-V (32-bits) gcc 12.3.0
RISC-V (32-bits) gcc 13.1.0
RISC-V (32-bits) gcc 13.2.0
RISC-V (32-bits) gcc 14.1.0
RISC-V (32-bits) gcc 8.2.0
RISC-V (32-bits) gcc 8.5.0
RISC-V (32-bits) gcc 9.4.0
RISC-V (64-bits) gcc (trunk)
RISC-V (64-bits) gcc 10.2.0
RISC-V (64-bits) gcc 10.3.0
RISC-V (64-bits) gcc 11.2.0
RISC-V (64-bits) gcc 11.3.0
RISC-V (64-bits) gcc 11.4.0
RISC-V (64-bits) gcc 12.1.0
RISC-V (64-bits) gcc 12.2.0
RISC-V (64-bits) gcc 12.3.0
RISC-V (64-bits) gcc 13.1.0
RISC-V (64-bits) gcc 13.2.0
RISC-V (64-bits) gcc 14.1.0
RISC-V (64-bits) gcc 8.2.0
RISC-V (64-bits) gcc 8.5.0
RISC-V (64-bits) gcc 9.4.0
RISC-V rv32gc clang (trunk)
RISC-V rv32gc clang 10.0.0
RISC-V rv32gc clang 10.0.1
RISC-V rv32gc clang 11.0.0
RISC-V rv32gc clang 11.0.1
RISC-V rv32gc clang 12.0.0
RISC-V rv32gc clang 12.0.1
RISC-V rv32gc clang 13.0.0
RISC-V rv32gc clang 13.0.1
RISC-V rv32gc clang 14.0.0
RISC-V rv32gc clang 15.0.0
RISC-V rv32gc clang 16.0.0
RISC-V rv32gc clang 17.0.1
RISC-V rv32gc clang 18.1.0
RISC-V rv32gc clang 9.0.0
RISC-V rv32gc clang 9.0.1
RISC-V rv64gc clang (trunk)
RISC-V rv64gc clang 10.0.0
RISC-V rv64gc clang 10.0.1
RISC-V rv64gc clang 11.0.0
RISC-V rv64gc clang 11.0.1
RISC-V rv64gc clang 12.0.0
RISC-V rv64gc clang 12.0.1
RISC-V rv64gc clang 13.0.0
RISC-V rv64gc clang 13.0.1
RISC-V rv64gc clang 14.0.0
RISC-V rv64gc clang 15.0.0
RISC-V rv64gc clang 16.0.0
RISC-V rv64gc clang 17.0.1
RISC-V rv64gc clang 18.1.0
RISC-V rv64gc clang 9.0.0
RISC-V rv64gc clang 9.0.1
Raspbian Buster
Raspbian Stretch
SPARC LEON gcc 12.2.0
SPARC LEON gcc 12.3.0
SPARC LEON gcc 13.1.0
SPARC LEON gcc 13.2.0
SPARC gcc 12.2.0
SPARC gcc 12.3.0
SPARC gcc 13.1.0
SPARC gcc 13.2.0
SPARC gcc 14.1.0
SPARC64 gcc 12.2.0
SPARC64 gcc 12.3.0
SPARC64 gcc 13.1.0
SPARC64 gcc 13.2.0
SPARC64 gcc 14.1.0
TI C6x gcc 12.2.0
TI C6x gcc 12.3.0
TI C6x gcc 13.1.0
TI C6x gcc 13.2.0
TI C6x gcc 14.1.0
TI CL430 21.6.1
VAX gcc NetBSDELF 10.4.0
VAX gcc NetBSDELF 10.5.0 (Nov 15 03:50:22 2023)
WebAssembly clang (trunk)
Xtensa ESP32 gcc 11.2.0 (2022r1)
Xtensa ESP32 gcc 12.2.0 (20230208)
Xtensa ESP32 gcc 8.2.0 (2019r2)
Xtensa ESP32 gcc 8.2.0 (2020r1)
Xtensa ESP32 gcc 8.2.0 (2020r2)
Xtensa ESP32 gcc 8.4.0 (2020r3)
Xtensa ESP32 gcc 8.4.0 (2021r1)
Xtensa ESP32 gcc 8.4.0 (2021r2)
Xtensa ESP32-S2 gcc 11.2.0 (2022r1)
Xtensa ESP32-S2 gcc 12.2.0 (20230208)
Xtensa ESP32-S2 gcc 8.2.0 (2019r2)
Xtensa ESP32-S2 gcc 8.2.0 (2020r1)
Xtensa ESP32-S2 gcc 8.2.0 (2020r2)
Xtensa ESP32-S2 gcc 8.4.0 (2020r3)
Xtensa ESP32-S2 gcc 8.4.0 (2021r1)
Xtensa ESP32-S2 gcc 8.4.0 (2021r2)
Xtensa ESP32-S3 gcc 11.2.0 (2022r1)
Xtensa ESP32-S3 gcc 12.2.0 (20230208)
Xtensa ESP32-S3 gcc 8.4.0 (2020r3)
Xtensa ESP32-S3 gcc 8.4.0 (2021r1)
Xtensa ESP32-S3 gcc 8.4.0 (2021r2)
arm64 msvc v19.28 VS16.9
arm64 msvc v19.29 VS16.10
arm64 msvc v19.29 VS16.11
arm64 msvc v19.30
arm64 msvc v19.31
arm64 msvc v19.32
arm64 msvc v19.33
arm64 msvc v19.34
arm64 msvc v19.35
arm64 msvc v19.36
arm64 msvc v19.37
arm64 msvc v19.38
arm64 msvc v19.latest
armv7-a clang (trunk)
armv7-a clang 10.0.0
armv7-a clang 10.0.1
armv7-a clang 11.0.0
armv7-a clang 11.0.1
armv7-a clang 12.0.0
armv7-a clang 12.0.1
armv7-a clang 13.0.0
armv7-a clang 13.0.1
armv7-a clang 14.0.0
armv7-a clang 15.0.0
armv7-a clang 16.0.0
armv7-a clang 17.0.1
armv7-a clang 18.1.0
armv7-a clang 9.0.0
armv7-a clang 9.0.1
armv8-a clang (all architectural features, trunk)
armv8-a clang (trunk)
armv8-a clang 10.0.0
armv8-a clang 10.0.1
armv8-a clang 11.0.0
armv8-a clang 11.0.1
armv8-a clang 12.0.0
armv8-a clang 13.0.0
armv8-a clang 14.0.0
armv8-a clang 15.0.0
armv8-a clang 16.0.0
armv8-a clang 17.0.1
armv8-a clang 18.1.0
armv8-a clang 9.0.0
armv8-a clang 9.0.1
ellcc 0.1.33
ellcc 0.1.34
ellcc 2017-07-16
hexagon-clang 16.0.5
llvm-mos atari2600-3e
llvm-mos atari2600-4k
llvm-mos atari2600-common
llvm-mos atari5200-supercart
llvm-mos atari8-cart-megacart
llvm-mos atari8-cart-std
llvm-mos atari8-cart-xegs
llvm-mos atari8-common
llvm-mos atari8-dos
llvm-mos c128
llvm-mos c64
llvm-mos commodore
llvm-mos cpm65
llvm-mos cx16
llvm-mos dodo
llvm-mos eater
llvm-mos mega65
llvm-mos nes
llvm-mos nes-action53
llvm-mos nes-cnrom
llvm-mos nes-gtrom
llvm-mos nes-mmc1
llvm-mos nes-mmc3
llvm-mos nes-nrom
llvm-mos nes-unrom
llvm-mos nes-unrom-512
llvm-mos osi-c1p
llvm-mos pce
llvm-mos pce-cd
llvm-mos pce-common
llvm-mos pet
llvm-mos rp6502
llvm-mos rpc8e
llvm-mos supervision
llvm-mos vic20
loongarch64 gcc 12.2.0
loongarch64 gcc 12.3.0
loongarch64 gcc 13.1.0
loongarch64 gcc 13.2.0
loongarch64 gcc 14.1.0
mips clang 13.0.0
mips clang 14.0.0
mips clang 15.0.0
mips clang 16.0.0
mips clang 17.0.1
mips clang 18.1.0
mips gcc 11.2.0
mips gcc 12.1.0
mips gcc 12.2.0
mips gcc 12.3.0
mips gcc 13.1.0
mips gcc 13.2.0
mips gcc 14.1.0
mips gcc 4.9.4
mips gcc 5.4
mips gcc 5.5.0
mips gcc 9.3.0 (codescape)
mips gcc 9.5.0
mips64 (el) gcc 12.1.0
mips64 (el) gcc 12.2.0
mips64 (el) gcc 12.3.0
mips64 (el) gcc 13.1.0
mips64 (el) gcc 13.2.0
mips64 (el) gcc 14.1.0
mips64 (el) gcc 4.9.4
mips64 (el) gcc 5.4.0
mips64 (el) gcc 5.5.0
mips64 (el) gcc 9.5.0
mips64 clang 13.0.0
mips64 clang 14.0.0
mips64 clang 15.0.0
mips64 clang 16.0.0
mips64 clang 17.0.1
mips64 clang 18.1.0
mips64 gcc 11.2.0
mips64 gcc 12.1.0
mips64 gcc 12.2.0
mips64 gcc 12.3.0
mips64 gcc 13.1.0
mips64 gcc 13.2.0
mips64 gcc 14.1.0
mips64 gcc 4.9.4
mips64 gcc 5.4.0
mips64 gcc 5.5.0
mips64 gcc 9.5.0
mips64el clang 13.0.0
mips64el clang 14.0.0
mips64el clang 15.0.0
mips64el clang 16.0.0
mips64el clang 17.0.1
mips64el clang 18.1.0
mipsel clang 13.0.0
mipsel clang 14.0.0
mipsel clang 15.0.0
mipsel clang 16.0.0
mipsel clang 17.0.1
mipsel clang 18.1.0
mipsel gcc 12.1.0
mipsel gcc 12.2.0
mipsel gcc 12.3.0
mipsel gcc 13.1.0
mipsel gcc 13.2.0
mipsel gcc 14.1.0
mipsel gcc 4.9.4
mipsel gcc 5.4.0
mipsel gcc 5.5.0
mipsel gcc 9.5.0
nanoMIPS gcc 6.3.0 (mtk)
power gcc 11.2.0
power gcc 12.1.0
power gcc 12.2.0
power gcc 12.3.0
power gcc 13.1.0
power gcc 13.2.0
power gcc 14.1.0
power gcc 4.8.5
power64 AT12.0 (gcc8)
power64 AT13.0 (gcc9)
power64 gcc 11.2.0
power64 gcc 12.1.0
power64 gcc 12.2.0
power64 gcc 12.3.0
power64 gcc 13.1.0
power64 gcc 13.2.0
power64 gcc 14.1.0
power64 gcc trunk
power64le AT12.0 (gcc8)
power64le AT13.0 (gcc9)
power64le clang (trunk)
power64le gcc 11.2.0
power64le gcc 12.1.0
power64le gcc 12.2.0
power64le gcc 12.3.0
power64le gcc 13.1.0
power64le gcc 13.2.0
power64le gcc 14.1.0
power64le gcc 6.3.0
power64le gcc trunk
powerpc64 clang (trunk)
s390x gcc 11.2.0
s390x gcc 12.1.0
s390x gcc 12.2.0
s390x gcc 12.3.0
s390x gcc 13.1.0
s390x gcc 13.2.0
s390x gcc 14.1.0
sh gcc 12.2.0
sh gcc 12.3.0
sh gcc 13.1.0
sh gcc 13.2.0
sh gcc 14.1.0
sh gcc 4.9.4
sh gcc 9.5.0
vast (trunk)
x64 msvc v19.0 (WINE)
x64 msvc v19.10 (WINE)
x64 msvc v19.14
x64 msvc v19.14 (WINE)
x64 msvc v19.15
x64 msvc v19.16
x64 msvc v19.20
x64 msvc v19.21
x64 msvc v19.22
x64 msvc v19.23
x64 msvc v19.24
x64 msvc v19.25
x64 msvc v19.26
x64 msvc v19.27
x64 msvc v19.28
x64 msvc v19.28 VS16.9
x64 msvc v19.29 VS16.10
x64 msvc v19.29 VS16.11
x64 msvc v19.30
x64 msvc v19.31
x64 msvc v19.32
x64 msvc v19.33
x64 msvc v19.34
x64 msvc v19.35
x64 msvc v19.36
x64 msvc v19.37
x64 msvc v19.38
x64 msvc v19.latest
x86 djgpp 4.9.4
x86 djgpp 5.5.0
x86 djgpp 6.4.0
x86 djgpp 7.2.0
x86 msvc v19.0 (WINE)
x86 msvc v19.10 (WINE)
x86 msvc v19.14
x86 msvc v19.14 (WINE)
x86 msvc v19.15
x86 msvc v19.16
x86 msvc v19.20
x86 msvc v19.21
x86 msvc v19.22
x86 msvc v19.23
x86 msvc v19.24
x86 msvc v19.25
x86 msvc v19.26
x86 msvc v19.27
x86 msvc v19.28
x86 msvc v19.28 VS16.9
x86 msvc v19.29 VS16.10
x86 msvc v19.29 VS16.11
x86 msvc v19.30
x86 msvc v19.31
x86 msvc v19.32
x86 msvc v19.33
x86 msvc v19.34
x86 msvc v19.35
x86 msvc v19.36
x86 msvc v19.37
x86 msvc v19.38
x86 msvc v19.latest
x86 nvc++ 22.11
x86 nvc++ 22.7
x86 nvc++ 22.9
x86 nvc++ 23.1
x86 nvc++ 23.11
x86 nvc++ 23.3
x86 nvc++ 23.5
x86 nvc++ 23.7
x86 nvc++ 23.9
x86 nvc++ 24.1
x86 nvc++ 24.3
x86-64 Zapcc 190308
x86-64 clang (amd-stg-open)
x86-64 clang (assertions trunk)
x86-64 clang (clangir)
x86-64 clang (experimental -Wlifetime)
x86-64 clang (experimental P1061)
x86-64 clang (experimental P1144)
x86-64 clang (experimental P1221)
x86-64 clang (experimental P2996)
x86-64 clang (experimental P3068)
x86-64 clang (experimental metaprogramming - P2632)
x86-64 clang (experimental pattern matching)
x86-64 clang (old concepts branch)
x86-64 clang (reflection)
x86-64 clang (resugar)
x86-64 clang (thephd.dev)
x86-64 clang (trunk)
x86-64 clang (variadic friends - P2893)
x86-64 clang (widberg)
x86-64 clang 10.0.0
x86-64 clang 10.0.0 (assertions)
x86-64 clang 10.0.1
x86-64 clang 11.0.0
x86-64 clang 11.0.0 (assertions)
x86-64 clang 11.0.1
x86-64 clang 12.0.0
x86-64 clang 12.0.0 (assertions)
x86-64 clang 12.0.1
x86-64 clang 13.0.0
x86-64 clang 13.0.0 (assertions)
x86-64 clang 13.0.1
x86-64 clang 14.0.0
x86-64 clang 14.0.0 (assertions)
x86-64 clang 15.0.0
x86-64 clang 15.0.0 (assertions)
x86-64 clang 16.0.0
x86-64 clang 16.0.0 (assertions)
x86-64 clang 17.0.1
x86-64 clang 17.0.1 (assertions)
x86-64 clang 18.1.0
x86-64 clang 18.1.0 (assertions)
x86-64 clang 2.6.0 (assertions)
x86-64 clang 2.7.0 (assertions)
x86-64 clang 2.8.0 (assertions)
x86-64 clang 2.9.0 (assertions)
x86-64 clang 3.0.0
x86-64 clang 3.0.0 (assertions)
x86-64 clang 3.1
x86-64 clang 3.1 (assertions)
x86-64 clang 3.2
x86-64 clang 3.2 (assertions)
x86-64 clang 3.3
x86-64 clang 3.3 (assertions)
x86-64 clang 3.4 (assertions)
x86-64 clang 3.4.1
x86-64 clang 3.5
x86-64 clang 3.5 (assertions)
x86-64 clang 3.5.1
x86-64 clang 3.5.2
x86-64 clang 3.6
x86-64 clang 3.6 (assertions)
x86-64 clang 3.7
x86-64 clang 3.7 (assertions)
x86-64 clang 3.7.1
x86-64 clang 3.8
x86-64 clang 3.8 (assertions)
x86-64 clang 3.8.1
x86-64 clang 3.9.0
x86-64 clang 3.9.0 (assertions)
x86-64 clang 3.9.1
x86-64 clang 4.0.0
x86-64 clang 4.0.0 (assertions)
x86-64 clang 4.0.1
x86-64 clang 5.0.0
x86-64 clang 5.0.0 (assertions)
x86-64 clang 5.0.1
x86-64 clang 5.0.2
x86-64 clang 6.0.0
x86-64 clang 6.0.0 (assertions)
x86-64 clang 6.0.1
x86-64 clang 7.0.0
x86-64 clang 7.0.0 (assertions)
x86-64 clang 7.0.1
x86-64 clang 7.1.0
x86-64 clang 8.0.0
x86-64 clang 8.0.0 (assertions)
x86-64 clang 8.0.1
x86-64 clang 9.0.0
x86-64 clang 9.0.0 (assertions)
x86-64 clang 9.0.1
x86-64 clang rocm-4.5.2
x86-64 clang rocm-5.0.2
x86-64 clang rocm-5.1.3
x86-64 clang rocm-5.2.3
x86-64 clang rocm-5.3.3
x86-64 clang rocm-5.7.0
x86-64 gcc (contract labels)
x86-64 gcc (contracts natural syntax)
x86-64 gcc (contracts)
x86-64 gcc (coroutines)
x86-64 gcc (modules)
x86-64 gcc (trunk)
x86-64 gcc 10.1
x86-64 gcc 10.2
x86-64 gcc 10.3
x86-64 gcc 10.4
x86-64 gcc 10.5
x86-64 gcc 11.1
x86-64 gcc 11.2
x86-64 gcc 11.3
x86-64 gcc 11.4
x86-64 gcc 12.1
x86-64 gcc 12.2
x86-64 gcc 12.3
x86-64 gcc 13.1
x86-64 gcc 13.2
x86-64 gcc 14.1
x86-64 gcc 3.4.6
x86-64 gcc 4.0.4
x86-64 gcc 4.1.2
x86-64 gcc 4.4.7
x86-64 gcc 4.5.3
x86-64 gcc 4.6.4
x86-64 gcc 4.7.1
x86-64 gcc 4.7.2
x86-64 gcc 4.7.3
x86-64 gcc 4.7.4
x86-64 gcc 4.8.1
x86-64 gcc 4.8.2
x86-64 gcc 4.8.3
x86-64 gcc 4.8.4
x86-64 gcc 4.8.5
x86-64 gcc 4.9.0
x86-64 gcc 4.9.1
x86-64 gcc 4.9.2
x86-64 gcc 4.9.3
x86-64 gcc 4.9.4
x86-64 gcc 5.1
x86-64 gcc 5.2
x86-64 gcc 5.3
x86-64 gcc 5.4
x86-64 gcc 5.5
x86-64 gcc 6.1
x86-64 gcc 6.2
x86-64 gcc 6.3
x86-64 gcc 6.4
x86-64 gcc 6.5
x86-64 gcc 7.1
x86-64 gcc 7.2
x86-64 gcc 7.3
x86-64 gcc 7.4
x86-64 gcc 7.5
x86-64 gcc 8.1
x86-64 gcc 8.2
x86-64 gcc 8.3
x86-64 gcc 8.4
x86-64 gcc 8.5
x86-64 gcc 9.1
x86-64 gcc 9.2
x86-64 gcc 9.3
x86-64 gcc 9.4
x86-64 gcc 9.5
x86-64 icc 13.0.1
x86-64 icc 16.0.3
x86-64 icc 17.0.0
x86-64 icc 18.0.0
x86-64 icc 19.0.0
x86-64 icc 19.0.1
x86-64 icc 2021.1.2
x86-64 icc 2021.10.0
x86-64 icc 2021.2.0
x86-64 icc 2021.3.0
x86-64 icc 2021.4.0
x86-64 icc 2021.5.0
x86-64 icc 2021.6.0
x86-64 icc 2021.7.0
x86-64 icc 2021.7.1
x86-64 icc 2021.8.0
x86-64 icc 2021.9.0
x86-64 icx (latest)
x86-64 icx 2021.1.2
x86-64 icx 2021.2.0
x86-64 icx 2021.3.0
x86-64 icx 2021.4.0
x86-64 icx 2022.0.0
x86-64 icx 2022.1.0
x86-64 icx 2022.2.0
x86-64 icx 2022.2.1
x86-64 icx 2023.0.0
x86-64 icx 2023.1.0
x86-64 icx 2023.2.1
x86-64 icx 2024.0.0
zig c++ 0.10.0
zig c++ 0.11.0
zig c++ 0.12.0
zig c++ 0.6.0
zig c++ 0.7.0
zig c++ 0.7.1
zig c++ 0.8.0
zig c++ 0.9.0
zig c++ trunk
Options
Source code
#ifndef DEAP_H_INCLUDED #define DEAP_H_INCLUDED # include <stdio.h> /* operator overloading : bool operator < ( Type data1, Type data2 ) ; */ template<class Type> class Deap { private: Type* mHeap ; int mMaxSize ; int mHeapSize ; void InsertData( int index, Type data ) ; void ReHeapUp( int index, bool isMin ) ; void BlankHeapDown( int& index, bool isMin ) ; int GetCorrespondingIndex( int index ) ; void DataSwap( int index1, int index2 ) ; void AdjustSize() ; public: explicit Deap(int max_size = 100) ; // constructor ~Deap() ; // destructor void Clear(); void Insert( Type data ) ; bool GetMin( Type& data ) ; bool GetMinAndDelete( Type& data ) ; void DeleteMin() ; bool GetMax( Type& data ) ; bool GetMaxAndDelete( Type& data ) ; void DeleteMax() ; int GetSize() ; } ; // class Deap template<class Type> Deap<Type>::Deap(int max_size) { // constructor mMaxSize = max_size ; mHeapSize = 1 ; mHeap = new Type[mMaxSize] ; } // Deap<Type>::Deap() template<class Type> Deap<Type>::~Deap() { // destructor delete[] mHeap ; mHeap = NULL ; } // Deap<Type>::~Deap() template<class Type> void Deap<Type>::Clear() { for (int i = 1; i < mHeapSize; ++i) mHeap[i].~Type(); mHeapSize = 1; } // Deap<Type>::Clear() template<class Type> void Deap<Type>::Insert( Type data ) { if ( mHeapSize == mMaxSize ) { AdjustSize() ; } // if if ( mHeapSize == 1 ) { mHeap[1] = data ; } // if else{ InsertData( mHeapSize, data ) ; } // else mHeapSize++ ; } // Deap<Type>::Insert() template<class Type> void Deap<Type>::InsertData( int index, Type data ) { mHeap[index] = data ; int correspondingIndex = GetCorrespondingIndex( index ) ; if ( index < correspondingIndex ) { // index is in Min Heap if ( correspondingIndex >= mHeapSize ) { // correspondingIndex not exist correspondingIndex = ( correspondingIndex - 1 ) / 2 ; } // if if ( mHeap[index] < mHeap[correspondingIndex] ) { ReHeapUp( index, true ) ; // Min Heap } // if else { DataSwap( index, correspondingIndex ) ; ReHeapUp( correspondingIndex, false ) ; // Max Heap } // else } // if else { // index is in Max Heap int leftChildIndex = correspondingIndex * 2 + 1 ; if ( leftChildIndex < mHeapSize ) { // // leftChildIndex exist int rightChildIndex = leftChildIndex + 1 ; if ( rightChildIndex < mHeapSize && mHeap[leftChildIndex] < mHeap[rightChildIndex] ) { correspondingIndex = rightChildIndex ; } // if else { correspondingIndex = leftChildIndex ; } // else } // if if ( mHeap[index] < mHeap[correspondingIndex] ) { DataSwap( index, correspondingIndex ) ; ReHeapUp( correspondingIndex, true ) ; // Min Heap } // if else { ReHeapUp( index, false ) ; // Max Heap } // else } // else } // Deap<Type>::InsertData() template<class Type> bool Deap<Type>::GetMin( Type& data ) { if ( mHeapSize != 1 ) { data = mHeap[1] ; return true ; } // if else { return false ; } // else } // Deap<Type>::GetMin() template<class Type> bool Deap<Type>::GetMinAndDelete( Type& data ) { if ( mHeapSize != 1 ) { data = mHeap[1] ; DeleteMin() ; return true ; } // if else { return false ; } // else } // Deap<Type>::GetMinAndDelete() template<class Type> void Deap<Type>::DeleteMin() { if ( mHeapSize != 1 ) { mHeapSize-- ; } // if if ( mHeapSize != 1 ) { Type temp = mHeap[mHeapSize] ; int blankIndex = 1 ; BlankHeapDown( blankIndex, true ) ; if ( mHeapSize == 2 ) { mHeap[1] = temp ; } // if else { InsertData( blankIndex, temp ) ; } // else } // if } // Deap<Type>::DeleteMin() template<class Type> bool Deap<Type>::GetMax( Type& data ) { if ( mHeapSize != 1 ) { data = ( mHeapSize == 2 ? mHeap[1] : mHeap[2] ) ; return true ; } // if else { return false ; } // else } // Deap<Type>::GetMax() template<class Type> bool Deap<Type>::GetMaxAndDelete( Type& data ) { if ( mHeapSize != 1 ) { data = ( mHeapSize == 2 ? mHeap[1] : mHeap[2] ) ; DeleteMax() ; return true ; } // if else { return false ; } // else } // Deap<Type>::GetMaxAndDelete() template<class Type> void Deap<Type>::DeleteMax() { if ( mHeapSize != 1 ) { mHeapSize-- ; } // if if ( mHeapSize != 1 && mHeapSize != 2 ) { Type temp = mHeap[mHeapSize] ; int blankIndex = 2 ; BlankHeapDown( blankIndex, false ) ; InsertData( blankIndex, temp ) ; } // if } // Deap<Type>::DeleteMax() template<class Type> int Deap<Type>::GetSize() { return mHeapSize ; } // Deap<Type>::GetSize() template<class Type> void Deap<Type>::AdjustSize() { Type* temp = mHeap ; mMaxSize = mMaxSize * 2 ; mHeap = new Type[mMaxSize] ; for ( int i = 0 ; i < mHeapSize ; i++ ) { mHeap[i] = temp[i] ; } // for delete[] temp ; temp = NULL ; } // Deap<Type>::AdjustSize() template<class Type> void Deap<Type>::ReHeapUp( int index, bool isMin ) { int currentIndex = index, parentIndex = 0 ; bool running = true ; while ( running ) { parentIndex = ( currentIndex - 1 ) / 2 ; if ( parentIndex == 0 ) { running = false ; } // if else { if ( isMin ? mHeap[currentIndex] < mHeap[parentIndex] : mHeap[parentIndex] < mHeap[currentIndex] ) { DataSwap( currentIndex, parentIndex ) ; currentIndex = parentIndex ; } // if else { running = false ; } // else } // else } // while } // Deap<Type>::ReHeapUp() template<class Type> void Deap<Type>::BlankHeapDown( int& index, bool isMin ) { int leftChildIndex = 0, rightChildIndex = 0 ; int targetIndex = 0 ; leftChildIndex = index * 2 + 1 ; while ( leftChildIndex < mHeapSize ) { targetIndex = leftChildIndex ; rightChildIndex = leftChildIndex + 1 ; if ( rightChildIndex < mHeapSize && ( isMin ? mHeap[rightChildIndex] < mHeap[targetIndex] : mHeap[targetIndex] < mHeap[rightChildIndex] ) ) { targetIndex = rightChildIndex ; } // if mHeap[index] = mHeap[targetIndex] ; index = targetIndex ; leftChildIndex = index * 2 + 1 ; } // while } // Deap<Type>::BlankHeapDown() template<class Type> int Deap<Type>::GetCorrespondingIndex( int index ) { int rightMostIndex = 0, increaseRange = 2 ; while ( index > rightMostIndex ) { rightMostIndex += increaseRange ; increaseRange *= 2 ; } // while int middleLeftIndex = ( rightMostIndex + ( rightMostIndex / 2 ) ) / 2 ; if ( index <= middleLeftIndex ) { return rightMostIndex - ( middleLeftIndex - index ) ; } // if else { return middleLeftIndex - ( rightMostIndex - index ) ; } // else } // Deap<Type>::GetCorrespondingIndex() template<class Type> void Deap<Type>::DataSwap( int index1, int index2 ) { Type temp = mHeap[index1] ; mHeap[index1] = mHeap[index2] ; mHeap[index2] = temp ; } // Deap<Type>::DataSwap() #endif // DEAP_H_INCLUDED // Copyright Malte Skarupke 2020. // Distributed under the Boost Software License, Version 1.0. // (See http://www.boost.org/LICENSE_1_0.txt) #include <utility> #include <cstdint> #include <functional> namespace minmax_heap_helpers { // returns the index of the highest set bit. undefined if no bits are set. // examples: // highest_set_bit(1) = 0 // highest_set_bit(4) = 2 // highest_set_bit(55) = 5 inline int highest_set_bit(uint64_t i) { #ifdef _MSC_VER unsigned long result; _BitScanReverse64(&result, i); return result; #else return 63 - __builtin_clzl(i); #endif } inline bool is_new_item_min(uint64_t length) { return (highest_set_bit(length) & 1) == 0; } inline bool is_min_item(uint64_t index) { return is_new_item_min(index + 1); } inline uint64_t grandparent_index(uint64_t index) { return (index - 3) / 4; } inline uint64_t parent_index(uint64_t index) { return (index - 1) / 2; } inline uint64_t first_child_index(uint64_t index) { return (index * 2) + 1; } inline uint64_t last_grandchild_index(uint64_t index) { return (index * 4) + 6; } template<typename It, typename Compare> uint64_t smallest_descendant(It begin, uint64_t length, uint64_t first_child, uint64_t first_grandchild, Compare && compare) { uint64_t second_child = first_child + 1; if (first_grandchild >= length) return first_child + (second_child != length && compare(begin[second_child], begin[first_child])); uint64_t second_grandchild = first_grandchild + 1; if (second_grandchild == length) return compare(begin[first_grandchild], begin[second_child]) ? first_grandchild : second_child; uint64_t min_grandchild = first_grandchild + !!compare(begin[second_grandchild], begin[first_grandchild]); uint64_t third_grandchild = second_grandchild + 1; if (third_grandchild == length) return compare(begin[min_grandchild], begin[second_child]) ? min_grandchild : second_child; else return compare(begin[min_grandchild], begin[third_grandchild]) ? min_grandchild : third_grandchild; } template<typename It, typename Compare> uint64_t largest_descendant(It begin, uint64_t length, uint64_t first_child, uint64_t first_grandchild, Compare && compare) { uint64_t second_child = first_child + 1; if (first_grandchild >= length) return first_child + (second_child != length && compare(begin[first_child], begin[second_child])); uint64_t second_grandchild = first_grandchild + 1; if (second_grandchild == length) return compare(begin[second_child], begin[first_grandchild]) ? first_grandchild : second_child; uint64_t max_grandchild = first_grandchild + !!compare(begin[first_grandchild], begin[second_grandchild]); uint64_t third_grandchild = second_grandchild + 1; if (third_grandchild == length) return compare(begin[second_child], begin[max_grandchild]) ? max_grandchild : second_child; else return compare(begin[max_grandchild], begin[third_grandchild]) ? third_grandchild : max_grandchild; } template<typename It, typename Compare> void push_down_min(It begin, typename std::iterator_traits<It>::value_type value, uint64_t index, uint64_t length, Compare && compare) { using std::swap; for (;;) { uint64_t last_grandchild = last_grandchild_index(index); if (last_grandchild < length) { auto it = begin + last_grandchild; uint64_t min_first_half = last_grandchild - 2 - !!compare(it[-3], it[-2]); uint64_t min_second_half = last_grandchild - !!compare(it[-1], it[0]); uint64_t smallest = compare(begin[min_second_half], begin[min_first_half]) ? min_second_half : min_first_half; if (!compare(begin[smallest], value)) break; begin[index] = std::move(begin[smallest]); index = smallest; uint64_t parent = parent_index(index); if (compare(begin[parent], value)) swap(begin[parent], value); } else { uint64_t first_child = first_child_index(index); if (first_child >= length) break; uint64_t first_grandchild = last_grandchild - 3; uint64_t smallest = smallest_descendant(begin, length, first_child, first_grandchild, compare); if (!compare(begin[smallest], value)) break; begin[index] = std::move(begin[smallest]); index = smallest; if (smallest < first_grandchild) break; uint64_t parent = parent_index(index); if (compare(begin[parent], value)) { begin[index] = std::move(begin[parent]); index = parent; } break; } } begin[index] = std::move(value); } template<typename It, typename Compare> void push_down_min_one_child_only(It begin, uint64_t index, Compare&& compare) { using std::swap; uint64_t child = first_child_index(index); if (compare(begin[child], begin[index])) swap(begin[index], begin[child]); } template<typename It, typename Compare> void push_down_min_one_level_only(It begin, uint64_t index, Compare&& compare) { using std::swap; uint64_t first_child = first_child_index(index); uint64_t smaller_child = first_child + !!compare(begin[first_child + 1], begin[first_child]); if (compare(begin[smaller_child], begin[index])) swap(begin[index], begin[smaller_child]); } template<typename It, typename Compare> void push_down_max(It begin, typename std::iterator_traits<It>::value_type value, uint64_t index, uint64_t length, Compare&& compare) { using std::swap; for (;;) { uint64_t last_grandchild = last_grandchild_index(index); if (last_grandchild < length) { auto it = begin + last_grandchild; uint64_t max_first_half = last_grandchild - 2 - !!compare(it[-2], it[-3]); uint64_t max_second_half = last_grandchild - !!compare(it[0], it[-1]); uint64_t largest = compare(begin[max_first_half], begin[max_second_half]) ? max_second_half : max_first_half; if (!compare(value, begin[largest])) break; begin[index] = std::move(begin[largest]); index = largest; uint64_t parent = parent_index(index); if (compare(value, begin[parent])) swap(begin[parent], value); } else { uint64_t first_child = first_child_index(index); if (first_child >= length) break; uint64_t first_grandchild = last_grandchild - 3; uint64_t largest = largest_descendant(begin, length, first_child, first_grandchild, compare); if (!compare(value, begin[largest])) break; begin[index] = std::move(begin[largest]); index = largest; if (largest < first_grandchild) break; uint64_t parent = parent_index(index); if (compare(value, begin[parent])) { begin[index] = std::move(begin[parent]); index = parent; } break; } } begin[index] = std::move(value); } template<typename It, typename Compare> void push_down_max_one_child_only(It begin, uint64_t index, Compare&& compare) { using std::swap; uint64_t child = first_child_index(index); if (compare(begin[index], begin[child])) swap(begin[index], begin[child]); } template<typename It, typename Compare> void push_down_max_one_level_only(It begin, uint64_t index, Compare&& compare) { using std::swap; uint64_t first_child = first_child_index(index); uint64_t bigger_child = first_child + !!compare(begin[first_child], begin[first_child + 1]); if (compare(begin[index], begin[bigger_child])) swap(begin[index], begin[bigger_child]); } } template<typename It, typename Compare> bool is_minmax_heap(It begin, It end, Compare&& compare) { uint64_t length = static_cast<uint64_t>(end - begin); auto test_index = [](uint64_t index, auto compare_index) { uint64_t first_child = minmax_heap_helpers::first_child_index(index); uint64_t second_child = first_child + 1; uint64_t first_grandchild = minmax_heap_helpers::first_child_index(first_child); uint64_t second_grandchild = first_grandchild + 1; uint64_t third_grandchild = minmax_heap_helpers::first_child_index(second_child); uint64_t fourth_grandchild = third_grandchild + 1; return compare_index(first_child) && compare_index(second_child) && compare_index(first_grandchild) && compare_index(second_grandchild) && compare_index(third_grandchild) && compare_index(fourth_grandchild); }; for (uint64_t i = 0; i < length; ++i) { if (minmax_heap_helpers::is_min_item(i)) { auto compare_one = [&](uint64_t child) { return child >= length || !compare(begin[child], begin[i]); }; if (!test_index(i, compare_one)) return false; } else { auto compare_one = [&](uint64_t child) { return child >= length || !compare(begin[i], begin[child]); }; if (!test_index(i, compare_one)) return false; } } return true; } template<typename It> bool is_minmax_heap(It begin, It end) { return is_minmax_heap(begin, end, std::less<>{}); } template<typename It, typename Compare> void push_minmax_heap(It begin, It end, Compare&& compare) { uint64_t length = static_cast<uint64_t>(end - begin); uint64_t index = length - 1; uint64_t parent = minmax_heap_helpers::parent_index(index); typename std::iterator_traits<It>::value_type value = std::move(end[-1]); if (minmax_heap_helpers::is_new_item_min(length)) { if (index == 0) static_cast<void>(0); else if (compare(begin[parent], value)) { begin[index] = std::move(begin[parent]); index = parent; goto push_up_max; } else { for (;;) { { uint64_t grandparent = minmax_heap_helpers::grandparent_index(index); if (compare(value, begin[grandparent])) { begin[index] = std::move(begin[grandparent]); index = grandparent; } else break; } push_up_min: if (!index) break; } } } else if (compare(value, begin[parent])) { begin[index] = std::move(begin[parent]); index = parent; goto push_up_min; } else { push_up_max: while (index > 2) { uint64_t grandparent = minmax_heap_helpers::grandparent_index(index); if (compare(begin[grandparent], value)) { begin[index] = std::move(begin[grandparent]); index = grandparent; } else break; } } begin[index] = std::move(value); } template<typename It> void push_minmax_heap(It begin, It end) { push_minmax_heap(begin, end, std::less<>{}); } template<typename It, typename Compare> void pop_minmax_heap_min(It begin, It end, Compare&& compare) { uint64_t length = static_cast<uint64_t>(end - begin) - 1; if (length == 0) return; minmax_heap_helpers::push_down_min(begin, std::exchange(end[-1], std::move(begin[0])), 0, length, compare); } template<typename It> void pop_minmax_heap_min(It begin, It end) { pop_minmax_heap_min(begin, end, std::less<>{}); } template<typename It, typename Compare> void pop_minmax_heap_max(It begin, It end, Compare&& compare) { uint64_t length = static_cast<uint64_t>(end - begin) - 1; if (length <= 1) return; uint64_t index = 1 + !!compare(begin[1], begin[2]); minmax_heap_helpers::push_down_max(begin, std::exchange(end[-1], std::move(begin[index])), index, length, std::forward<Compare>(compare)); } template<typename It> void pop_minmax_heap_max(It begin, It end) { pop_minmax_heap_max(begin, end, std::less<>{}); } template<typename It, typename Compare> void make_minmax_heap(It begin, It end, Compare && compare) { uint64_t length = end - begin; uint64_t index = length / 2; if (index == 0) return; // optimization: there can be only one item that has only one child // handling that item up front simplifies the second loop a little, since // we know that all other items have two children if ((length & 1) == 0) { --index; if (minmax_heap_helpers::is_min_item(index)) minmax_heap_helpers::push_down_min_one_child_only(begin, index, compare); else minmax_heap_helpers::push_down_max_one_child_only(begin, index, compare); if (index == 0) return; } // optimization: half of all the items will have no grandchildren. this // simplifies the push_down function a lot, so we handle these items // first. we could then do another optimization where we know that // after the first half, the next quarter of items has grandchildren but // no great-grandchildren, but the code is already big enough if (length != 4) { uint64_t lowest_index_with_no_grandchildren = length / 4; for (;;) { int highest_bit = minmax_heap_helpers::highest_set_bit(index); uint64_t loop_until = std::max(lowest_index_with_no_grandchildren, (static_cast<uint64_t>(1) << highest_bit) - 1); --index; if (highest_bit & 1) { for (;; --index) { minmax_heap_helpers::push_down_max_one_level_only(begin, index, compare); if (index == loop_until) break; } } else { for (;; --index) { minmax_heap_helpers::push_down_min_one_level_only(begin, index, compare); if (index == loop_until) break; } if (index == 0) return; } if (index == lowest_index_with_no_grandchildren) break; } } int highest_bit = minmax_heap_helpers::highest_set_bit(index); uint64_t loop_until = (static_cast<uint64_t>(1) << highest_bit) - 1; switch (highest_bit & 1) { for (;;) { case 0: for (;;) { --index; minmax_heap_helpers::push_down_min(begin, std::move(begin[index]), index, length, compare); if (index == loop_until) break; } if (index == 0) return; loop_until /= 2; [[fallthrough]]; case 1: for (;;) { --index; minmax_heap_helpers::push_down_max(begin, std::move(begin[index]), index, length, compare); if (index == loop_until) break; } loop_until /= 2; } } } template<typename It> void make_minmax_heap(It begin, It end) { return make_minmax_heap(begin, end, std::less<>{}); } namespace dary_heap_helpers { template<int D> uint64_t first_child_index(uint64_t index) { return index * D + 1; } template<int D> uint64_t last_child_index(uint64_t index) { return index * D + D; } template<int D> uint64_t last_grandchild_index(uint64_t index) { return index * (D * D) + (D * D + D); } template<int D> uint64_t parent_index(uint64_t index) { return (index - 1) / D; } template<int D> uint64_t grandparent_index(uint64_t index) { return (index - (D + 1)) / (D * D); } template<int D> uint64_t index_with_no_grandchild(uint64_t length) { return grandparent_index<D>(length - 1) + 1; } template<int D, typename It, typename Compare> inline It largest_child(It first_child_it, Compare && compare) { if constexpr (D == 1) return first_child_it; else if constexpr (D == 2) return first_child_it + !!compare(first_child_it[0], first_child_it[1]); else { It first_half_largest = largest_child<D / 2>(first_child_it, compare); It second_half_largest = largest_child<D - D / 2>(first_child_it + D / 2, compare); return compare(*first_half_largest, *second_half_largest) ? second_half_largest : first_half_largest; } } template<int D, typename It, typename Compare> It largest_child(It first_child_it, int num_children, Compare && compare) { if constexpr (D == 2) return first_child_it; else if constexpr (D == 3) { if (num_children == 1) return first_child_it; else return first_child_it + !!compare(first_child_it[0], first_child_it[1]); } else if constexpr (D == 4) { switch (num_children) { case 1: return first_child_it; case 2: return first_child_it + !!compare(first_child_it[0], first_child_it[1]); default: It largest = first_child_it + !!compare(first_child_it[0], first_child_it[1]); return compare(*largest, first_child_it[2]) ? first_child_it + 2 : largest; } } else { switch(num_children) { case 1: return first_child_it; case 2: return first_child_it + !!compare(first_child_it[0], first_child_it[1]); case 3: { It largest = first_child_it + !!compare(first_child_it[0], first_child_it[1]); return compare(*largest, first_child_it[2]) ? first_child_it + 2 : largest; } case 4: { It largest_first_half = first_child_it + !!compare(first_child_it[0], first_child_it[1]); It largest_second_half = first_child_it + 2 + !!compare(first_child_it[2], first_child_it[3]); return compare(*largest_first_half, *largest_second_half) ? largest_second_half : largest_first_half; } default: int half = num_children / 2; It first_half_largest = largest_child<D>(first_child_it, half, compare); It second_half_largest = largest_child<D>(first_child_it + half, num_children - half, compare); return compare(*first_half_largest, *second_half_largest) ? second_half_largest : first_half_largest; } } } } template<int D, typename It, typename Compare> void make_dary_heap(It begin, It end, Compare && compare) { using std::swap; uint64_t length = end - begin; if (length <= 1) return; uint64_t index = (length - 2) / D; // optimization: there can be only one item that has fewer than D children // handling that item up front simplifies the second loop a little, since // we know that all other items have two children int num_children_end = (length - 1) % D; if (num_children_end) { It largest_child = dary_heap_helpers::largest_child<D>(begin + dary_heap_helpers::first_child_index<D>(index), num_children_end, compare); if (compare(begin[index], *largest_child)) swap(begin[index], *largest_child); if (index == 0) return; --index; } // optimization: half of all the items will have no grandchildren. this // simplifies the push_down function a lot, so we handle these items // first. we could then do another optimization where we know that // after the first half, the next quarter of items has grandchildren but // no great-grandchildren, but the code is already big enough if (index > 0) { uint64_t lowest_index_with_no_grandchildren = dary_heap_helpers::index_with_no_grandchild<D>(length); for (;;) { It largest_child = dary_heap_helpers::largest_child<D>(begin + dary_heap_helpers::first_child_index<D>(index), compare); if (compare(begin[index], *largest_child)) swap(begin[index], *largest_child); if (index-- == lowest_index_with_no_grandchildren) break; } } for (;; --index) { typename std::iterator_traits<It>::value_type value = std::move(begin[index]); uint64_t move_down_index = index; for (;;) { uint64_t last_child_index = dary_heap_helpers::last_child_index<D>(move_down_index); uint64_t first_child_index = last_child_index - (D - 1); It largest_child = begin; if (last_child_index < length) largest_child = dary_heap_helpers::largest_child<D>(begin + first_child_index, compare); else if (first_child_index >= length) break; else largest_child = dary_heap_helpers::largest_child<D>(begin + first_child_index, length - first_child_index, compare); if (!compare(value, *largest_child)) break; begin[move_down_index] = std::move(*largest_child); move_down_index = largest_child - begin; } begin[move_down_index] = std::move(value); if (index == 0) break; } } template<int D, typename It> void make_dary_heap(It begin, It end) { make_dary_heap<D>(begin, end, std::less<>{}); } template<int D, typename It, typename Compare> bool is_dary_heap(It begin, It end, Compare && compare) { uint64_t length = end - begin; for (uint64_t i = 1; i < length; ++i) { uint64_t parent = dary_heap_helpers::parent_index<D>(i); if (compare(begin[parent], begin[i])) return false; } return true; } template<int D, typename It> bool is_dary_heap(It begin, It end) { return is_dary_heap<D>(begin, end, std::less<>{}); } template<int D, typename It, typename Compare> void push_dary_heap(It begin, It end, Compare && compare) { typename std::iterator_traits<It>::value_type value = std::move(end[-1]); uint64_t index = (end - begin) - 1; while (index > 0) { uint64_t parent = dary_heap_helpers::parent_index<D>(index); if (!compare(begin[parent], value)) break; begin[index] = std::move(begin[parent]); index = parent; } begin[index] = std::move(value); } template<int D, typename It> void push_dary_heap(It begin, It end) { return push_dary_heap<D>(begin, end, std::less<>{}); } template<int D, typename It, typename Compare> void pop_dary_heap(It begin, It end, Compare && compare) { uint64_t length = (end - begin) - 1; typename std::iterator_traits<It>::value_type value = std::move(end[-1]); end[-1] = std::move(begin[0]); uint64_t index = 0; for (;;) { uint64_t last_child = dary_heap_helpers::last_child_index<D>(index); uint64_t first_child = last_child - (D - 1); if (last_child < length) { It largest_child = dary_heap_helpers::largest_child<D>(begin + first_child, compare); if (!compare(value, *largest_child)) break; begin[index] = std::move(*largest_child); index = largest_child - begin; } else if (first_child < length) { It largest_child = dary_heap_helpers::largest_child<D>(begin + first_child, length - first_child, compare); if (compare(value, *largest_child)) { begin[index] = std::move(*largest_child); index = largest_child - begin; } break; } else break; } begin[index] = std::move(value); } template<int D, typename It> void pop_dary_heap(It begin, It end) { return pop_dary_heap<D>(begin, end, std::less<>{}); } #include <chrono> #include <random> #include <iostream> int num_items = 100'000; void measure_deap() { std::mt19937_64 random; std::uniform_int_distribution<int> distribution; Deap<int> d(num_items); for (int i = 0; i < num_items; ++i) { d.Insert(distribution(random)); } auto start = std::chrono::high_resolution_clock::now(); int data; for ( int i = 0 ; i < num_items; i++ ) { d.GetMinAndDelete(data); } auto end = std::chrono::high_resolution_clock::now(); auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start); std::cout << "Deap: " << duration.count() << "us" << std::endl; } void measure_min_max_heap() { std::mt19937_64 random; std::uniform_int_distribution<int> distribution; std::vector<int> heap; heap.reserve(num_items); for (int i = 0; i < num_items; ++i) { heap.push_back(distribution(random)); } auto start = std::chrono::high_resolution_clock::now(); int size = num_items; while (size > 0) { pop_minmax_heap_min(heap.begin(), heap.begin() + size); --size; } auto end = std::chrono::high_resolution_clock::now(); auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start); std::cout << "Min-max heap: " << duration.count() << "us" << std::endl; } int main() { measure_deap(); measure_min_max_heap(); }
Become a Patron
Sponsor on GitHub
Donate via PayPal
Source on GitHub
Mailing list
Installed libraries
Wiki
Report an issue
How it works
Contact the author
CE on Mastodon
About the author
Statistics
Changelog
Version tree