C++

Forum

 
Query: Priority Queue Natural ordering of strings

NovaPrimeveera (17)
Dear C++ community

I kindly want to inquire, what natural ordering strings use when being printed from a priority queue. I am questioning alphabetical natural ordering because of the following example:

priorityQueue1 = {"George", "Jim", "John", "Blake", "Kevin", "Michael"};
priorityQueue2 = {"George", "Katie", "Kevin", "Michelle", "Ryan"};

When priorityQueue1 uses the 'addAll' method on priorityQueue2. The result that is printed is:

[Blake, George, George, Jim, Kevin, Michael, John, Katie, Kevin, Michelle, Ryan]

but, if it was printed in alphabetical order than the result would be:

[Blake, George, George, Jim, John, Katie, Kevin, Kevin, Michael, Michelle, Ryan]

Any advice is much appreciated.
coder777 (8444)
The result that is printed is:
Which is certainly the wrong order.

When priorityQueue1 uses the 'addAll' method on priorityQueue2.
Since the standard priority_queue does not provide such a function, what queue do you use?

For the standard priority_queue see:

http://www.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue
lastchance (6980)
standard priority_queue does not provide such a function


Uggh. java.
Enoizat (1343)
I cannot reproduce your error:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
 
#include <functional>
#include <iostream>
#include <queue>
#include <string>
#include <vector>


template <typename T, typename U, typename V>
void
printPQ(std::priority_queue<T, U, V>& q);

template <typename T, typename U, typename V>
std::priority_queue<T, U, V>
addAll(std::priority_queue<T, U, V>& one, std::priority_queue<T, U, V>& two);


int main()
{
    std::vector<std::string> v1 = {
        "George", "Jim", "John", "Blake", "Kevin", "Michael"
    };
    std::priority_queue < std::string,
                          std::vector<std::string>,
                          std::greater<std::string> > q1(std::greater<std::string>(),
                                                         v1);
    auto q1_bkp { q1 };
    std::cout << "q1:\n";
    printPQ(q1_bkp);
    std::cout << "\n\n";

    std::vector<std::string> v2 {
        "George", "Katie", "Kevin", "Michelle", "Ryan"
    };
    std::priority_queue < std::string,
                          std::vector<std::string>,
                          std::greater<std::string> > q2(std::greater<std::string>(),
                                                         v2);
    auto q2_bkp { q2 };
    std::cout << "q2:\n";
    printPQ(q2_bkp);
    std::cout << "\n\n";

    addAll(q1, q2);
    std::cout << "q1 + q2:\n";
    printPQ(q1);
    std::cout << "\n\nFrom higher to lower:\n";

    std::priority_queue <std::string> q3;
    for(const std::string& e : v1) {
        q3.push(e);
    }
    auto q3_bkp { q3 };
    std::cout << "q3:\n";
    printPQ(q3_bkp);
    std::cout << "\n\n";

    std::priority_queue<std::string> q4;
    for(const std::string& e : v2) {
        q4.push(e);
    }
    auto q4_bkp { q4 };
    std::cout << "q4:\n";
    printPQ(q4_bkp);
    std::cout << "\n\n";

    addAll(q3, q4);
    std::cout << "q3 + q4:\n";
    printPQ(q3);
    std::cout << "\n\n";
}


template <typename T, typename U, typename V>
void
printPQ(std::priority_queue<T, U, V>& q)
{
    while(!q.empty()) {
        std::cout << q.top() << ' ';
        q.pop();
    }
}


template <typename T, typename U, typename V>
std::priority_queue<T, U, V>
addAll(std::priority_queue<T, U, V>& one, std::priority_queue<T, U, V>& two)
{
    while(!two.empty()) {
        one.push(two.top());
        two.pop();
    }
    return one;
}


Output:
q1:
Blake George Jim John Kevin Michael

q2:
George Katie Kevin Michelle Ryan

q1 + q2:
Blake George George Jim John Katie Kevin Kevin Michael Michelle Ryan

From higher to lower:
q3:
Michael Kevin John Jim George Blake

q4:
Ryan Michelle Kevin Katie George

q3 + q4:
Ryan Michelle Michael Kevin Kevin Katie John Jim George George Blake


Please provide an example code.
NovaPrimeveera (17)
The queue I used was a a priority queue. The original code is in Java, that is why I never post it but for reference the code is the following:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
public static void main(String[] args) {
	
			 PriorityQueue<String> queue1 = new PriorityQueue<String>(Arrays.asList(
			 new String[]{"George", "Jim", "John", "Blake", "Kevin", "Michael"}));
			 
			 PriorityQueue<String> queue2 = new PriorityQueue<String>(Arrays.asList(
			 new String[] {"George", "Katie", "Kevin", "Michelle", "Ryan"}));
			 
			
			 System.out.println("The first output is: " + queue1);
			 
			 queue1 = new PriorityQueue<String>(Arrays.asList(
			 new String[]{"George", "Jim", "John", "Blake", "Kevin", "Michael"}));
			 
			 queue1.removeAll(queue2);
			 System.out.println("The second output is: " + queue1);

			 queue1 = new PriorityQueue<String>(Arrays.asList(
			 new String[]{"George", "Jim", "John", "Blake", "Kevin", "Michael"}));
			 
			 queue1.retainAll(queue2);
			 System.out.println("The third output is " + queue1);

	}
coder777 (8444)
@Enoizat

Your code shows also why using auto is not always a good idea: With cpp.sh it doesn't compile because it assumes a wrong type initializer_list<...>

@ NovaPrimeveera

Where does that problem occur? It looks very much like a bug in Java?
NovaPrimeveera (17)
I think the problem occurs in this piece of code,but that is an example code given by my Professor ( my sincerest apologies for accidentally remove the ' queue1.addAll(queue2)' ) :

1
2
3
4
5
6
 
PriorityQueue<String> queue1 = new PriorityQueue<String>(Arrays.asList(new String[]{"George", "Jim", "John", "Blake", "Kevin", "Michael"}));
			 
PriorityQueue<String> queue2 = new PriorityQueue<String>(Arrays.asList(new String[] {"George", "Katie", "Kevin", "Michelle", "Ryan"}));
			 
queue1.addAll(queue2);
System.out.println("The first output is: " + queue1);


I am using Eclipse IDE.
Enoizat (1343)
coder777 wrote:
Your code shows also why using auto is not always a good idea: [...] it assumes a wrong type initializer_list<...>

Yes, sorry, I compile with the -std=c++2a option.
I think if you change from the uniform initializer {} to the ‘classic’ = it should work even with auto.

coder777 (8444)
Enoizat wrote:
I think if you change from the uniform initializer {} to the ‘classic’ = it should work even with auto.
Yes, it does. But auto does have that inherent problem of generating an unexpected type.

@NovaPrimeveera

See this:

https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html

particularly:
The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).
Strange, but that would explain the wrong output.
Enoizat (1343)
coder777 wrote:
auto does have that inherent problem of generating an unexpected type

It looks compiler dependent, doesn’t it? Actually it doesn’t seem there’s any problem from g++ 5.1.0 with -std=c++17 enabled (I’ve tested on wandbox https://wandbox.org/ ).

coder777 (8444)
It looks compiler dependent, doesn’t it?
It is. And that makes the situation even worse. So a slight change of the compiler version raises a firework of errors...

More scary are those silent error which compile due to implicit conversion, but a certain constructor is not called... and you have really no idea where to look for the cause of that subtle bug.

Therefore I recommend to minimize the use of auto.
Enoizat (1343)
coder777 wrote:
It is. And that makes the situation even worse […omissis…] So a slight change of the compiler version raises a firework of errors...

I don’t think that’s a proper description of the current situation.
It seems auto works pretty fine at least from C++17 on (but it worked fine even before, just in another way).


coder777 wrote:
More scary are those silent error which compile due to implicit conversion, but a certain constructor is not called... and you have really no idea where to look for the cause of that subtle bug.

I’m afraid I need an example.


coder777 wrote:
Therefore I recommend to minimize the use of auto.

Ok, but perhaps it’s worth mentioning there’re many other programmers who seem to appreciate auto. For example, in the C++ Core Guidelines there’s plenty of examples based on auto. I haven’t carried out a survey, but I’d say there are more examples of declarations based on auto than not.
There even are codes like:
1
2
3
4
5
6
7
8
9
10
 
auto read = [](auto& input, auto& value)
{
    input >> value;
    // check for errors
};

auto print(auto& output, const auto& value)
{
    output << value << "\n";
}


Even in 2013, Herb Sutter paid special attention to it:
https://herbsutter.com/2013/06/07/gotw-92-solution-auto-variables-part-1/
https://herbsutter.com/2013/06/13/gotw-93-solution-auto-variables-part-2/
https://herbsutter.com/2013/08/12/gotw-94-solution-aaa-style-almost-always-auto/
(AAA - Almost Always use Auto comes from Andrei Alexandrescu)

Stroustrup himself recounts he would have liked to introduce auto since 1983 (*) and uses it nearly everywhere in his The C++ Programming Language.
There is not much advantage in using auto instead of int for an expression as simple as 123. The harder the type is to write and the harder the type is to know, the more useful auto becomes. For example:
1
2
3
4
5
6
7
8
 
template<class T> void f1(vector<T>& arg)
{
    for (vector<T>::iterator p = arg.begin(); p!=arg.end(); ++p)
        *p = 7;

    for (auto p = arg.begin(); p!=arg.end(); ++p)
        *p = 7;
}

The loop using auto is the more convenient to write and the easier to read. Also, it is more resilient to code changes. For example, if I changed arg to be a list, the loop using auto would still work correctly whereas the first loop would need to be rewritten. So, unless there is a good reason not to, use auto in small scopes.

If a scope is large, mentioning a type explicitly can help localize errors. That is, compared to using a specific type, using auto can delay the detection of type errors. For example:
1
2
3
4
5
6
 
void f(double d)
{
    constexpr auto max = d+7;
    int a[max];       // error: array bound not an integer
        // ...
}

(Bjarne Stroustrup, The C++ Programming Language, Chapter 6.3.6.1. The auto Type Specifier) (bold is mine)

But perhaps it also depends on personal preferences.

- - -
(*) Bjarne Stroustrup, The C++ Programming Language, Chapter 1.4.4.1. Language Features: «Deducing the type of an object from its initializer, auto: §2.2.2, §6.3.6.1; Bjarne Stroustrup. I first designed and implemented auto in 1983 but had to remove it because of C compatibility problems.»
Topic archived. No new replies allowed.