0

私は std::map とリストを使用して、要素と関連するスコアのウィンドウ処理を追跡しています。ウィンドウがいっぱいになったら、要素をウィンドウ キューからポップして、マップから削除したいと考えています。重複する可能性があるため、マップはウィンドウ内の各要素が何回検出されたかを追跡します。また、特定のウィンドウで最小値を取得し続けることができるように、順序付きマップも使用しています。

私の問題は、予期しないときに find() が end() を返すことです。マップを繰り返し処理すると、要素が存在することがわかります。map を使用する際の対数の複雑さを犠牲にしたくありません。

tl;dr: std::map は、要素がマップにないことを示しています。手動スキャンはそうであると言います。

[編集: Bryan Chen の提案によりマップが修正されました。ありがとうございました！]

#include <cstdint>
#include <cstdio>
#include <cinttypes>
#include <map>
#include <list>
#include <vector>

#include "util.h"
#include "kmerutil.h"

namespace kpg {

struct elscore_t {
    uint64_t el_, score_;
    INLINE elscore_t(uint64_t el, uint64_t score): el_(el), score_(score) {
        LOG_ASSERT(el == el_);
        LOG_ASSERT(score == score_);
    }
    INLINE elscore_t(): el_(0), score_(0) {}
    inline bool operator <(const elscore_t &other) const {
        return score_ < other.score_ || el_ < other.el_; // Lexicographic is tie-breaker.
    }
    inline bool operator ==(const elscore_t &other) const {
        return score_ == other.score_ && el_ == other.el_; // Lexicographic is tie-breaker.
    }
    std::string to_string() const {
        return std::to_string(el_) + "," + std::to_string(score_);
    }
};

struct esq_t: public std::list<elscore_t> {
};

typedef std::map<elscore_t, unsigned> esmap_t;

class qmap_t {
    // I could make this more efficient by using pointers instead of
    // elscore_t structs.
    // *maybe* TODO
    // Could also easily templatify this module for other windowing tasks.
    esq_t list_;
#if !NDEBUG
public:
    esmap_t map_;
private:
#else
    esmap_t map_;
#endif
    const size_t wsz_;  // window size to keep
    public:
    void add(const elscore_t &el) {
        auto it(map_.upper_bound(el));
        if(it->first == el) ++it->second;
        else map_.emplace(el, 1);
    }
    void del(const elscore_t &el) {
        auto f(map_.find(el));
        if(f == map_.end()) {
            LOG_DEBUG("map failed :(\n");
            for(f = map_.begin(); f != map_.end(); ++f)
                if(f->first == el)
                    break;
        }
        LOG_ASSERT(f != map_.end());
        if(--f->second <= 0)
            map_.erase(f);
    }
    uint64_t next_value(const uint64_t el, const uint64_t score) {
        list_.emplace_back(el, score);
        LOG_ASSERT(list_.back().el_ == el);
        LOG_ASSERT(list_.back().score_ == score);
        add(list_.back());
        if(list_.size() > wsz_) {
            //fprintf(stderr, "list size: %zu. wsz: %zu\n", list_.size(), wsz_);
            //map_.del(list_.front());
            del(list_.front());
            list_.pop_front();
        }
        LOG_ASSERT(list_.size() <= wsz_);
        return list_.size() == wsz_ ? map_.begin()->first.el_: BF;
        // Signal a window that is not filled by 0xFFFFFFFFFFFFFFFF
    }
    qmap_t(size_t wsz): wsz_(wsz) {
    }
    void reset() {
        list_.clear();
        map_.clear();
    }
};

}
4

2 に答える 2

1

これは有効な厳密な弱い順序付けではありません:

return score_ < other.score_ || el_ < other.el_;

と がelscore_t(0, 1) < elscore_t(1, 0)ありelscore_t(1, 0) < elscore_t(0, 1)ます。

于 2016-11-15T03:38:43.183 に答える
0

TCが彼の答えで指摘したように、あなたoperator<は正しくありません。

std::tieを使用して辞書式比較を行うことができます

return std::tie(score_, el_) < std::tie(other.score_, other.el_);

そうでなければあなたができる

if (score_ == other.score_) {
  return el_ < other.el_; // use el_ to compare only if score_ are same
}
return score_ < other.score_;
于 2016-11-15T03:45:27.910 に答える