based

Opinionated utility library
git clone git://git.dimitrijedobrota.com/based.git
Log | Files | Refs | README | LICENSE | HACKING | CONTRIBUTING | CODE_OF_CONDUCT | BUILDING
commit fc616cd767a03229610ed8cff873e07a0cd828ac
parent 9d5172ed36002f9bc2876715eb40a5ba8af0b6aa
author Dimitrije Dobrota < mail@dimitrijedobrota.com >
date Fri, 21 Mar 2025 11:16:13 +0100

min_element, max_element and minmax_element

Diffstat:
M example/CMakeLists.txt | +
A example/algorithm.cpp | ++++++++++++++++++++++++++++++++++++++
M include/based/algorithm.hpp | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M include/based/instrumentation.hpp | +

4 files changed, 146 insertions(+), 0 deletions(-)

diff --git a/ example/CMakeLists.txt b/ example/CMakeLists.txt

@@ -21,5 +21,6 @@ function(add_example NAME)

endfunction()

add_example(instrumentation)
add_example(algorithm)

add_folders(Example)

diff --git a/ example/algorithm.cpp b/ example/algorithm.cpp

@@ -0,0 +1,38 @@

#include "based/algorithm.hpp"

#include "based/instrumentation.hpp"

int main()
{
{
const based::timer time;

based::count_operations(
16UL,
16UL * 1024 * 1024,
[](const auto& a, const auto& b) { based::min_element(a, b); },
based::normalize_n);
}

{
const based::timer time;

based::count_operations(
16UL,
16UL * 1024 * 1024,
[](const auto& a, const auto& b) { based::max_element(a, b); },
based::normalize_n);
}

{
const based::timer time;

based::count_operations(
16UL,
16UL * 1024 * 1024,
[](const auto& a, const auto& b) { based::minmax_element(a, b); },
based::normalize_n);
}

return 0;
}

diff --git a/ include/based/algorithm.hpp b/ include/based/algorithm.hpp

@@ -1,6 +1,7 @@

#pragma once

#include <functional>
#include <utility>

namespace based
{

@@ -20,6 +21,30 @@ const T& min(const T& lhs, const T& rhs)

return based::min(lhs, rhs, std::less());
}

// return first min element
template<typename I, typename Cmp>
I min_element(I first, I last, Cmp cmp)
{
if (first == last) {
return last;
}

I mini = first++;
while (first != last) {
if (cmp(*first, *mini)) {
mini = first;
}
first++;
}
return mini;
}

template<typename I>
I min_element(I first, I last)
{
return based::min_element(first, last, std::less());
}

// returns max element, second if equal
template<typename T, typename Cmp>
const T& max(const T& lhs, const T& rhs, Cmp cmp)

@@ -33,4 +58,85 @@ const T& max(const T& lhs, const T& rhs)

return based::max(lhs, rhs, std::less());
}

// return last max element
template<typename I, typename Cmp>
I max_element(I first, I last, Cmp cmp)
{
if (first == last) {
return last;
}

I maxi = first++;
while (first != last) {
if (!cmp(*first, *maxi)) {
maxi = first;
}
first++;
}
return maxi;
}

template<typename I>
I max_element(I first, I last)
{
return based::max_element(first, last, std::less());
}

// return first min and last max element
template<typename I, typename Cmp>
std::pair<I, I> minmax_element(I first, I last, Cmp cmp)
{
if (first == last) {
return {last, last};
}

I mini = first++;
if (first == last) {
return {mini, mini};
}

I maxi = first++;
if (cmp(*maxi, *mini)) {
std::swap(mini, maxi);
}

I next = std::next(first);
while (first != last && next != last) {
I pmini = first;
I pmaxi = next;

if (cmp(*pmaxi, *pmini)) {
std::swap(pmini, pmaxi);
}

if (cmp(*pmini, *mini)) {
mini = pmini;
}

if (!cmp(*pmaxi, *maxi)) {
maxi = pmaxi;
}

next++;
first = next;
next++;
}

if (first != last) {
if (cmp(*first, *mini)) {
mini = first;
} else if (!cmp(*first, *maxi)) {
maxi = first;
}
}

return {mini, maxi};
}

template<typename I>
std::pair<I, I> minmax_element(I first, I last)
{
return based::minmax_element(first, last, std::less());
}

} // namespace based

diff --git a/ include/based/instrumentation.hpp b/ include/based/instrumentation.hpp

@@ -40,6 +40,7 @@ public:

template<typename I>
void print_row(I first, I last, std::size_t precision)
{
std::cout << std::format("{:{}} | ", *first++, m_min_wth);
while (first != last) {
std::cout << std::format("{:{}.{}f} | ", *first, m_min_wth, precision);
first++;