d******e
发帖数: 152 | 1 请教一个C++ 的 iterator 问题。
假设有多个 streams, 找到那些至少有k 个stream 有的数。
我设了个Stream 类， 但是那个 bool move() 有问题，
iterator 到了尾部后， it != nums.end() 还是 true;
给的例子应该输出 3， 然后停止，但是运行却不是想象的。
谢谢。
#include
#include
#include
using namespace std;
class Stream{
private:
vector nums;
public:
vector::iterator it;
Stream(vector v): nums(v) {
it = nums.begin();
}
bool move(){
return it != nums.end();
}
int getValue(){
++it;
return *it;
}
};
class Comp{
public:
bool operator()(Stream& s1, Stream& s2){
return *(s1.it) > *(s2.it);
}
};
class Merge_stream{
private:
priority_queue, Comp> pq;
public:
vector find_nums(vector streams, int k){
vector res;
if (streams.size() == 0) return res;
for (int i = 0; i < streams.size(); ++i){
if (streams[i].move())
pq.push(streams[i]);
}
while (!pq.empty()){
Stream cur_s = pq.top();
pq.pop();
int cur_val = *(cur_s.it);
int count = 1;
while (cur_s.move() && cur_s.getValue() == cur_val);
if (cur_s.move())
pq.push(cur_s);
// deal with other streams with the same vals
while (!pq.empty() && cur_val == *(pq.top().it)){
++count;
Stream cur_top = pq.top();
pq.pop();
while (cur_top.move() && cur_top.getValue() == cur_val);
if (cur_top.move())
pq.push(cur_top);
}
if (count >= k)
res.push_back(cur_val);
}
return res;
}
};
int main(){
vector v1 = {1, 2, 2, 3};
vector v2 = {0, 1, 3};
vector v3 = {0, 2, 3};
Stream s1(v1);
Stream s2(v2);
int a = -1;
for (int i = 0; i < 4; ++i){
if (s2.move())
a = s2.getValue();
}
Stream s3(v3);
vector s = {s1, s2, s3};
Merge_stream m;
vector res;
res = m.find_nums(s, 3);
return 0;
} | p***o
发帖数: 1252 | 2 getValue有UB, 编译的时候把调试选项打开-D_GLIBCXX_DEBUG
【在 d******e 的大作中提到】
: 请教一个C++ 的 iterator 问题。
: 假设有多个 streams, 找到那些至少有k 个stream 有的数。
: 我设了个Stream 类， 但是那个 bool move() 有问题，
: iterator 到了尾部后， it != nums.end() 还是 true;
: 给的例子应该输出 3， 然后停止，但是运行却不是想象的。
: 谢谢。
: #include
: #include
: #include
: using namespace std;
| t**********e
发帖数: 134 | 3 When the iterator points to the last element in vector, not vector.end() in
move, the move() function returns true; then in getValue(), iterator points
to vector.end() after ++iterator, then getValue() will try to return vector.
end().
【在 d******e 的大作中提到】
: 请教一个C++ 的 iterator 问题。
: 假设有多个 streams, 找到那些至少有k 个stream 有的数。
: 我设了个Stream 类， 但是那个 bool move() 有问题，
: iterator 到了尾部后， it != nums.end() 还是 true;
: 给的例子应该输出 3， 然后停止，但是运行却不是想象的。
: 谢谢。
: #include
: #include
: #include
: using namespace std;
| m*****o
发帖数: 110 | 4 int getValue(){
return *it++;
} | d******e
发帖数: 152 | 5 Thank you very much.
in
points
vector.
【在 t**********e 的大作中提到】
: When the iterator points to the last element in vector, not vector.end() in
: move, the move() function returns true; then in getValue(), iterator points
: to vector.end() after ++iterator, then getValue() will try to return vector.
: end().
|
|
