我正在寻找可以解决以下用例的数据结构：
- 值是从背面插入的
- 单个值的大小是几十个字节。
- 值自然按升序顺序排序，其中一个字段是用作唯一标识符的服务器。
- 值通常会从前面删除，但也可以从密钥指定的任意位置中删除，因此查找和删除应该很快。
- 将值的连续子集复制到这种类型的新数据结构时应便宜。
- 清算应该便宜。
- 通常包含数十个或数百个值，但也可能包含数千个。
- 性能应该是一致的，因为我将其用于软实时系统。
我一直在思考Deque 辅助Deque拿着位图的辅助Deque，可用于指示删除值，但是在我坐下来代码之前，我会感谢您的建议。谢谢！
您可以尝试使用 key_type和 node<value_type>的模板参数链接的 unordered_map，并且该节点将具有以前的 next values'keys。
课程将与此相似：（含义是不完整的）
#include <unordered_map>
template<typename key, typename value>
struct linked_map {
void push_back(key key_, value value_) {
if (!is_first_last_set)
first_last.first = key_;
assert(base.find(key_) == base.end());
base[key_] = value_;
// TODO: set prev/next_node_key
first_last.second = key_;
is_first_last_set = true;
}
void erase(key key_) {
// TODO: update previous and next node's previous and next keys
base.erase(base.find(key_));
}
value &front() {
return base[first_last.first].data;
}
void pop_front() {
erase(first_last.first);
}
...
bool is_first_last_set = false;
std::pair<key,key> first_last;
struct node {
value data;
key prev_node_key,next_node_key;
};
std::unordered_map<key,std::pair<key,value>> base;
};
unordered_map是为删除的O(1)随机访问。该值中的node是保存该订单在该 unordered_map中。
我选择使用unordered_map，因为它的性能比map具有更一致的性能，因为它不必分配（在记忆被碎片或出于任何原因时分配时间更长）要插入 delete front是几个缓存误差。
我会保持简单。
要处理中间的元素删除，我会使用optional<T>。比单独的位设置更干净。与单独的bitset相比，内存成本适中，但是连续的内存似乎值得。
当您拥有键值时，我会选择一个pair< key, optional<value> >，如果删除值，我会独自留下密钥。这使搜索代码更容易。
对于双端NES，deque启动。它不是理想的，但它是书面的。双端圆向量可能会更快，但我很懒。
我会用适当的方法写入数据结构。作为第一次通行证，将其作为您想到的最简单的事情。（可能是一个分类的向量）。
然后，您可以去实现应用程序的其余部分，然后您可以查看数据结构是否是瓶颈，如果是的，请优化它。（在这一点上，您将拥有一个功能齐全的应用程序，可以用于测试不同的实现。）
考虑了这些建议，我选择了具有以下属性的Deque：
- 侵入性：这些值提供了一个可以搜索的钥匙，以及将其标记为已删除的方法，并检查是否已删除它们。
- 排序：值以键的升序存储。
- 前后元素始终不删除。
我已经将代码推到github -https：//github.com/yitzikc/instrusiveorteddeque
，也可以在下面可用：
/*
* InstrusiveSortedDeque.h
*
* Created on: Dec 4, 2016
* Author: yitzikc
*/
#ifndef UTILS_INTRUSIVESORTEDDEQUE_H_
#define UTILS_INTRUSIVESORTEDDEQUE_H_
#include <algorithm>
#include <deque>
#include <boost/iterator/filter_iterator.hpp>
namespace Utils {
// InstrusiveSortedDeque: A deque containing sorted values, which should be default constructible and supply the following types and methods:
// * typedef KeyType
// * KeyType GetKey() const;
// * IsDeleted() const; - indicating that a value should be considered as removed
// * Remove() - Designates a value as deleted.
template <typename T> // TODO: Add other template args allowing the allocator to be customized
class InstrusiveSortedDeque : public std::deque<T> {
private:
typedef std::deque<T> StdDeque;
static constexpr bool FilterPredicate(const T& value) { return ! value.IsDeleted(); }
// A default-constructible type which wraps FilterPredicate
struct FilterPredicateType {
inline bool operator() (const T& value)
{
return FilterPredicate(value);
}
};
public:
using typename StdDeque::allocator_type;
using typename StdDeque::size_type;
using typename StdDeque::pointer;
using typename StdDeque::const_pointer;
using typename StdDeque::reference;
using typename StdDeque::const_reference;
// A user-supplied key type
typedef typename T::KeyType key_type;
typedef T value_type;
// A key-type supporting quick access. Essentially a thin wrapper around indexes of the underlying deque class
class quick_key_type {
int m_index;
enum { INVALID_INDEX = -1, MIN_VALID_INDEX = 0 };
friend class InstrusiveSortedDeque;
explicit constexpr quick_key_type(int index = INVALID_INDEX)
: m_index(index)
{
}
public:
constexpr quick_key_type(const quick_key_type&) = default;
BOOST_CXX14_CONSTEXPR quick_key_type& operator=(const quick_key_type&) = default;
constexpr bool is_valid() const { return m_index >= MIN_VALID_INDEX; }
constexpr bool is_front() const { return m_index == MIN_VALID_INDEX; }
constexpr bool operator==(quick_key_type other) { return other.m_index == m_index; }
constexpr bool operator< (quick_key_type other) { return other.m_index < m_index; }
~quick_key_type() = default;
};
typedef boost::filter_iterator<FilterPredicateType, typename StdDeque::iterator> iterator;
typedef boost::filter_iterator<FilterPredicateType, typename StdDeque::const_iterator> const_iterator;
typedef boost::filter_iterator<FilterPredicateType, typename StdDeque::reverse_iterator> reverse_iterator;
typedef boost::filter_iterator<FilterPredicateType, typename StdDeque::const_reverse_iterator> const_reverse_iterator;
InstrusiveSortedDeque( const_iterator first, const_iterator last, const allocator_type& alloc = allocator_type() )
: StdDeque(first, last, alloc)
, m_nMarkedAsErased(0)
{
}
InstrusiveSortedDeque( iterator first, iterator last, const allocator_type& alloc = allocator_type() )
: StdDeque(first, last, alloc)
, m_nMarkedAsErased(0)
{
}
InstrusiveSortedDeque(const InstrusiveSortedDeque<T>& other)
: InstrusiveSortedDeque(other.cbegin(), other.cend(), other.get_allocator())
// FIXME: Aliasing the allocator might not be a good idea when we use custom allocators
{
}
template< class InputIt >
InstrusiveSortedDeque( InputIt first, InputIt last, const allocator_type& alloc = allocator_type() )
: StdDeque(MakeFilteredIter(this, first), MakeFilteredIter(this, last), alloc)
, m_nMarkedAsErased(0)
{
}
InstrusiveSortedDeque()
: StdDeque::deque()
, m_nMarkedAsErased(0)
{
}
using StdDeque::deque;
InstrusiveSortedDeque<T>& operator=(const InstrusiveSortedDeque<T>& other)
{
Clone(other);
return *this;
}
InstrusiveSortedDeque<T>& operator=(InstrusiveSortedDeque<T>&& other)
{
static_cast<StdDeque*>(this)->operator=(other);
m_nMarkedAsErased = other.m_nMarkedAsErased;
return *this;
}
// Accessors by quick_key
reference at(quick_key_type key)
{
return GetByQuickKey<reference>(this, key);
}
const_reference at(quick_key_type key) const
{
return GetByQuickKey<const_reference>(this, key);
}
reference operator[](quick_key_type key)
{
return GetByQuickKey<reference>(this, key);
}
const_reference operator[](quick_key_type key) const
{
return GetByQuickKey<const_reference>(this, key);
}
// Methods for obtaining forward iterators
iterator begin()
{
ValidateEdge(this->front());
return MakeFilteredIter(this, StdDeque::begin());
}
const_iterator begin() const
{
ValidateEdge(this->front());
return MakeFilteredIter(this, StdDeque::begin());
}
const_iterator cbegin() const
{
return begin();
}
iterator end()
{
ValidateEdge(this->back());
return MakeFilteredIter(this, StdDeque::end());
}
const_iterator end() const
{
ValidateEdge(this->back());
return MakeFilteredIter(this, StdDeque::end());
}
const_iterator cend() const
{
return end();
}
// Methods for obtaining reverse iterators
reverse_iterator rbegin()
{
ValidateEdge(this->back());
return MakeFilteredIter(this, StdDeque::rbegin());
}
const_reverse_iterator rbegin() const
{
ValidateEdge(this->back());
return MakeFilteredIter(this, StdDeque::rbegin());
}
const_reverse_iterator crbegin() const
{
return rbegin();
}
reverse_iterator rend()
{
ValidateEdge(this->front());
return MakeFilteredIter(this, StdDeque::rend());
}
const_reverse_iterator rend() const
{
ValidateEdge(this->front());
return MakeFilteredIter(this, StdDeque::rend());
}
const_reverse_iterator crend() const
{
return end();
}
iterator quick_key_to_iterator(quick_key_type qk)
{
return QuickKeyToIterator(this, qk);
}
const_iterator quick_key_to_iterator(quick_key_type qk) const
{
return QuickKeyToIterator(this, qk);
}
size_type size() const
{
const size_type baseSize = capacity();
if (baseSize <= 1) {
assert(0 == m_nMarkedAsErased);
return baseSize;
}
const ssize_t netSize = baseSize - m_nMarkedAsErased;
assert(netSize > 1);
return netSize;
}
// Size of the underlying deque
size_type capacity() const
{
return StdDeque::size();
}
// Find methods which return an iterator to the specified key using a binary search
const_iterator find(key_type k) const
{
typename StdDeque::const_iterator it;
DoFind(this, it, StdDeque::cbegin(), StdDeque::cend(), k);
return MakeFilteredIter(this, std::move(it));
}
// Find methods which return an iterator to the specified key using a binary search
iterator find(key_type k)
{
typename StdDeque::iterator it;
DoFind(this, it, StdDeque::begin(), StdDeque::end(), k);
return MakeFilteredIter(this, std::move(it));
}
// An alternate find, starts by searching at the front of the deque before trying the usual search,
// and returns a 'quick key' instead of an iterator
quick_key_type find_front(key_type userKey) const
{
if (! this->empty()) {
if (this->front().GetKey() == userKey) {
return quick_key_type(quick_key_type::MIN_VALID_INDEX);
}
else {
// TODO: cache the result that we find here, and try searching from the cached value.
typename StdDeque::const_iterator it;
if (DoFind(this, it, StdDeque::cbegin(), StdDeque::cend(), userKey)) {
return quick_key_type(it - StdDeque::cbegin());
}
}
}
return quick_key_type();
}
void erase(iterator& it)
{
erase(it.base());
return;
}
// TODO: Also implement the overload using a range.
bool erase(key_type k)
{
typename StdDeque::iterator it;
if (DoFind(this, it, StdDeque::begin(), StdDeque::end(), k)) {
return erase(it);
}
return false;
}
bool erase(quick_key_type k)
{
return erase(StdDeque::begin() + k.m_index);
}
void pop_front()
{
assert(! this->empty() && ! this->front().IsDeleted());
StdDeque::pop_front();
TrimFront();
}
void pop_back()
{
assert(! this->empty() && ! this->back().IsDeleted());
StdDeque::pop_back();
TrimBack();
}
void clear()
{
StdDeque::clear();
m_nMarkedAsErased = 0;
return;
}
void assign(const_iterator first, const_iterator last)
{
AssignFiltered(first, last);
}
void assign(iterator first, iterator last)
{
AssignFiltered(first, last);
}
template< class InputIt >
void assign( InputIt first, InputIt last )
{
AssignFiltered(MakeFilteredIter(this, first), MakeFilteredIter(this, last));
}
// Wrappers for emplace_back() and emplace_front(), which return references to the newly created values
// Note that this is incompatible with the C++ 17 interface, where emplace...() methods return iterators
// A more flexible emplace_back which will attempt to emplace at the back but will insert at the correct position
// if the new value is not in fact greater than the last value
template< typename... Args >
reference emplace_back(Args&&... args)
{
const_pointer const prevBack = this->empty() ? nullptr : & (this->back());
StdDeque::emplace_back(std::forward<Args>(args)...);
reference& back = this->back();
assert(! back.IsDeleted());
if (nullptr != prevBack) {
assert(! prevBack->IsDeleted());
if (BOOST_UNLIKELY(back.GetKey() <= prevBack->GetKey())) {
assert(back.GetKey() < prevBack->GetKey());
auto it = DoFindUnchecked(StdDeque::begin(), StdDeque::end() - 1, back.GetKey());
assert((it->GetKey() > back.GetKey()) && (& *it != &back));
auto newIt = StdDeque::emplace(it, std::move(back));
StdDeque::pop_back();
ValidateEdge(this->back());
return *newIt;
}
}
return back;
}
// TODO: Handle out-of-place values in emplace_front like in emplace_back
template< typename... Args >
reference emplace_front(Args&&... args)
{
const_pointer const prevFront = this->empty() ? nullptr : & (this->front());
StdDeque::emplace_front(std::forward<Args>(args)...);
assert(! this->front().IsDeleted());
assert( (nullptr == prevFront) ||
((! prevFront->IsDeleted()) && (this->front().GetKey() < prevFront->GetKey())));
return this->front();
}
// FIXME: Implement resize() to to maintain the invariants for m_nMarkedAsErased if it shrinks
// FIXME: Implement the other overloads of assign() to maintain the invariants for m_nMarkedAsErased
private:
typename StdDeque::size_type m_nMarkedAsErased = 0;
void TrimFront()
{
while (! this->empty() && this->front().IsDeleted()) {
StdDeque::pop_front();
--m_nMarkedAsErased;
}
return;
}
void TrimBack()
{
while (! this->empty() && this->back().IsDeleted()) {
StdDeque::pop_back();
--m_nMarkedAsErased;
}
return;
}
template <typename ThisType, typename IterType>
static bool DoFind(ThisType thisPtr, IterType& result, IterType&& beginIter, IterType&& endIter, key_type k)
{
if (! thisPtr->empty() && (k <= thisPtr->back().GetKey())) {
result = DoFindUnchecked(beginIter, endIter, k);
// FIXME: We should handle cases when endIter != StdDeque::end()
assert(result != thisPtr->StdDeque::end());
if ((result->GetKey() == k) && (endIter != result)) {
return true;
}
}
result = thisPtr->StdDeque::end();
return false;
}
template <typename IterType>
static inline auto DoFindUnchecked(IterType&& beginIter, IterType&& endIter, key_type k)
{
constexpr auto FindComp = [](const T& value, typename T::KeyType k)->bool { return value.GetKey() < k; };
return std::lower_bound(beginIter, endIter, k, FindComp);
}
void Clone(const InstrusiveSortedDeque& other)
{
StdDeque::resize(other.size()); // Pre-allocate space if necessary
constexpr auto pred = [](const value_type& r) { return ! r.IsDeleted(); };
std::copy_if(other.StdDeque::begin(), other.StdDeque::end(), StdDeque::begin(), pred);
m_nMarkedAsErased = 0;
}
template <typename RefType, typename ThisType>
static inline RefType GetByQuickKey(ThisType thisPtr, quick_key_type key)
{
return thisPtr->StdDeque::at(key.m_index);
}
template <typename ThisType>
static auto QuickKeyToIterator(ThisType thisPtr, const quick_key_type qk)
{
if (qk.is_valid()) {
auto it = thisPtr->StdDeque::begin() + qk.m_index;
if (! it->IsDeleted()) {
return MakeFilteredIter(thisPtr, std::move(it));
}
}
return MakeFilteredIter(thisPtr, thisPtr->StdDeque::end());
}
// Filter iterator wrapping implementation
template <typename ThisType, typename BaseIterType>
inline static boost::filter_iterator<FilterPredicateType, BaseIterType> MakeFilteredIter(ThisType thisPtr, BaseIterType&& baseIter)
{
return boost::make_filter_iterator<FilterPredicateType>(baseIter, thisPtr->StdDeque::end());
}
template< class InputIt >
void AssignFiltered(InputIt first, InputIt last)
{
StdDeque::assign(first, last);
m_nMarkedAsErased = 0;
}
// Validate that a value is a valid fron or back value
void ValidateEdge(const value_type& v) const
{
// Note that if the deque is empty, the reference to v might be garbage.
assert(this->empty() || ! v.IsDeleted());
}
bool erase(typename StdDeque::iterator it)
{
if (! it->IsDeleted()) {
it->Remove();
assert(it->IsDeleted());
++m_nMarkedAsErased;
TrimFront();
TrimBack();
return true;
}
else {
assert((capacity() > 1) && (m_nMarkedAsErased > 0));
ValidateEdge(this->front());
ValidateEdge(this->back());
return false;
}
}
};
} // namespace Utils
#endif /* UTILS_INTRUSIVESORTEDDEQUE_H_ */