11

I was doing some hacking today and found out that std::priority_queue does not have a clear() member function. Are there any technical reasons as to why the standards committee may have left this out?

To be clear, I am aware that it is easy to work around this via assignment:

oldPQ = std::priority_queue<int>{};

This solution is less desirable because:

  1. It requires you to repeat the type - this does not continue to work under maintenance. As @chris pointed out below, you can simplify this if you're using the default constructor, but if you have a custom comparator, this may not be possible.
  2. std::priority_queue cannot be used in a templated function that expects a clear() member function.
  3. It is generally undesirable that it does not meet the common interface provided by the other containers. In particular, everything from std::forward_list to std::unordered_map to std::string has clear(). The only other exceptions I note are std::array, for which the semantics would not make sense, and std::stack and std::queue, for which the semantics are more questionable when std::deque works without any extra effort.

One item that looks like an issue, but in practice needn't be: Because the internal container used for std::priority_queue is templated and may not have a clear() member function of its own, this creates an interesting problem, in particular it raises the question of backward compatibility. This is a non-issue because:

  1. For internal containers that do not provide clear(), as long as nobody attempts to invoke std::priority_queue::clear(), the code will continue to compile.
  2. It may still be possible with SFINAE to provide the new interface (the clear member) by calling clear() on the internal container when it's available and by repeatedly popping if it is not.

It is my opinion that this is a defect in the C++ standard. Assuming a technical discussion does not provide a strong case for why this method is omitted, I intend to pursue the creation of a standards proposal.

Edit:

Seems this is being handled in-committee (note the last post): https://groups.google.com/a/isocpp.org/forum/?fromgroups#!searchin/std-discussion/clear/std-discussion/_mYobAFBOrM/ty-2347w1T4J

http://wg21.cmeerw.net/lwg/issue2194

Mark
  • 3,806
  • 3
  • 21
  • 32
  • Shouldn't `oldPQ = {};` work? I get that the other reasons are still valid, but that doesn't require repeating the type. – chris Oct 03 '13 at 18:12
  • @chris - Good catch! Never made the connection that you could do that. – Mark Oct 03 '13 at 18:16
  • 2
    [This may be relevant](http://stackoverflow.com/questions/493774/why-dont-the-standard-c-container-adaptors-provide-a-clear-function?rq=1) – milleniumbug Oct 03 '13 at 18:23
  • 1
    `clear` is a requirement for Sequence and Associative Containers (it's required individually for those). In fact, it seems like all three container *adapters*, `stack`, `queue` and `priority_queue` don't have `clear`. – dyp Oct 03 '13 at 18:24
  • Also, in case you're wondering whether or not something is a bug: [isocpp forums -- ISO C++ Standard – Discussion](http://isocpp.org/forums). Description: "Are you wondering why a certain C++ language or library feature works the way it does? how multiple features interact? or whether you’ve found a bug in the standard?" – dyp Oct 03 '13 at 18:27
  • @milleniumbug's link makes a good bit of sense as to why `std::stack` and `std::queue` might omit `clear()`, but the argument does not seem to follow for `std::priority_queue`. In particular, to use a different data structure as a queue (say, `std::deque`), only requires limiting yourself to a subset of its features. To make a priority queue out of any other container requires considerably greater effort if using the algorithm header's various heap functions to do so. One could leverage `std::set`'s iterator properties, but this is likely not as performant in practice. – Mark Oct 03 '13 at 18:34

1 Answers1

6

The specification of container adaptors is known to be overly pedantic: since the "abstract" spec of the corresponding data structure (from some book on abstract algorithms and data structures) does not include operation clear for canonical priority queues or stacks, it is not provided in the adaptor. This indeed often makes it quite inconvenient to use these adaptors in practice.

The good news though is that the inner container member is declared inside the adaptor as a protected member of the adapter, named c. This is probably done specifically for you to be able to easily implement your own version of the adaptor: by inheriting from the standard adaptor and adding whatever member functions you want to add, including clear.

As for comparing these adaptors' interfaces with standard container interfaces... I don't think it is a valid comparison. These adaptors have never been intended to be compatible with containers in terms of interface. Quite the opposite, the purpose of these adaptors was largely to restrict the public interface of the data structure and force it into the narrow bounds of what is allowed by its canonical abstract definition.

For example, you are not allowed to iterate over the canonical stack. Stack, by definition, is not "iterable". The fact that stack adaptor disables iteration interface is a good thing. But the absence of clear certainly feels too pedantic, since it has a great practical value without looking like a big violation of the canonical interface.

AnT stands with Russia
  • 312,472
  • 42
  • 525
  • 765
  • 1
    I accept that this may have been the reasoning used, but argue that it is not sufficient. 1) `std::priority_queue` is not meant to be inherited from. Its destructor is not virtual. 2) `std::priority_queue`, for me at least, falls into a different bucket than `std::stack` and `std::queue` when it comes to what operations seem reasonable. In particular, with the latter two, one can easily ask 'well why not use `std::deque`?', there is no simple alternative for `std::priority_queue`. More precisely, `std::priority_queue` adds functionality rather than just hiding some. – Mark Oct 03 '13 at 21:47
  • 1
    @Mark: 1) In template programming inheritance is not meant to represent ISA relationships, meaning that it is completely irrelevant whether the destructor is virtual or not, 2) the fact that `c` is a *protected* member clearly and explicitly indicates that the adaptor classes *are* actually meant to be inherited from, 3) if you don't like using public inheritance in such contexts (even though there's nothing wrong with it), you can opt for private one, re-exposing the inherited members manually. – AnT stands with Russia Oct 03 '13 at 22:01
  • Destructors should either be public and virtual or protected and non-virtual; misuse exposes undefined behavior opportunities. The guidence from "C++ Coding Standards" by Herb Sutter and Andrei Alexandrescu is just as relevant on this point as it was when it was written. Template programming does not mitigate this rule, and lofty statements about an entire category do not hold up. Private inheritance is a sketchy and poor technique to express composition. I would accept that this advice may not have been known at the time the STL was crafted. As Scott Meyers likes to say "we were young." – Mark Oct 04 '13 at 02:52
  • @Mark: Not really. There's massive amount of template metaprogramming techniques critically based on purely utilitarian properties of public inheritance (CRTP being just one huge example), which completely ignore the polymorphic destruction issue. There's just no need to bring this purely classic OOP issue into the realm of template metaprogramming. "Exposes undefined behavior opportunities" is not an argument in C++ world. An ordinary division operator "exposes undefined behavior opportunities". That does not mean we should avoid it. – AnT stands with Russia Oct 04 '13 at 06:24
  • CRTP is in no way an exception to the guidance. The issues are just as real, the guidance is just as easy to follow, and there's no downside. Pick A or B, it's simple. As for undefined behavior, in general, yes, we allow plenty in the language; isn't it great that we can shoot ourselves in the foot in so many ways. If it's easy to prevent the undefined behavior at no cost, why not though? Because we like poor design? Because we want to save a few characters? Prefer failing at compile-time to undefined behavior at runtime. Assume users of your code will be foolish. – Mark Oct 05 '13 at 04:43