我有一個包含一組std::pair<int, int>. 對于這個資料結構，我需要兩個重要的屬性：
- 我可以快速檢查集合成員資格。
- 先進先出
因此，作為一個擁有 cppreference.com 的 C 初學者，我去了std::queue<std::unordered_set<PointUV, pointUVHash>> frontierPointsUV{};我擁有的地方，并在下面的附錄中typedef std::pair<int, int> PointUV;包含了實作。PointUVHash
我的問題是
- 這是滿足上述兩個要求的明智方法嗎？
- 如何檢查集合成員資格？我嘗試
frontierPointsUV.c.contains過設定成員資格，但出現“沒有成員”錯誤。 - 如何推送和彈出（或插入和擦除）？我試圖在任何一個容器上呼叫這些修飾符都沒有成功。
附錄 - 哈希實作
struct pointUVHash final
{
// This is a safe hashing function for pointUV because we only ever expect it to have 0 or positive ints
// in ranges well under 2**16
int operator()(const PointUV &p) const
{
return int(p.first) (int(p.second) << 16);
}
};
uj5u.com熱心網友回復：
佇列配接器需要一個有序的容器，例如 deque 或 list 才能作業。在我看來，它也已經過時了，因為它只是從底層容器中洗掉了功能，并且沒有添加任何實質內容。
您想要的是兩個保持同步的資料結構，例如 oneunordered_set<pair<int, int> >和 one deque<pair<int, int> >。看看howpair<int, int>是一個非常簡單的型別，這個組合效果最好。如果您開始處理可能希望避免重復物件和查找的更復雜型別，則將指標存盤在其中一個容器中可能是一種選擇。
無論如何，這樣的事情應該可以解決問題：
class unique_queue
{
public:
using value_type = std::pair<int, int>;
private:
struct hash: private std::hash<int>
{
std::size_t operator()(const value_type& value) const noexcept
{
if(sizeof(int) >= sizeof(std::size_t)) {
const std::hash<int>& inthash = *this;
return inthash(value.first) * 31 inthash(value.second);
}
return static_cast<std::size_t>(value.first)
<< ((sizeof(std::size_t) - sizeof(int)) * CHAR_BIT)
static_cast<std::size_t>(value.second);
}
};
using set_type = std::unordered_set<value_type, hash>;
using queue_type = std::deque<value_type>;
set_type set;
queue_type queue;
public:
bool push(const value_type& value)
{
std::pair<set_type::iterator, bool> inserted = set.insert(value);
if(! inserted.second) // equal value already contained
return false;
try {
queue.push_back(value);
} catch(...) { // provide exception safety
set.erase(inserted.first);
throw;
}
return true;
}
bool empty() const noexcept
{ return queue.empty(); }
const value_type& front() const noexcept
{ return queue.front(); }
void pop() noexcept
{
set.erase(front());
queue.pop_front();
}
bool contained(const value_type& value) const noexcept
{ return set.count(value) != 0; }
};
我保持函式語意有點接近佇列或雙端佇列提供的內容，例如，如果front()在空佇列上呼叫未定義的行為。
如果您希望佇列中有多個相等鍵，最簡單的方法是替換unordered_set<pair<int, int> >為unordered_map<pair<int, int>, size_t>以跟蹤佇列中有多少相等鍵。像這樣的東西：
class set_queue
{
public:
using value_type = std::pair<int, int>;
private:
struct hash: private std::hash<int>
{
std::size_t operator()(const value_type& value) const noexcept
{
if(sizeof(int) >= sizeof(std::size_t)) {
const std::hash<int>& inthash = *this;
return inthash(value.first) * 31 inthash(value.second);
}
return static_cast<std::size_t>(value.first)
<< ((sizeof(std::size_t) - sizeof(int)) * CHAR_BIT)
static_cast<std::size_t>(value.second);
}
};
using map_type = std::unordered_map<value_type, std::size_t, hash>;
using queue_type = std::deque<value_type>;
map_type map;
queue_type queue;
public:
bool push(const value_type& value)
{
std::pair<map_type::iterator, bool> inserted = map.emplace(value, 0);
try {
queue.push_back(value);
} catch(...) { // provide exception safety
if(inserted.second)
map.erase(inserted.first);
throw;
}
inserted.first->second = 1;
return true;
}
bool empty() const noexcept
{ return queue.empty(); }
const value_type& front() const noexcept
{ return queue.front(); }
void pop() noexcept
{
map_type::iterator refcount = map.find(front());
assert(refcount != map.end());
queue.pop_front();
refcount->second -= 1;
if(! refcount->second) // last element of same value
map.erase(refcount);
}
std::size_t count(const value_type& value) const noexcept
{
map_type::const_iterator found = map.find(value);
return found == map.end() ? 0 : found->second;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/444258.html
上一篇：C ：將元素插入到std::map<MyStruct>中，其中MyStruct只能聚合初始化并包含const唯一指標