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 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 5.4
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 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)
M68K gcc 13.1.0
M68K gcc 13.2.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 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 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
SPARC64 gcc 12.2.0
SPARC64 gcc 12.3.0
SPARC64 gcc 13.1.0
SPARC64 gcc 13.2.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 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 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
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 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 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 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 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 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 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 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
sh gcc 12.2.0
sh gcc 12.3.0
sh gcc 13.1.0
sh gcc 13.2.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 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 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 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 BSTREE #define BSTREE #include <cstdint> #include <functional> #include <iomanip> #include <iostream> #include <queue> #include <sstream> #include <stack> #include <utility> #include <vector> #include <gsl/gsl> #include <stdexcept> constexpr std::size_t min_size = 2; constexpr std::size_t root_node = 1; constexpr std::size_t default_depth = 4; constexpr std::size_t out_of_range = 0; constexpr void printSpaces(std::size_t num) { for (std::size_t i = 0; i < num; ++i) std::cout << ' '; } constexpr std::size_t leftChild(size_t index) { return index << 1; } constexpr std::size_t rightChild(size_t index) { return (index << 1) + 1; } constexpr std::size_t myParent(size_t index) { return index >> 1; } constexpr bool isLeftEdge(std::size_t index) { std::size_t temp = index >> 1; temp |= temp >> 1; // temp + 1 = 2^(floor(log2(index))) temp |= temp >> 2; // which is on the left edge temp |= temp >> 4; temp |= temp >> 8; temp |= temp >> 16; return temp + 1 == index; } constexpr bool isRightEdge(std::size_t index) { std::size_t temp = index; temp |= temp >> 1; // temp = 2^(floor(log2(index))+1)-1 temp |= temp >> 2; // which is on the right edge temp |= temp >> 4; temp |= temp >> 8; temp |= temp >> 16; return temp == index; } enum class Justify { Left, Right, Center }; enum class ChildType :bool { Left, Right }; constexpr ChildType whatType(std::size_t index) { if(index & 1) return ChildType::Right; return ChildType::Left; } template <class K, class M = char> class BSTree { public: struct Node; using key_type = K; using key_compare = std::function<bool(const key_type&, const key_type&)>; using value_type = std::pair<K, M>; using mapped_type = M; using reference = value_type& ; using const_reference = const value_type&; using size_type = std::size_t; using container_type = std::vector<Node>; template <bool isconst> struct bstIterator; class value_compare; using iterator = bstIterator<false>; using const_iterator = bstIterator<true>; BSTree(std::size_t size = min_size); BSTree(std::size_t size, const key_compare fn); mapped_type& at(const key_type& key); const mapped_type& at(const key_type& key) const; iterator begin(); const_iterator begin() const; const_iterator cbegin() const; void clear(); std::size_t count(const key_type& key) const; const_iterator cend() const noexcept; const_iterator crbegin() const; const_iterator crend() const noexcept; iterator end() noexcept; const_iterator end() const noexcept; std::pair<iterator, iterator> equal_range(const key_type& key); std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const; iterator erase(const_iterator position); iterator erase(const_iterator first, const_iterator last); std::size_t erase(const key_type& key); iterator find(const key_type key); const_iterator find(const key_type key) const; std::size_t height(); std::pair<typename BSTree<K, M>::iterator, bool> insert(const key_type& key, const mapped_type& mapped = mapped_type()); std::pair<typename BSTree<K, M>::iterator, bool> insert(const value_type & value); iterator insert(iterator, const value_type & value); template <class InputIterator> void insert(InputIterator first, InputIterator last); void insert(std::initializer_list<value_type> il); bool isBalanced(); bool isBST(); key_compare key_comp() const; iterator lower_bound(const key_type& key); const_iterator lower_bound(const key_type& key) const; mapped_type& operator[](const key_type& key); void reserve(std::size_t size); std::size_t size() const noexcept; void swap(BSTree&) noexcept; iterator rbegin(); const_iterator rbegin() const; iterator rend() noexcept; const_iterator rend() const noexcept; iterator upper_bound(const key_type & key); const_iterator upper_bound(const key_type & key) const; value_compare value_comp; void viewKeys(); void viewTree(std::size_t root = root_node, std::size_t depth = default_depth); class value_compare { friend class BSTree; protected: key_compare comp; value_compare(key_compare c):comp(c) {} public: using result_type = bool; using first_argument_type = value_type; using second_argument_type = value_type; bool operator()(const value_type& a, const value_type& b) const { return comp(a.first, b.first); } }; template <bool isconst = false> struct bstIterator { public: using value_type = std::pair<K, M>; using reference = typename std::conditional_t < isconst, value_type const &, value_type & >; using pointer = typename std::conditional_t < isconst, value_type const *, value_type * >; using vec_pointer = typename std::conditional_t <isconst, std::vector<Node> const *, std::vector<Node> *>; using key_compare_pointer = typename std::conditional_t <isconst, std::function<bool(const K&, const K&)> const *, std::function<bool(const K&, const K&)> *>; using iterator_category = std::bidirectional_iterator_tag; bstIterator() noexcept : ptrToBuffer(nullptr), index_(0), reverse_(false), ptrToComp(nullptr) {} /* * copy/conversion constructor */ bstIterator(const BSTree<K, M>::bstIterator<false>& i) noexcept : ptrToBuffer(i.ptrToBuffer), index_(i.index_), reverse_(i.reverse_), ptrToComp(i.ptrToComp) {} /* * dereferencing and other operators */ reference operator*() { if (index_ == out_of_range) { std::stringstream ss; ss << "\nPointer Out Of Range!\n"; throw std::out_of_range(ss.str()); } return (*ptrToBuffer).at(index_).value_; } pointer operator->() { return &(operator *()); } bstIterator& operator++ () { if (!reverse_) { if (index_ == out_of_range) { std::stringstream ss; ss << "\nOut Of Range: operator++\n"; throw std::out_of_range(ss.str()); } nextIndex(); return *this; } if (index_ != out_of_range) previousIndex(); else index_ = highest(root_node); return *this; } bstIterator operator ++(int) { const bstIterator iter = *this; if (!reverse_) { if (index_ == out_of_range) { std::stringstream ss; ss << "\nOut Of Range: operator ++(int)\n"; throw std::out_of_range(ss.str()); } nextIndex(); return iter; } if(index_ != out_of_range) previousIndex(); else index_ = highest(root_node); return iter; } bstIterator& operator --() { if (reverse_) { if (index_ == out_of_range) { std::stringstream ss; ss << "\nOut Of Range: operator--\n"; throw std::out_of_range(ss.str()); } nextIndex(); return *this; } if (index_ != out_of_range) previousIndex(); else index_ = highest(root_node); return *this; } bstIterator operator --(int) { const bstIterator iter = *this; if (reverse_) { if (index_ == out_of_range) { std::stringstream ss; ss << "\nOut Of Range: operator --(int)\n"; throw std::out_of_range(ss.str()); } nextIndex(); return iter; } if (index_ != out_of_range) previousIndex(); else index_ = highest(root_node); return iter; } bool operator==(const bstIterator &other) noexcept { if (comparable(other)) return (index_ == other.index_); return false; } bool operator!=(const bstIterator &other) noexcept { if (comparable(other)) return !this->operator==(other); return true; } friend class BSTree<K, M>; private: inline bool comparable(const bstIterator & other) noexcept { return (reverse_ == other.reverse_); } std::size_t highest(std::size_t root) { while ((*ptrToBuffer).at(root).rnode) root = rightChild(root); return root; } std::size_t lowest(std::size_t root) { while ((*ptrToBuffer).at(root).lnode) root = leftChild(root); return root; } void nextIndex() { if ((*ptrToBuffer).at(index_).rnode) { index_ = lowest(rightChild(index_)); return; } if (!isRightEdge(index_)) { const key_type key = (*ptrToBuffer).at(index_).key(); index_ = myParent(index_); while ((*ptrToComp)((*ptrToBuffer).at(index_).key(), key)) index_ = myParent(index_); } else index_ = out_of_range; } void previousIndex() { if ((*ptrToBuffer).at(index_).lnode) { index_ = highest(leftChild(index_)); return; } if (!isLeftEdge(index_)) { const key_type key = (*ptrToBuffer).at(index_).key(); index_ = myParent(index_); while ((*ptrToComp)(key, (*ptrToBuffer).at(index_).key())) index_ = myParent(index_); } else index_ = out_of_range; } vec_pointer ptrToBuffer; size_type index_; bool reverse_; key_compare_pointer ptrToComp; }; private: struct Node { Node(key_type key = key_type(), mapped_type mapped = mapped_type()) noexcept : value_(std::make_pair(key, mapped)), lnode(false), rnode(false) {} Node(value_type value) : value_(value), lnode(false), rnode(false) {} Node(const Node &node) : value_(node.value_), lnode(node.lnode), rnode(node.rnode) {} virtual ~Node() = default; Node& operator=(const Node&) = default; Node(Node&&) = default; Node& operator=(Node&&) = default; key_type& key() noexcept { return value_.first; } const key_type& key() const noexcept { return value_.first; } mapped_type& mapped() noexcept { return value_.second; } const mapped_type& mapped() const { return value_.second; } void printKey(std::size_t size, Justify just); value_type value_; bool lnode; bool rnode; }; uint8_t msbDeBruijn32(uint32_t v) noexcept; void moveDown(std::size_t root, ChildType type); void shift(std::size_t root, int diff); void moveUp(std::size_t); void shiftLeft(std::size_t); void shiftRight(std::size_t); void rotateRight(std::size_t index); void rotateLeft(std::size_t index); void rotateLR(std::size_t index); void rotateRL(std::size_t index); void reweight(std::size_t index); bool rebalanceRoot(); bool rebalance(std::size_t index, bool increase); void simpleRemove(std::size_t parent, ChildType type); std::size_t bottomNode(std::size_t current, ChildType type); void complexRemove(std::size_t child, ChildType type); void wipeout(std::size_t child, ChildType type); std::size_t locate(key_type key, std::size_t start = root_node); std::size_t erase(const key_type& key, std::size_t start); std::size_t height(std::size_t node); void inject(std::size_t index, iterator& iter, key_type key, mapped_type mapped, ChildType type); std::pair<typename BSTree<K, M>::iterator, bool> insert(std::size_t, const key_type & , const mapped_type & ); iterator bound(const key_type & key, bool upper); bool isBalanced(std::size_t index); bool isBST(std::size_t current); void inorder(std::size_t index, std::function<void(key_type&, mapped_type&)> fn); void traverseByLevel(std::size_t root, std::size_t max_level, std::function<void(std::size_t, std::size_t)> fn); std::size_t node_count; std::vector<Node> nodes; std::vector<int8_t> weights; key_compare comp; }; template<class K, class M> inline BSTree<K, M>::BSTree(std::size_t size) : comp(std::less<K>()), value_comp(std::less<K>()) { try { nodes.reserve(size); weights.reserve(size); } catch (const std::exception& e) { throw; } node_count = 0; } template<class K, class M> inline BSTree<K, M>::BSTree(std::size_t size, const key_compare fn) : comp(fn), value_comp(fn) { try { nodes.reserve(size); weights.reserve(size); } catch (const std::exception& e) { throw; } node_count = 0; } template<class K, class M> inline typename BSTree<K, M>::mapped_type & BSTree<K, M>::at(const key_type & key) { const std::size_t index = locate(key); if (index == out_of_range) { std::stringstream ss; ss << "\nOut Of Range for key: \"" << key << "\"\n"; throw std::out_of_range(ss.str()); } return nodes.at(index).mapped(); } template<class K, class M> inline const typename BSTree<K, M>::mapped_type & BSTree<K, M>::at(const key_type & key) const { std::size_t index = locate(key); if (index == out_of_range) { std::stringstream ss; ss << "\nOut Of Range for key: \"" << key << "\"\n"; throw std::out_of_range(ss.str()); } return nodes.at(index).mapped(); } template<class K, class M> inline typename BSTree<K, M>::iterator BSTree<K, M>::begin() { iterator iter; iter.ptrToBuffer = &nodes; iter.index_ = iter.lowest(root_node); iter.reverse_ = false; iter.ptrToComp = ∁ return iter; } template<class K, class M> inline typename BSTree<K, M>::const_iterator BSTree<K, M>::begin() const { return cbegin(); } template<class K, class M> inline typename BSTree<K, M>::const_iterator BSTree<K, M>::cbegin() const { const_iterator iter; iter.ptrToBuffer = &nodes; iter.index_ = iter.lowest(root_node); iter.reverse_ = false; iter.ptrToComp = ∁ return iter; } template<class K, class M> inline void BSTree<K, M>::clear() { nodes.resize(min_size); weights.resize(min_size); node_count = 0; weights.at(root_node) = 0; nodes.at(root_node).lnode = false; nodes.at(root_node).rnode = false; } template<class K, class M> inline std::size_t BSTree<K, M>::count(const key_type& key) const { if (locate(key) != out_of_range) return 1; return 0; } template<class K, class M> inline typename BSTree<K, M>::const_iterator BSTree<K, M>::cend() const noexcept { const_iterator iter; iter.ptrToBuffer = &nodes; iter.index_ = out_of_range; iter.reverse_ = false; iter.ptrToComp = ∁ return iter; } template<class K, class M> inline typename BSTree<K, M>::const_iterator BSTree<K, M>::crbegin() const { const_iterator iter; iter.ptrToBuffer = &nodes; iter.index_ = iter.highest(root_node); iter.reverse_ = true; iter.ptrToComp = ∁ return iter; } template<class K, class M> inline typename BSTree<K, M>::const_iterator BSTree<K, M>::crend() const noexcept { const_iterator iter; iter.ptrToBuffer = &nodes; iter.index_ = out_of_range; iter.reverse_ = true; iter.ptrToComp = ∁ return iter; } template<class K, class M> inline typename BSTree<K, M>::iterator BSTree<K, M>::end() noexcept { iterator iter; iter.ptrToBuffer = &nodes; iter.index_ = out_of_range; iter.reverse_ = false; iter.ptrToComp = ∁ return iter; } template<class K, class M> inline typename BSTree<K, M>::const_iterator BSTree<K, M>::end() const noexcept { return cend(); } template<class K, class M> inline std::pair<typename BSTree<K, M>::iterator, typename BSTree<K, M>::iterator> BSTree<K, M>::equal_range(const key_type & key) { iterator lower = bound(key, false); iterator upper = bound(key, true); return std::make_pair(lower, upper); } template<class K, class M> inline std::pair<typename BSTree<K, M>::const_iterator, typename BSTree<K, M>::const_iterator> BSTree<K, M>::equal_range(const key_type & key) const { std::pair<const_iterator, const_iterator> range; const_iterator& lower = range.first; const_iterator& upper = range.second; lower = upper = lower_bound(); upper.nextIndex(); return range; } template<class K, class M> inline uint8_t BSTree<K, M>::msbDeBruijn32(uint32_t v) noexcept { /* The use of a deBruijn sequence in order to find the most significant bit (MSB) in a 32-bit value. This cool idea is from a 1998 paper out of MIT (http://supertech.csail.mit.edu/papers/debruijn.pdf). */ static const std::array<uint8_t, 32> BitPosition { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 }; v |= v >> 1; // first round down to one less than a power of 2 v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16; return BitPosition.at(gsl::narrow_cast<uint32_t>(v * 0x07C4ACDDU) >> 27); } template<class K, class M> inline void BSTree<K, M>::moveDown(std::size_t root, ChildType type) { std::stack<std::size_t> inv_tree; std::queue<std::size_t> sub_tree; sub_tree.push(root); while (!sub_tree.empty()) { const std::size_t current = sub_tree.front(); sub_tree.pop(); inv_tree.push(current); if (nodes.at(current).lnode) sub_tree.push(leftChild(current)); if (nodes.at(current).rnode) sub_tree.push(rightChild(current)); } const std::size_t diff = (type == ChildType::Left) ? root : root + 1; const int root_msb = msbDeBruijn32(root); while (!inv_tree.empty()) { const std::size_t current = inv_tree.top(); inv_tree.pop(); const int n = msbDeBruijn32(current); const std::size_t forward = current + diff * (1 << (n - root_msb)); nodes.at(forward) = nodes.at(current); weights.at(forward) = weights.at(current); nodes.at(current).lnode = false; nodes.at(current).rnode = false; weights.at(current) = 0; } if (type == ChildType::Left) nodes.at(root).lnode = true; else nodes.at(root).rnode = true; } template<class K, class M> inline void BSTree<K, M>::shift(std::size_t root, int diff) { if (root <= 1) return; std::queue<size_t> sub_tree; const int root_msb = msbDeBruijn32(root); sub_tree.push(root); while (true) { int levelCount = sub_tree.size(); if (levelCount == 0) return; while (levelCount > 0) { const std::size_t current = sub_tree.front(); sub_tree.pop(); if (nodes.at(current).lnode) sub_tree.push(current << 1); if (nodes.at(current).rnode) sub_tree.push((current << 1) + 1); const int n = msbDeBruijn32(current); const std::size_t forward = current + diff * (1 << (n - root_msb)); nodes.at(forward) = nodes.at(current); weights.at(forward) = weights.at(current); nodes.at(current).lnode = false; nodes.at(current).rnode = false; weights.at(current) = 0; --levelCount; } } } template<class K, class M> inline void BSTree<K, M>::moveUp(std::size_t root) { const int diff = (root >> 1) - root; shift(root, diff); } template<class K, class M> inline void BSTree<K, M>::shiftLeft(std::size_t root) { const int diff = -1; shift(root, diff); } template<class K, class M> inline void BSTree<K, M>::shiftRight(std::size_t root) { const int diff = 1; shift(root, diff); } template<class K, class M> inline void BSTree<K, M>::rotateRight(std::size_t index) { const std::size_t parent = myParent(index); nodes.at(parent).lnode = false; moveDown(parent, ChildType::Right); const std::size_t rchild = rightChild(index); const std::size_t sibling = index + 1; if (nodes.at(index).rnode) { shiftRight(rchild); nodes.at(index).rnode = false; nodes.at(sibling).lnode = true; } else { nodes.at(sibling).lnode = false; } moveUp(index); nodes.at(parent).rnode = true; reweight(parent); reweight(index); reweight(sibling); } template<class K, class M> inline void BSTree<K, M>::rotateLeft(std::size_t index) { const std::size_t parent = myParent(index); nodes.at(parent).rnode = false; moveDown(parent, ChildType::Left); const std::size_t lchild = leftChild(index); const std::size_t sibling = index - 1; if (nodes.at(index).lnode) { shiftLeft(lchild); nodes.at(index).lnode = false; nodes.at(sibling).rnode = true; } else { nodes.at(sibling).rnode = false; } moveUp(index); nodes.at(parent).lnode = true; reweight(parent); reweight(index); reweight(sibling); } template<class K, class M> inline void BSTree<K, M>::rotateLR(std::size_t index) { const std::size_t parent = myParent(index); const std::size_t rchild = rightChild(index); std::size_t rlgrand(out_of_range), rrgrand(out_of_range); if (nodes.at(rchild).lnode) rlgrand = leftChild(rchild); if (nodes.at(rchild).rnode) rrgrand = rightChild(rchild); nodes.at(parent).lnode = false; moveDown(parent, ChildType::Right); nodes.at(parent) = nodes.at(rchild); nodes.at(rchild).lnode = false; nodes.at(rchild).rnode = false; nodes.at(index).rnode = false; const std::size_t sibling = index + 1; if (rrgrand != out_of_range) { const int diff = ((rrgrand + 1) >> 1) - rrgrand; shift(rrgrand, diff); nodes.at(sibling).lnode = true; } if (rlgrand != out_of_range) { moveUp(rlgrand); nodes.at(index).rnode = true; } nodes.at(parent).rnode = true; nodes.at(parent).lnode = true; reweight(rchild); reweight(parent); reweight(index); reweight(sibling); } template<class K, class M> inline void BSTree<K, M>::rotateRL(std::size_t index) { const std::size_t parent = myParent(index); const std::size_t lchild = leftChild(index); std::size_t llgrand(out_of_range), lrgrand(out_of_range); if (nodes.at(lchild).lnode) llgrand = leftChild(lchild); if (nodes.at(lchild).rnode) lrgrand = rightChild(lchild); nodes.at(parent).rnode = false; moveDown(parent, ChildType::Left); nodes.at(parent) = nodes.at(lchild); nodes.at(lchild).lnode = false; nodes.at(lchild).rnode = false; nodes.at(index).lnode = false; const std::size_t sibling = index - 1; if (llgrand != out_of_range) { const int diff = ((llgrand - 1) >> 1) - llgrand; shift(llgrand, diff); nodes.at(sibling).rnode = true; } if (lrgrand != out_of_range) { moveUp(lrgrand); nodes.at(index).lnode = true; } nodes.at(parent).lnode = true; nodes.at(parent).rnode = true; reweight(lchild); reweight(parent); reweight(index); reweight(sibling); } template<class K, class M> inline void BSTree<K, M>::reweight(std::size_t index) { int left(0), right(0); if (nodes.at(index).lnode) left = gsl::narrow_cast<int>(height(leftChild(index))); if (nodes.at(index).rnode) right = gsl::narrow_cast<int>(height(rightChild(index))); weights.at(index) = gsl::narrow_cast<int8_t>(right - left); } template<class K, class M> inline bool BSTree<K, M>::rebalanceRoot() { reweight(root_node); if (weights.at(root_node) >= -1 && weights.at(root_node) <= 1) return false; if (weights.at(root_node) > 0) rotateLeft(rightChild(root_node)); else rotateRight(leftChild(root_node)); reweight(root_node); return true; } template<class K, class M> inline bool BSTree<K, M>::rebalance(std::size_t index, bool increase) { if (index == 1) { return rebalanceRoot(); } const bool changed = true; while (index > 1) { const std::size_t parent = myParent(index); const int8_t old_weight = weights.at(parent); reweight(parent); if (weights.at(parent) == old_weight) return !changed; if ((whatType(index) == ChildType::Left && increase) || (whatType(index) == ChildType::Right && !increase)) { if (weights.at(parent) < -1) { const std::size_t pivot = leftChild(parent); reweight(pivot); // Added since weights can be inacurate (eek!) if (weights.at(pivot) < 0) rotateRight(pivot); else rotateLR(pivot); return changed; } index = parent; if (weights.at(index) == 0) return !changed; continue; } if (weights.at(parent) > 1) { const std::size_t pivot = rightChild(parent); reweight(pivot); // Added since weights can be inacurate (eek!) if (weights.at(pivot) > 0) rotateLeft(pivot); else rotateRL(pivot); return changed; } index = parent; if (weights.at(index) == 0) return !changed; } return changed; } template<class K, class M> void BSTree<K, M>::simpleRemove(std::size_t index, ChildType type) { const std::size_t parent = myParent(index); /* nodes.at(index).lnode = false; nodes.at(index).rnode = false; */ weights.at(index) = 0; if (type == ChildType::Right) { nodes.at(parent).rnode = false; if (weights.at(parent) - 1 < -1) { const std::size_t sibling = index - 1; rebalance(sibling, true); return; } if (--weights.at(parent) == 0) rebalance(parent, false); } else { nodes.at(parent).lnode = false; if (weights.at(parent) + 1 > 1) { const std::size_t sibling = index + 1; rebalance(sibling, true); return; } if (++weights.at(parent) == 0) rebalance(parent, false); } } template<class K, class M> std::size_t BSTree<K, M>::bottomNode(std::size_t current, ChildType type) { while (true) { if (type == ChildType::Right) { if (nodes.at(current).lnode) { current = leftChild(current); continue; } break; } if (nodes.at(current).rnode) { current = rightChild(current); continue; } break; } return current; } template<class K, class M> void BSTree<K, M>::complexRemove(std::size_t child, ChildType type) { const std::size_t index = myParent(child); if (type == ChildType::Left) { // move left child if (!nodes.at(child).rnode) { moveUp(child); nodes.at(index).rnode = true; if (++weights.at(index) == 0) rebalance(index, false); return; } wipeout(child, type); return; } if (!nodes.at(child).lnode) { // move right child moveUp(child); nodes.at(index).lnode = true; if (--weights.at(index) == 0) rebalance(index, false); return; } wipeout(child, type); return; } template<class K, class M> inline void BSTree<K, M>::wipeout(std::size_t child, ChildType type) { const std::size_t current = (type == ChildType::Left) ? bottomNode(rightChild(child), type) : bottomNode(leftChild(child), type); nodes.at(myParent(child)).value_ = nodes.at(current).value_; if (type==ChildType::Left) { if (nodes.at(current).lnode) moveUp(leftChild(current)); else nodes.at(myParent(current)).rnode = false; } else { if (nodes.at(current).rnode) moveUp(rightChild(current)); else nodes.at(myParent(current)).lnode = false; } rebalance(current, false); } template<class K, class M> std::size_t BSTree<K, M>::locate(key_type key, std::size_t start) { std::size_t current = start; while (true) { if (nodes.at(current).key() == key) return current; if (comp(key, nodes.at(current).key())) { if (!nodes.at(current).lnode) return out_of_range; current = current << 1; continue; } if (!nodes.at(current).rnode) return out_of_range; current = (current << 1) + 1; } return out_of_range; } template<class K, class M> typename BSTree<K, M>::iterator BSTree<K, M>::erase(const_iterator position) { constexpr std::size_t count_zero = 0; iterator iter; if (position == cend()) return end(); key_type next_key{}; std::size_t next_index(0); if (++position != cend()) { next_key = position->first; next_index = position.index_; } --position; if (erase(position->first, position.index_) == count_zero) return end(); if (next_index == out_of_range) return end(); iter = find(next_key); return iter; } template<class K, class M> typename BSTree<K, M>::iterator BSTree<K, M>::erase(const_iterator first, const_iterator last) { iterator iter; for (auto it = first; it != last; ++it) iter = erase(it); return iter; } template<class K, class M> std::size_t BSTree<K, M>::erase(const key_type& key) { return erase(key, 1); } template<class K, class M> std::size_t BSTree<K, M>::erase(const key_type& key, std::size_t start) { constexpr std::size_t count_zero = 0; constexpr std::size_t count_one = 1; const auto index = locate(key, start); if (index == out_of_range) return count_zero; const bool left = nodes.at(index).lnode; const bool right = nodes.at(index).rnode; --node_count; if (!left && !right) { simpleRemove(index, whatType(index)); return count_one; } const std::size_t lchild = leftChild(index); const std::size_t rchild = rightChild(index); if (left && !right) { moveUp(lchild); rebalance(index, false); return count_one; } if (!left && right) { moveUp(rchild); rebalance(index, false); return count_one; } if (left&&right) { if (height(rchild) <= height(lchild)) complexRemove(lchild, ChildType::Left); else complexRemove(rchild, ChildType::Right); return count_one; } throw std::exception(); return count_zero; } template<class K, class M> inline typename BSTree<K, M>::iterator BSTree<K, M>::find(const key_type key) { iterator iter; iter.ptrToBuffer = &nodes; iter.reverse_ = false; iter.ptrToComp = ∁ iter.index_ = locate(key); return iter; } template<class K, class M> inline typename BSTree<K, M>::const_iterator BSTree<K, M>::find(const key_type key) const { const_iterator iter; iter.ptrToBuffer = &nodes; iter.reverse_ = false; iter.ptrToComp = ∁ iter.index_ = locate(key); return iter; } template<class K, class M> std::size_t BSTree<K, M>::height(std::size_t index) { int height = 0; if (index == out_of_range) return height; std::queue<size_t> sub_tree; sub_tree.push(index); while (true) { int nodeCount = sub_tree.size(); if (nodeCount == 0) return height; height++; while (nodeCount > 0) { const std::size_t current = sub_tree.front(); sub_tree.pop(); if (nodes.at(current).lnode) sub_tree.push(leftChild(current)); if (nodes.at(current).rnode) sub_tree.push(rightChild(current)); --nodeCount; } } } template<class K, class M> inline std::size_t BSTree<K, M>::height() { if (node_count == 0) return 0; return height(root_node); } template<class K, class M> inline void BSTree<K, M>::inject(std::size_t index, iterator & iter, key_type key, mapped_type mapped, ChildType type) { ++node_count; std::size_t child{ 0 }; bool tilted = false; if (type == ChildType::Left) { child = leftChild(index); nodes.at(index).lnode = true; if (--weights.at(index) != 0) tilted = true; } else { child = rightChild(index); nodes.at(index).rnode = true; if (++weights.at(index) != 0) tilted = true; } nodes.at(child).key() = key; nodes.at(child).mapped() = mapped; weights.at(child) = 0; iter.index_ = child; if (tilted) { if (rebalance(index, true)) iter.index_ = locate(key); } } template<class K, class M> std::pair<typename BSTree<K, M>::iterator, bool> BSTree<K, M>::insert(std::size_t root, const key_type& key, const mapped_type& mapped) { iterator iter; iter.reverse_ = false; iter.ptrToComp = ∁ iter.ptrToBuffer = &nodes; if (node_count == 0) { ++node_count; nodes.resize(min_size); weights.resize(min_size); nodes.at(root_node).key() = key; nodes.at(root_node).mapped() = mapped; weights.at(root_node) = 0; iter.index_ = 1; return std::pair(iter, true); } std::size_t index = root; while (true) { if (key == nodes.at(index).key()) { nodes.at(index).mapped() = mapped; iter.index_ = index; return std::pair(iter, false); break; } if (2 * index >= nodes.size()) { const int n = msbDeBruijn32(index); nodes.resize(1 << (n + 2)); weights.resize(nodes.size()); } if (comp(key, nodes.at(index).key())) { if (!nodes.at(index).lnode) { inject(index, iter, key, mapped, ChildType::Left); return std::pair(iter, true); } index = leftChild(index); continue; } if (!nodes.at(index).rnode) { inject(index, iter, key, mapped, ChildType::Right); return std::pair(iter, true); } index = rightChild(index); } } template<class K, class M> std::pair<typename BSTree<K, M>::iterator, bool> BSTree<K, M>::insert(const key_type& key, const mapped_type& mapped) { return insert(1, key, mapped); } template<class K, class M> inline std::pair<typename BSTree<K, M>::iterator, bool> BSTree<K, M>::insert(const value_type& value) { return insert(value.first, value.second); } template<class K, class M> inline typename BSTree<K, M>::iterator BSTree<K, M>::insert(iterator hint, const value_type & value) { const std::size_t index = hint.index_; if (index == out_of_range) { if (!comp(value.first, (--hint)->first)) return insert(hint.index_, value.first, value.second).first; return insert(root_node, value.first, value.second).first; } if (comp(value.first, hint->first)) { --hint; if (hint.index_ == out_of_range || !comp(value.first, hint->first)) return insert(index, value.first, value.second).first; return insert(root_node, value.first, value.second).first; } ++hint; if (hint.index_ == out_of_range || comp(value.first, hint->first)) return insert(index, value.first, value.second).first; return insert(root_node, value.first, value.second).first; } template<class K, class M> template<class InputIterator> inline void BSTree<K, M>::insert(InputIterator first, InputIterator last) { for (auto it = first; it != last; ++it) const auto reply = insert(root_node, it->first, it->second); } template<class K, class M> inline void BSTree<K, M>::insert(std::initializer_list<value_type> il) { for (auto it = il.begin(); it != il.end(); ++it) const auto reply = insert(root_node, it->first, it->second); } template<class K, class M> bool BSTree<K, M>::isBalanced(std::size_t index) { std::size_t old_level = gsl::narrow_cast<std::size_t>(-1); bool ret = true; if (index == out_of_range) return true; traverseByLevel(index, height(index), [&](std::size_t level, std::size_t current) -> void { if (level != old_level) { old_level = level; } if (current == 0) return; if (nodes.at(current).lnode || nodes.at(current).rnode) { const std::size_t lheight = height(leftChild(current)); const std::size_t rheight = height(rightChild(current)); if ((lheight > rheight) && (lheight - rheight > 1) || (rheight > lheight) && (rheight - lheight > 1)) { ret = false; return; } } }); return ret; } template<class K, class M> inline bool BSTree<K, M>::isBalanced() { return isBalanced(root_node); } template<class K, class M> bool BSTree<K, M>::isBST(std::size_t index) { std::size_t old_level = gsl::narrow_cast<std::size_t>(-1); bool ret = true; if (index == out_of_range) return true; traverseByLevel(index, height(index), [&](std::size_t level, std::size_t current) -> void { if (level != old_level) { old_level = level; } if (current == 0) return; if (nodes.at(current).lnode) { const std::size_t lchild = leftChild(current); if (comp(nodes.at(current).key(), nodes.at(lchild).key())) { ret = false; return; } } if (nodes.at(current).rnode) { const std::size_t rchild = rightChild(current); if (comp(nodes.at(rchild).key(), nodes.at(current).key())) { ret = false; return; } } }); return ret; } template<class K, class M> inline bool BSTree<K, M>::isBST() { return isBST(root_node); } template<class K, class M> inline typename BSTree<K, M>::key_compare BSTree<K, M>::key_comp() const { return comp; } template<class K, class M> inline typename BSTree<K, M>::iterator BSTree<K, M>::bound(const key_type & key, bool upper) { iterator iter; std::size_t index = root_node; iter.ptrToBuffer = &nodes; iter.reverse_ = false; iter.ptrToComp = ∁ while (true) { if (key == nodes.at(index).key()) { iter.index_ = index; if (upper) return ++iter; return iter; } if (comp(key, nodes.at(index).key())) { // key < root->key if (nodes.at(index).lnode) { index = leftChild(index); continue; } else { iter.index_ = index; return iter; } } if (nodes.at(index).rnode) { index = rightChild(index); continue; } iter.index_ = index; return ++iter; } } template<class K, class M> inline typename BSTree<K, M>::iterator BSTree<K, M>::lower_bound(const key_type & key) { return bound(key, false); } template<class K, class M> inline typename BSTree<K, M>::const_iterator BSTree<K, M>::lower_bound(const key_type & key) const { const_iterator iter; iter = bound(key, false); return iter; } template<class K, class M> inline typename BSTree<K, M>::mapped_type & BSTree<K, M>::operator[](const key_type & key) { std::size_t index = locate(key); if (index == out_of_range) { mapped_type mapped{}; const auto[iter, reply] = insert(root_node, key, mapped); index = iter.index_; } return nodes.at(index).mapped(); } template<class K, class M> inline void BSTree<K, M>::reserve(std::size_t size) { nodes.reserve(size); weights.reserve(size); } template<class K, class M> inline std::size_t BSTree<K, M>::size() const noexcept { return node_count; } template<class K, class M> inline void BSTree<K, M>::swap(BSTree & other) noexcept { std::swap(nodes, other.nodes); std::swap(weights, other.weights); std::swap(node_count, other.node_count); } template<class K, class M> inline typename BSTree<K, M>::iterator BSTree<K, M>::rbegin() { iterator iter; iter.ptrToBuffer = &nodes; iter.index_ = iter.highest(root_node); iter.reverse_ = true; iter.ptrToComp = ∁ return iter; } template<class K, class M> inline typename BSTree<K, M>::const_iterator BSTree<K, M>::rbegin() const { return crbegin(); } template<class K, class M> inline typename BSTree<K, M>::iterator BSTree<K, M>::rend() noexcept { iterator iter; iter.ptrToBuffer = &nodes; iter.index_ = out_of_range; iter.reverse_ = true; iter.ptrToComp = ∁ return iter; } template<class K, class M> inline typename BSTree<K, M>::const_iterator BSTree<K, M>::rend() const noexcept { return crend(); } template<class K, class M> inline typename BSTree<K, M>::iterator BSTree<K, M>::upper_bound(const key_type & key) { return bound(key, true); } template<class K, class M> inline typename BSTree<K, M>::const_iterator BSTree<K, M>::upper_bound(const key_type & key) const { const_iterator iter; iter = bound(key, true); return iter; } template<class K, class M> void BSTree<K, M>::inorder(std::size_t index, std::function<void(key_type&, mapped_type&)> fn) { if (index == out_of_range) return; size_t current = index; std::stack<size_t> s; while (!s.empty() || current != out_of_range) { if (current != out_of_range) { s.push(current); if (!nodes.at(current).lnode) current = out_of_range; else current = leftChild(current); } else { current = s.top(); s.pop(); fn(nodes.at(current).key(), nodes.at(current).mapped()); if (!nodes.at(current).rnode) current = out_of_range; else current = rightChild(current); } } } template<class K, class M> inline void BSTree<K, M>::viewKeys() { inorder(1, [](key_type& key, mapped_type& mapped) -> void { std::cout << key << '\n'; }); } template<class K, class M> inline void BSTree<K, M>::traverseByLevel(std::size_t root, std::size_t max_level, std::function<void(std::size_t, std::size_t)> fn) { if (root < 1) return; std::queue<size_t> sub_tree; sub_tree.push(root); std::size_t level = 0; while (level < max_level) { int levelCount = sub_tree.size(); if (levelCount == 0) return; while (levelCount > 0) { const std::size_t current = sub_tree.front(); sub_tree.pop(); if (nodes.at(current).lnode) sub_tree.push(leftChild(current)); else sub_tree.push(0); if (nodes.at(current).rnode) sub_tree.push(rightChild(current)); else sub_tree.push(0); fn(level, current); --levelCount; } ++level; } } template<class K, class M> inline void BSTree<K, M>::Node::printKey(std::size_t size, Justify just) { std::stringstream ss; char buf[255]; ss << key(); ss.getline(buf,255); std::string s{buf}; const std::size_t length = s.length(); switch (just) { case Justify::Left: std::cout << s; printSpaces(size - length); break; case Justify::Right: printSpaces(size - length); std::cout << s; break; case Justify::Center: const std::size_t pad = (size - length) >> 1; printSpaces(pad); std::cout << s; printSpaces(size - length - pad); break; } } template<class K, class M> inline void BSTree<K, M>::viewTree(std::size_t root, std::size_t depth) { std::string s; std::size_t key_size = 0; traverseByLevel(root, depth, [&](std::size_t level, std::size_t index) -> void { std::stringstream ss; char buf[255]; if (index != 0) { ss << nodes.at(index).key(); ss.getline(buf, 255); s = buf; if (s.length() > key_size) key_size = s.length(); s.clear(); } }); std::size_t oldLevel = gsl::narrow_cast<std::size_t>(-1); traverseByLevel(root, depth, [&] (std::size_t level, std::size_t index) -> void { const std::size_t space_size = (key_size & 1) ? 1 : 2; if (level != oldLevel) { const std::size_t lead_space = ((1 << (depth - level - 1)) - 1) * ((key_size + space_size) >> 1); oldLevel = level; std::cout << "\n"; printSpaces(lead_space); } else { const std::size_t internal_space = ((1 << (depth - level - 1)) - 1)*(key_size + space_size) + space_size; printSpaces(internal_space); } if (index != 0) nodes.at(index).printKey(key_size, Justify::Center); else printSpaces(key_size); }); std::cout << "\n"; } #endif // !BSTREE
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