C++

Forum

 
Problems with understanding a c++ code

cshan223 (1)
Please help me understand the following c++ code. The following are different parts of the code that I have questions with. The complete code has 191 lines, I attached it to the end of the post.

Question1: Given a class:
1
2
3
4
5
6
7
8
9
10
 
    class ThresholdEntry
    {
    public:
        unsigned int threshold;         
        typename map_t::iterator map_iter;

        bool operator > (const ThresholdEntry & te) const {
        return threshold > te.threshold;
        }
    };


The following priority queue is declared:
1
2
3
 
    std::priority_queue<ThresholdEntry,
        std::vector<ThresholdEntry>,
        std::greater<ThresholdEntry>> compress_heap;

I learnt that std::priority_queue<int> queue means a queue sorted by the integer entries in the queue, then when you have three items in the priority_queue<typeA, typeB, typeC>, does that mean each entry in the queue has three elements with sorting priority A>B>C ?

Question2: What does std::greater<ThresholdEntry> mean in the lines above?


Question3: Given subroutines "feed":
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
 
      void feed(IntType v) {
        ++last_n;

        if((uint64_t)v == max_v) return;

        const auto iter = entries_map.upper_bound(v);

        entry & ecur = iter->second;

        const unsigned int threshold = (unsigned int)std::floor(EPS * last_n * 2);
        unsigned int tmp = ecur.g + ecur.delta;
        if(tmp < threshold)
        {
            ++(ecur.g);
        }
        else
        {
            auto iter2 = entries_map.insert(iter, std::make_pair(v, entry(1, tmp-1)));

            compress_heap.push({tmp + 1, iter2});

            while(true)
            {
                auto top_entry = compress_heap.top();
                if(top_entry.threshold > threshold)
                {
                    break;
                }

                compress_heap.pop();
              
                auto map_iter2 = top_entry.map_iter; 
                auto map_iter1 = map_iter2++; 
                assert(map_iter2 != entries_map.end());

                auto & e1 = map_iter1->second;
                auto & e2 = map_iter2->second;

                auto real_threshold = e1.g + e2.g + e2.delta;

                if(real_threshold <= threshold) {
                    e2.g += e1.g;
                    entries_map.erase(map_iter1);
                    break;
                }
                else
                {
                    top_entry.threshold = real_threshold;
                    compress_heap.push(top_entry);
                }
            }
        }
    }

The subroutine compiles ok in ubuntu(g++) but line20 generates error in VS2012:
1
2
3
4
5
6
 
Error	3	error C2661: 'std::priority_queue<_Ty,_Container,_Pr>::push' :
    no overloaded function takes 0 arguments
Error	5	error C2143: syntax error : missing ';' before '}'	
Error	4	error C2143: syntax error : missing ';' before '{'	
Error	2	error C2143: syntax error : missing ')' before '{'	
Error	6	error C2059: syntax error : ')'

It seems the compiler is expecting "_Ty, _Container, _Pr" but line20 has parameters: "tmp+1, iter2", is it the reason why error is generated? But why does it compile successfully in ubuntu?

The complete code:
 
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
 
#ifndef GK_H__
#define GK_H__

#include <map>
#include <vector>
#include <algorithm>
#include <limits>
#include <cstdint>
#include <unordered_map>
#include <queue>
#include <cassert>
#include <functional>

template<class IntType>
class GK
{
public:
    long long last_n;
    double EPS;
    uint64_t max_v;

    class entry{
    public:
        entry () { }
        entry (unsigned int _g, unsigned int _d) : g(_g), delta(_d) { }
        unsigned int g,delta;
    };

    typedef std::multimap<IntType, entry> map_t;
    map_t entries_map;
    unsigned int max_gd;

    class SummaryEntry
    {
    public:
        IntType v;
        long long g, delta;
    };
    std::vector<SummaryEntry> summary;

    GK(double eps, uint64_t max_v = std::numeric_limits<IntType>::max()) 
        :last_n(0)
        ,EPS(eps) 
        ,max_v(max_v)
    {
        entry e(1,0);
        entries_map.insert(std::make_pair(max_v, e));
    }

    void finalize () {
        summary.clear();
        summary.reserve(entries_map.size());
        SummaryEntry se;
        se.g = 0;
        max_gd = 0;
        for(auto & p : entries_map)
        {
            const auto & e = p.second;
            unsigned int gd = e.g + e.delta;
            if(gd > max_gd) max_gd = gd;

            se.v = p.first;
            se.g += e.g;
            se.delta = e.delta;
            summary.push_back(se);
        }
        max_gd /= 2;
    }

    IntType query_for_value(double rank) const
    {
        SummaryEntry se;
        se.g = rank*last_n+max_gd;
        se.delta = 0;
        auto iter = upper_bound(summary.begin(), summary.end(),
                se,
                [](const SummaryEntry & e1, const SummaryEntry & e2)->bool{
                    return (e1.g + e1.delta) < (e2.g + e2.delta);
                });

        if(iter == summary.begin())
        {
            return 0;
        }

        return (--iter)->v;
    } 
    
    class ThresholdEntry
    {
    public:
        unsigned int threshold;
        typename map_t::iterator map_iter;

        bool operator > (const ThresholdEntry & te) const {
            return threshold > te.threshold;
        }
    };

    std::priority_queue<ThresholdEntry, 
        std::vector<ThresholdEntry>, 
        std::greater<ThresholdEntry>> compress_heap;

    void feed(IntType v) {
        ++last_n;

        if((uint64_t)v == max_v) return;

        const auto iter = entries_map.upper_bound(v);

        entry & ecur = iter->second;
        const unsigned int threshold = (unsigned int)std::floor(EPS * last_n * 2);
        unsigned int tmp = ecur.g + ecur.delta;
        if(tmp < threshold)
        {
            ++(ecur.g);
        }
        else
        {
            auto iter2 = entries_map.insert(iter, std::make_pair(v, entry(1,
                tmp-1)));

            compress_heap.push({tmp + 1, iter2});

            // try to remove one
            while(true)
            {
                auto top_entry = compress_heap.top();
                if(top_entry.threshold > threshold)
                {
                    break;
                }

                compress_heap.pop();
                // check if it is true
                auto map_iter2 = top_entry.map_iter; 
                auto map_iter1 = map_iter2++; 
                assert(map_iter2 != entries_map.end());

                auto & e1 = map_iter1->second;
                auto & e2 = map_iter2->second;

                auto real_threshold = e1.g + e2.g + e2.delta;

                if(real_threshold <= threshold) {
                    e2.g += e1.g;
                    entries_map.erase(map_iter1);
                    break;
                }
                else
                {
                    top_entry.threshold = real_threshold;
                    compress_heap.push(top_entry);
                }
            }
        }
    }
};

#endif // GK_H__
Topic archived. No new replies allowed.