The choice of data representation means that we have up to three copies of each element. For large T, that could be problematic. For uncopyable T, it's a show-stopper.

An alternative implementation uses std::stack<T, std::list<T>> instead of std::stack<T, std::deque<T>> for m_data; this won't invalidate any relevant iterators when we push or pop, thus allowing m_mins and m_maxs to contain iterators (or references, or pointers) to the objects in the main stack.

Orthogonal to this, consider using a single stack of { value, min, max } rather than three parallel containers.

The empty() test in pop() is a departure from the standard library stack interface, which doesn't impose this overhead on users. I guess that's an implementation choice, but it is somewhat surprising.

The functions which return pointers could instead return references if we remove the empty() tests in them.

Instead of writing template <typename T> requires std::totally_ordered<T>, we could use the shorter and (IMO) clearer abbreviated constraint:

template <std::totally_ordered T>

Consider providing an emplace() member function, like std::stack. (If we use std::list and references, this allows the use of more exotic T that need not be movable).

The main difference between MinMaxComparable and std::totally_ordered is that the former doesn't require the two operators we actually use (<= and >=). Use the standard concept, which does include those operators and which is well-known, rather than introducing more cognitive load.

As always, self-contained code such as this should be accompanied by unit tests when presented for review. That helps users to understand the supported use-cases, gives confidence that the code works as advertised, and supports experimentation with alternative implementations.

Questions

Standard concept versus custom concept “with minimal requirements”

The careless way answer to this question would be to say that it would be better to go with a more minimal concept, even if that meant not using a standard concept.

However, the way your question is worded makes me suspect you don’t really understand the point of concepts. The name of your custom concept makes me even more concerned.

Concepts are not merely about syntactic constraints. They are about semantic constraints. Syntax is used as a plausible way to check for semantics, but don’t mistake the trees for the forest.

Let me try to make that concrete. Suppose I created a type that had operator==, operator<, and operator>, all returning bool… but each of them just returned a random bool value each time they were called. Now, is that the kind of type that is supposed to be used with MinMaxStack? Note that I didn’t ask if it would work. Syntactically it would work just fine. It would compile without a squeak, and run without any UB. But… would a MinMaxStack stack of that type… make any sense?

I think it wouldn’t make sense. Which means that whatever it is you want from the T in a MinMaxStack<T>, it has to be more than just having operator==, operator<, and operator>, all returning bool. In order for MinMaxStack<T> to make any sense, T must be ordered. You can’t have a “min” or a “max” of something that is not ordered. In order for MinMaxStack<T> to work, T has to be ordered, and that ordering has to be reflected via operator==, operator<, and operator>. In other words, t1 < t2 has to be true if and only if t1 is somehow ordered “less” than t2, such that min(t1, t2) returns t1. There are further semantic requirements, too, like that if t1 < t2 is true now, it will always be true (assuming the values of don’t change); “the minimum value” can only make sense if there is only one minimum value (it’s not “a minimum value” or “the minimum values”), and that value does not change (it’s not “the current minimum value” or “the minimum value at the moment when pushed into the stack”).

So you see, there is so much more to a concept than just the syntactic checks. The syntactic checks are just a means to an end. They are not the end itself. The actual point of a concept is semantic checking. Checking syntactic capability is just checking what a type can do. That usually provides a strong clue for what that type is, which is why C++ concepts uses syntactic checking; it’s the only practical choice, because doing semantic checking would require a compiler with a strong general artificial intelligence that is literally psychic to be able to read the mind of the coder. But make no mistake, syntactic checking is just a rough and dirty mechanism to do semantic checking… which is what concepts are really about.

This is why concepts with names that end in “-able” are smelly. The classic bad example is a concept like:

template<typename T>
concept addable = requires(T a) { a + a; };

Like, what would be the use of this concept? You can do a + b with numbers, sure… but you can also do it with strings, and addition and concatenation are very different beasts. If you wrote a function sum() that took a list of addables, you would expect that function to be doing addition, not concatenation. And, by extension, you would expect that since addition is associative and commutative, that it wouldn’t matter what order the arguments were summed up in. It may be surprising for sum("a"s, "b"s) to return "ba"… but why? That’s a perfectly cromulent summation. The problem there is that sum() shouldn’t work for types whose operator+ doesn’t mean addition. addable (or “plus-able”) is meaningless. What you want is something with meaning, like a concept for number or quantity or something like that.

Now, yes, I am aware that the standard library has a bunch of concepts that are “-able” concepts. But the standard library is a very special monster. It is a very, very rare case of a library that has to be both a) super low level; and b) universally generic. If you have an operation as basic as std::copy(), I mean, there’s really not much you can constrain it with other than std::copyable. (Yes, I know that’s not actually how it is constrained (and I know std::copy() is not constrained at all; only std::ranges::copy() is), but that’s beside the point.) If you want something that should work with std::copy(), you can’t really specify much more semantic beyond just “it can be copied”.

But practically speaking, you will pretty much never write algorithms quite so low-level as the standard library algorithms. As I pointed out above, even something as “basic” as MinMaxStack has a ton of semantic requirements. You will never write concepts quite like the low-level building-block concepts of the standard library. So your concepts will never be “-able” concepts, they will always be concepts with more semantic weight.

This also implies that it should be quite rare to use the low-level “-able” concepts of the standard library by themselves. They will usually be building blocks of more advanced concepts.

I would say that the concept you have written—MinMaxComparable—is… meh. It is a “-able” concept, which is smelly, but it actually does imply some semantic meaning. It sure implies that the type is ordered, in some way. That woud suggest that a better name for the concept would be ordered; then it would be named literally what it means (and it would now make sense in other places where you want ordering, but not the maximum or minimum).

But the standard library has std::totally_ordered. What does your concept offer that std::totally_ordered does not?

Your justification is that you don’t need operator<= or operator>=, and thus the concept with “minimal requirements” is better. That is misguided.

Again, concepts are about semantics, not syntax. The absolutely wrong way to determine which concepts you need to constrain a type is to look at how the type is used, pick out all the operations, and then make/use a concept with just those opertions.

The correct way to choose a concept is to think about what CONCEPTUAL meaning(s) the type has to have. NOT which operators/interface it needs. If you get the CONCEPT (not concept, but rather the idea) of the type right, the interface will (or at least, should) be correct automatically.

Let’s put that into practice. Any type that goes into a MinMaxStack has to be ordered. Any type that is ordered has to support operator==, operator<, and operator>… but it also has to support operator<= and operator>= as well. It doesn’t make a lick of sense for a < b or a == c to work, but not a <= c. And to really hammer that point home: that is actually what you do in MinMaxStack! So your MinMaxComparable is technically insufficient!

Here’s another way of looking at it. You wrote your MinMaxComparable using the logic that you only “need” operator==, operator<, and operator> (but, again, you violated that assumption yourself!). Okay, but… that’s not actually correct. You only really need operator== and operator<. (In fact, you may only need operator<!) Instead of:

        const bool isNewMin = m_mins.empty() || v <= m_mins.top();
        const bool isNewMax = m_maxs.empty() || v >= m_maxs.top();

… you could write:

        const bool isNewMin = m_mins.empty() || v < m_mins.top() || v == m_mins.top();
        const bool isNewMax = m_maxs.empty() || (not (v < m_maxs.top()));

… or something similar.

You could then make a concept that only requires operator== and operator<.

However, that is misguided. Just because you can get away with only those minimal operations, doesn’t mean you should. (Again, the standard library is a special monster. It does define things like std::sort() to only use operator<, for maximal universal genericity. You can technically sort things that are not only not ordered, but that it technically doesn’t even make sense to conceptualize as “sortable”.)

If instead you used a concept that means “ordered”, then you could use just the minimal set of operator== and operator<… which requires the extra equality check and or, and extra not, in the example above… or you could other operations that may be more efficient. In other words, if you constrain on the kind of type you need to support—ordered types—rather than the minimal operations you need, then you are not restricted to that minimal set of operations. You can use other operations that should be supported by any ordered type, and get a more efficient implementation.

So using a concept that has semantic meaning—rather than just syntactic—means your stack can be more efficient.

There is one more wrinkle to consider. The concept you want to use for your stack is “ordered”… but is it “totally ordered”?

That is up to you to decide.

On the one hand, if you use any T that is not totally ordered in a class like MinMaxStack<T>, you can get nonsense results. For example, if you had a MinMaxStack<double>, and you pushed 1.0, 2.0, and NaN, then depdening on the internals of MinMaxStack, the min/max values could be any of (1.0, 2.0), (1.0, NaN), (NaN, 2.0), or (Nan, Nan). Which one you get could even change from one version of the class to the next, if you do any refactoring.

On the other hand, if you disallow partially-ordered types, you cannot make MinMaxStack<double>, even if the user is disciplined enough to never push NaN into it.

Put another way: Do you want your MinMaxStack to always work safely and correctly, or do you want it to be dangerous with the user responsibile not to blow their own foot off?

Here’s another consideration. std::totally_ordered implies a strict total ordering. Would you be okay with a strict weak ordering? It would mean that if you made MinMaxStack<int> and pushed 2, 2, and 3, the min/max would always be (2, 3)… but, you wouldn’t know which 2 that is. For int, it makes no difference; every 2 is 2, But for weakly-ordered types, it could be possible to distinguish between the two 2 values. And then it would raise the question of which 2 should be the minimum.

std::totally_ordered makes all of those subtle problems vanish, at the cost of being, well, strict, and not even allowing types that cause ambiguities. Is that the correct way to go? You’re the designer of the class; you decide.

If you decide on a strict total ordering, then there is just no sense in not using std::totally_ordered. If you want a weak ordering and/or a partial ordering, then you will need to make your own concept. (Or use std::strict_weak_order with the right comparator, or std::three_way_comparable with the desired category, or whatever.)

Is requires std::constructible_from<T, U> accurate for the method push()?

… sorta?

It’s not technically wrong, if that’s what you’re wondering. It will correctly work with the value category, because when you call s.push(a) (with a lvalue T), the U will be deduced as either T& or T const&, so the constraint shakes out to std::constructible_from<T, T&> or std::constructible_from<T, T const&>… which is basically checking for copy constructability. When you call s.push(std::move(a)) (with a rvalue T), the U will be deduced as T, so you get std::constructible_from<T, T>… so, basically, move construction. So, it “works”.

And, of course, it works for “converting constructors” as well. So you can do s.push(b) or s.push(std::move(b)) with any b that is not a T, and the concept will do the check that you can construct a T from either a lvalue or rvalue whatever the hell b is.

So, it “works”, but… does it really make sense?

Does it make sense to be able to push a T (lvalue or rvalue) and anything that a T can by singly-constructed from—including explicit constructors (!!!)—but not anything else, like anything a T can be constructed from, even if takes multiple arguments. Does it make sense to silently allow explicit conversions?

The standard containers usually have three functions:

push(T const&)
push(T&&)

emplace(auto&&...)

Technically, you could rewrite the two push functions using a single function, at the cost of an extra move:

push(T)

emplace(auto&&...)

And with a little template trick, you could even avoid the extra move:

template<typename U>
requires std::same_as<T, std::remove_cvref_t<U>>
push(U&&)

emplace(auto&&...)

(There’s a bit more to it than that, if you want to allow implicit conversions, but that’s getting complex. There is an easier way, described below.)

Now, theoretically, emplace() obsoletes push(), because it can do anything push() can do and more. You could, in fact, throw out push() completely, and just rename emplace() to push(). But push() is worth keeping around for two reasons.

1. Being able to do s.push() or s.push(a, b, c) is a little weird. In the first case it looks like you’re pushing nothing. In the second, it looks like you are pushing multiple things. By contrast, s.emplace() and s.emplace(a, b, c) are a little more obvious about what they’re doing.
2. s.push(a) will only work if a is a T, or if it is something that is IMPLICITLY convertible to a T. By contrast, s.emplace(a) will work even if it requires explicit construction.

The latter point is really important to what you are doing. Your formulation isn’t technically wrong… but it does hide the fact that an EXPLICIT construction may be taking place. That’s… not good. When a constructor is marked explicit, that often means the class designer is trying to protect against accidental conversions, possibly because they are potentially dangerous or expensive. You don’t want to whitewash explicit-ness away. But with your class, if I do s.push(a), I have no idea if an expensive/dangerous explicit conversion will be taking place.

You could fix that by changing your constraint from std::constructible_from<T, U> to std::convertible_to<U, T>. That would mean that only things that can be implicitly converted to T will work… which is pretty much what you want. Everything that worked properly with std::constructible_from<T, U> will continue to work, including handling all value categories correctly. But now, only things that implicitly convert to a T will be allowed. (If you want an explicit conversion, you can still do it. You just have to, well, be explicit about it. Which is kinda the point.)

Code review

template <typename T>
    requires std::totally_ordered<T>
class MinMaxStack {

I went in to a fair amount of detail about the ordered concept above, but is that really the only constraint you want?

Generally, for a container class, you don’t want to store anything that is not an object. Would MinMaxStack<int&> make sense? What about MinMaxStack<void>?

You might want to do at least requires std::totally_ordered<T> and std::is_object_v<T>, or something similar.

    using Stack = std::stack<T>;

You pretty much never want to use a std::stack as an implementation detail. std::stack is not a container; it is a container adaptor. All it does is take an existing container, and limit the interface. This limiting might make sense for a user-facing component; it would restrict the user to only do a minimal set of operations. It makes no sense whatsoever as an internal component; why would you tie your own hands? That’s just silly.

If you don’t want to give users the ability to do anything other than push or pop, then sure, use a std::stack to restrict them to those operations, because if you don’t take away their ability to do other stuff, they will. But if you don’t want to do anything other than push or pop… then just don’t.

So instead of a std::stack<T>… which is really just a limited std::deque<T>… just use a std::deque<T>. (Or, perhaps even better, a std::vector<T>.) All it means is that you do .push_back() and .pop_back() rather than just .push() or .pop(). But it gives you much more power and flexibility.

Right now you need copies of whatever you put in the internal stack in order to keep track of the minimum and maximum values. (You use secondary stacks, but technically all you need are single objects.) @TobySpeight has pointed out that this is problematic, especially for non-copyable T, and suggested you use a std::stack<T, std::list<T>> so you can just keep the iterators to the min and max values, avoiding the need for copies, which is a brilliant idea…

… except it won’t work, because you are using a std::stack. Even though there would be a std::list<T> inside of the std::stack, you can’t get at it, because std::stack has such a restricted interface. Short of inheriting from a std::stack<T, std::list<T>> (which would be a fantastically stupid idea), there is just no way to get those iterators.

The solution is simple. Don’t use the std::stack. Instead of std::stack<T, std::list<T>>, just use std::list<T>. Now you have trivial and direct access to the list’s iterators. Problem solved. Just by throwing away the std::stack.

Instead of std::stack, you can use std::list and use iterators to keep track of the min and max values, or std::vector (or std::deque) and use indices to keep track of the min and max values. Whichever you choose, efficiency, flexibility, and power all start from throwing away that damn std::stack.

    template <typename U>
        requires std::constructible_from<T, U>
    void push(U&& value) {
        T v{std::forward<U>(value)};
        
        const bool isNewMin = m_mins.empty() || v <= m_mins.top();
        const bool isNewMax = m_maxs.empty() || v >= m_maxs.top();
        
        m_data.push(std::move(v));
        
        if (isNewMin) m_mins.push(m_data.top());
        if (isNewMax) m_maxs.push(m_data.top());
    }

Let’s think about your strategy here.

You are given some value to push into your stack. So the first thing you do is construct a temporary T. You use that for a couple of boolean checks, then move-construct a new T inside of m_data, and then use the results of those boolean checks to copy m_data.top() into m_mins and/or m_maxs.

Now, does the temporary T make sense? Why not just immediately put the value directly into m_data. It’s going there regardless, right? Then, once it’s there, instead of v in those boolean checks, you just use m_data.top(). Otherwise, everything else is the same:

    template <typename U>
        requires std::constructible_from<T, U>
    void push(U&& value) {
        m_data.push(std::forward<U>(value));
        
        const bool isNewMin = m_mins.empty() || m_data.top() <= m_mins.top();
        const bool isNewMax = m_maxs.empty() || m_data.top() >= m_maxs.top();
        
        if (isNewMin) m_mins.push(m_data.top());
        if (isNewMax) m_maxs.push(m_data.top());
    }

That’s one less T object that has to be created.

private:
    Stack m_data;
    Stack m_mins;
    Stack m_maxs;
};

Using two secondary stacks to keep track of the maximum and minimum values is an interesting choice. It’s wildly inefficient, of course, but it might be just about the only way to do it so long as you’re using std::stack.

Let’s suppose you take my advice and use std::vector or std::list instead of std::stack. Let’s use std::vector as an example. Now you no longer need to memorize every min/max value as they get pushed onto the main stack. Now you just need to know the position of the min/max values within the main stack.

So let’s start with this:

template<std::totally_ordered T>
    requires std::is_object_v<T>
class MinMaxStack
{
    template <typename U>
        requires std::convertible_to<U, T>
    void push(U&& value)
    {
        // ...
    }

    void pop()
    {
        // ...
    }

    [[nodiscard]] T const* top() const noexcept
    {
        if (empty())
            return nullptr;

        return m_data.data();
    }

    [[nodiscard]] T const* getMin() const noexcept
    {
        if (empty())
            return nullptr;

        return m_data.data() + m_min;
    }

    [[nodiscard]] T const* getMax() const noexcept
    {
        if (empty())
            return nullptr;

        return m_data.data() + m_max;
    }

    [[nodiscard]] auto size() const noexcept { return m_data.size(); }

    [[nodiscard]] auto empty() const noexcept { return m_data.empty(); }

private:
    std::vector<T> m_data = {};
    std::vector<T>::size_type m_min = {};
    std::vector<T>::size_type m_max = {};
};

So now, what do we need to do in push(). Well, let’s start with the simple part: we need to add the new object to m_data:

    template <typename U>
        requires std::convertible_to<U, T>
    void push(U&& value)
    {
        m_data.emplace_back(std::forward<U>(value));

        // ...
    }

Now we need to check if the new value is a new minimum (or maximum). The catch is, there may not be an old minimum! If this is the very first thing being pushed onto the stack, then there will be no previous minimum. But if this is the very first thing pushed onto the stack, then the size of the stack must now be 1, non?

So:

    template <typename U>
        requires std::convertible_to<U, T>
    void push(U&& value)
    {
        m_data.emplace_back(std::forward<U>(value));

        if ((m_data.size() == 1u) or (m_data.back() < m_data[m_min]))
            // ???
    }

So basically, if this is the first thing in the stack (m_data.size() == 1), OR if the thing we just put on the stack is not the first thing in the stack and it is less than the previous minimum, then it is a new minimum. So what do we do now?

Well, we record its position in the stack. Since it was the last thing pushed, its position will be m_data.size() - 1:

    template <typename U>
        requires std::convertible_to<U, T>
    void push(U&& value)
    {
        m_data.emplace_back(std::forward<U>(value));

        if ((m_data.size() == 1u) or (m_data.back() < m_data[m_min]))
            m_min = m_data.size() - 1;

        // ...
    }

And now we do basically the same thing for the max value:

    template <typename U>
        requires std::convertible_to<U, T>
    void push(U&& value)
    {
        m_data.emplace_back(std::forward<U>(value));

        if ((m_data.size() == 1u) or (m_data.back() < m_data[m_min]))
            m_min = m_data.size() - 1;

        if ((m_data.size() == 1u) or (m_data.back() > m_data[m_max]))
            m_max = m_data.size() - 1;
    }

Popping is a little bit trickier, but not by much.

After we pop the value, we check to see if it was the minimum or maximum:

    void pop()
    {
        if (empty())
            return;

        m_data.pop_back();

        if ((m_min == m_data.size()) or (m_max == m_data.size()))
            // ...
    }

In other words, if the index of the min (or max) is the index of just past the last element (that is, the index of the element we just popped), then we have some readjusting to do.

To find the new min and/or max, we can use std::ranges::minmax_element() to do a single search for both the min and max in a single pass:

    void pop()
    {
        if (empty())
            return;

        m_data.pop_back();

        if ((m_min == m_data.size()) or (m_max == m_data.size()))
        {
            auto const result = std::ranges::minmax_element(m_data);

            // ...
        }
    }

std::ranges::minmax_element() returns iterators, so we use std::ranges::distance() from std::ranges::begin(m_data) to convert that to an index:

    void pop()
    {
        if (empty())
            return;

        m_data.pop_back();

        if ((m_min == m_data.size()) or (m_max == m_data.size()))
        {
            auto const result = std::ranges::minmax_element(m_data);

            m_min = std::ranges::distance(std::ranges::begin(m_data), result.min);
            m_max = std::ranges::distance(std::ranges::begin(m_data), result.max);
        }
    }

That’s all there is to it!

Note that this is not necessarily “better” than your way. The downside of what I just did is that popping can be expensive whenever you happen to pop a minimum or maximum value, because that triggers a search of all the remaining data to find the new min/max. On the other hand, pushing a new min/max the way I just did could be orders of magnitude faster than your way. There are always tradeoffs.

Another interesting thing to note is that while I did use operator< and operator> in push(), in pop() I just used std::ranges::minmax_element(). I don’t know what std::ranges::minmax_element() does internally… and I don’t care, because it (indirectly) requires std::strict_weak_order, which any kind of “ordered” concept must surely imply. (Unless you want to allow partial ordering, which, as I explained, would break things.) The actual operations done don’t really matter. All that matters is the concepts hold.