std :: map的查找找不到，但手動掃描地圖中的元素

我使用std :: map和一個列表來跟蹤元素和相關分數的窗口。當窗口已滿時，我想從窗口隊列中彈出一個元素並將其從地圖中移除。由於可能存在重複，因此地圖會跟蹤窗口中遇到的每個元素的次數。我還使用有序地圖，以便我可以在給定的窗口中獲取最小值。std :: map的查找找不到，但手動掃描地圖中的元素

我的問題是find（）返回結束（），當它不被期望。當我遍歷地圖時，我發現元素存在。我不想犧牲使用map的對數複雜度。

tl; dr：std :: map表示元素不在地圖中。手動掃描表明它是。

[編輯：布賴恩陳的建議修復了地圖。謝謝]

#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(); 
    } 
}; 

}

來源

2016-11-15 NoSeatbelts

您應該避免從STL容器繼承，他們不是真正設計爲基類。見http://stackoverflow.com/questions/2034916/is-it-okay-to-inherit-implementation-from-stl-containers-rather-than-delegate –

這不是一個有效的嚴格的弱排序。 –

我重構了它以避免從std :: map繼承。不知何故，問題依然存在。（將更新代碼） – NoSeatbelts

正如T.C.在他的回答中指出，你的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-15 03:45:27

這不是一個有效的嚴格弱序：

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-15 03:38:43

有用且正確的評論。我接受了Bryan Chen的回答，因爲他提供了一個解決方案以及診斷問題。 – NoSeatbelts

std :: map的查找找不到，但手動掃描地圖中的元素

回答

相關問題