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

An alternative implementation usesstd::stack<T, std::list<T>> instead ofstd::stack<T, std::deque<T>> form_data; this won't invalidate any relevant iterators when we push or pop, thus allowingm_mins andm_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.

Theempty() test inpop() 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 theempty() tests in them.

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

template <std::totally_ordered T>

Consider providing anemplace() member function, likestd::stack. (If we usestd::list and references, this allows the use of more exoticT that need not be movable).

The main difference betweenMinMaxComparable andstd::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.

• \$\begingroup\$Yes, I should have saidpotentially three copies. Improved the wording there.\$\endgroup\$

  Toby Speight

  – Toby Speight

  2025-11-28 11:34:56 +00:00

  Commentedyesterday

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 notmerely aboutsyntactic constraints. They are aboutsemantic 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 hadoperator==,operator<, andoperator>, all returningbool… but each of them just returned a randombool value each time they were called. Now, is that the kind of type that is supposed to be used withMinMaxStack? Note that I didn’t ask if itwould work. Syntactically it would work just fine. It would compile without a squeak, and run without any UB. But… would aMinMaxStack stack of that type… make any sense?

I think it wouldn’t make sense. Which means that whatever it is you want from theT in aMinMaxStack<T>, it has to be more thanjust havingoperator==,operator<, andoperator>, all returningbool. In order forMinMaxStack<T> to make any sense,T must beordered. You can’t have a “min” or a “max” of something that is not ordered. In order forMinMaxStack<T> to work,T has to be ordered,and that ordering has to be reflected viaoperator==,operator<, andoperator>. In other words,t1 < t2 has to betrueif and only ift1 is somehow ordered “less” thant2, such thatmin(t1, t2) returnst1. There are further semantic requirements, too, like that ift1 < t2 is true now, it willalways 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 “thecurrent 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 thanjust 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 issemantic checking. Checking syntactic capability is just checking what a type cando. That usually provides a strong clue for what that typeis, which is why C++ concepts uses syntactic checking; it’s the only practical choice, because doingsemantic 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 isjust 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 doa + b with numbers, sure… but you can also do it with strings, and addition and concatenation arevery different beasts. If you wrote a functionsum() that took a list ofaddables, 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 forsum("a"s, "b"s) to return"ba"… but why? That’s a perfectly cromulent summation. The problem there is thatsum() shouldn’t work for types whoseoperator+ doesn’t meanaddition.addable (or “plus-able”) is meaningless. What you want is something withmeaning, like a concept fornumber orquantity or something like that.

Now, yes, I am aware that the standard library has abunch 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 beboth a) super low level; and b) universally generic. If you have an operation as basic asstd::copy(), I mean, there’s really not much youcan constrain it with other thanstd::copyable. (Yes, I know that’s notactually how it is constrained (and I knowstd::copy() is not constrained at all; onlystd::ranges::copy() is), but that’s beside the point.) If you want something that should work withstd::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” asMinMaxStack has aton 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 actuallydoes 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 beordered; 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 hasstd::totally_ordered. What does your concept offer thatstd::totally_ordered does not?

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

Again, concepts are aboutsemantics, 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.

Thecorrect way to choose a concept is tothink about whatCONCEPTUAL meaning(s) the type has to have.NOT which operators/interface it needs. If you get theCONCEPT (notconcept, but rather theidea) 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 aMinMaxStack has to be ordered. Any type that is ordered has to supportoperator==,operator<, andoperator>…but it also has to supportoperator<= andoperator>= as well. It doesn’t make a lick of sense fora < b or a == c to work, but nota <= c. And to really hammer that point home:that is actually what you do inMinMaxStack! So yourMinMaxComparable is technically insufficient!

Here’s another way of looking at it. You wrote yourMinMaxComparable using the logic that you only “need”operator==,operator<, andoperator> (but, again, you violated that assumption yourself!). Okay, but… that’s not actually correct. You onlyreally needoperator== andoperator<. (In fact, youmay only needoperator<!) 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 requiresoperator== andoperator<.

However, that is misguided. Just because youcan get away with only those minimal operations, doesn’t mean youshould. (Again, the standard library is a special monster. Itdoes define things likestd::sort() toonly useoperator<, 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 youcould use just the minimal set ofoperator== andoperator<… which requires the extra equality check andor, and extranot, in the example above… or you could other operations that may be more efficient. In other words, if you constrain on thekind 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 thatshould be supported by any ordered type, and get a more efficient implementation.

So using a concept that hassemantic 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 anyT that isnot totally ordered in a class likeMinMaxStack<T>, you can get nonsense results. For example, if you had aMinMaxStack<double>, and you pushed1.0,2.0, andNaN, then depdening on the internals ofMinMaxStack, 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 makeMinMaxStack<double>, even if the user is disciplined enough to never pushNaN into it.

Put another way: Do you want yourMinMaxStack 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 strictweak ordering? It would mean that if you madeMinMaxStack<int> and pushed2,2, and3, the min/max would always be(2, 3)…but, you wouldn’t knowwhich2 that is. Forint, it makes no difference; every2 is2, But for weakly-ordered types, itcould be possible to distinguish between the two2 values. And then it would raise the question ofwhich2 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 usingstd::totally_ordered. If you want a weak ordering and/or a partial ordering, then you will need to make your own concept. (Or usestd::strict_weak_order with the right comparator, orstd::three_way_comparable with the desired category, or whatever.)

Is requiresstd::constructible_from<T, U> accurate for the methodpush()?

… sorta?

It’s nottechnicallywrong, if that’s what you’re wondering. It will correctly work with the value category, because when you calls.push(a) (with a lvalueT), theU will be deduced as eitherT& orT const&, so the constraint shakes out tostd::constructible_from<T, T&> orstd::constructible_from<T, T const&>… which isbasically checking for copy constructability. When you calls.push(std::move(a)) (with a rvalueT), theU will be deduced asT, so you getstd::constructible_from<T, T>… so, basically, move construction. So, it “works”.

And, of course, it works for “converting constructors” as well. So you can dos.push(b) ors.push(std::move(b)) with anyb that isnot aT, and the concept will do the check that you can construct aT from either a lvalue or rvalue whatever the hellb is.

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

Does it make sense to be able to push aT (lvalue or rvalue)and anything that aT can by singly-constructed from—includingexplicit constructors (!!!)—butnot anything else, likeanything aT can be constructed from, even if takes multiple arguments. Does it make sense to silently allowexplicit 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() obsoletespush(), because it can do anythingpush() can do and more. You could, in fact, throw outpush() completely, and just renameemplace() topush(). Butpush() is worth keeping around for two reasons.

1. Being able to dos.push() ors.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() ands.emplace(a, b, c) are a little more obvious about what they’re doing.
2. s.push(a) will only work ifa is aT, or if it is something that isIMPLICITLY convertible to aT. 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’ttechnically wrong… but it does hide the fact that anEXPLICIT construction may be taking place. That’s… not good. When a constructor is markedexplicit, 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 whitewashexplicit-ness away. But with your class, if I dos.push(a), I have no idea if an expensive/dangerousexplicit conversion will be taking place.

You could fix that by changing your constraint fromstd::constructible_from<T, U> tostd::convertible_to<U, T>. That would mean that only things that can beimplicitly converted toT will work… which is pretty much what you want. Everything that worked properly withstd::constructible_from<T, U> will continue to work, including handling all value categories correctly. But now, only things thatimplicitly convert to aT will be allowed. (If you want anexplicit 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 theonly constraint you want?

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

You might want to do at leastrequires 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 astd::stack as an implementation detail.std::stack is not a container; it is a containeradaptor. All it does is take an existing container, andlimit 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 yourown hands? That’s just silly.

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

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

Right now you needcopies 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-copyableT, and suggested you use astd::stack<T, std::list<T>> so you can just keep theiterators 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 astd::stack. Even though there would be astd::list<T>inside of thestd::stack, you can’t get at it, becausestd::stack has such a restricted interface. Short of inheriting from astd::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 thestd::stack. Instead ofstd::stack<T, std::list<T>>, just usestd::list<T>. Now you have trivial and direct access to the list’s iterators. Problem solved. Just by throwing away thestd::stack.

Instead ofstd::stack, you can usestd::list and use iterators to keep track of the min and max values, orstd::vector (orstd::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 damnstd::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 atemporaryT. You use that for a couple of boolean checks, then move-construct anewT inside ofm_data, and then use the results of those boolean checks to copym_data.top() intom_mins and/orm_maxs.

Now, does the temporaryT make sense? Why not just immediately put the value directly intom_data. It’s going there regardless, right? Then, once it’s there, instead ofv in those boolean checks, you just usem_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 lessT 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 usingstd::stack.

Let’s suppose you take my advice and usestd::vector orstd::list instead ofstd::stack. Let’s usestd::vector as an example. Now you no longer need to memorizeevery min/max value as they get pushed onto the main stack. Now you just need to know theposition 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 inpush(). Well, let’s start with the simple part: we need to add the new object tom_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 anold 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 be1, 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 isnot the first thing in the stackand 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 bem_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 ofjust 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 usestd::ranges::minmax_element() to do a single search forboth 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 usestd::ranges::distance() fromstd::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 notnecessarily “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 ofall 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 useoperator< andoperator> inpush(), inpop() I just usedstd::ranges::minmax_element(). I don’t know whatstd::ranges::minmax_element() does internally… and I don’t care, because it (indirectly) requiresstd::strict_weak_order, which any kind of “ordered” concept must surely imply. (Unless you want to allowpartial ordering, which, as I explained, would break things.) The actual operations done don’t really matter. All that matters is the concepts hold.

• c++
• comparative-review
• stack
• c++20