I am writing a C++ program where I have to maintain a list of offsets (in an array or file) and I am using a std::deque<size_t> for this. The list gets filled while reading the file, containing the positions of the last occurrences of a specifiec character - let's say 'a'. So while reading the file, everytime the character 'a' occurs I push its position to the end of the queue.
Now at some points I have to erase all entries in this list that are smaller than a given maximum size (or in other words: that are more than x bytes away from the current reading position). Since the queue is sorted (by the way it is getting created) the most simple approach would probably be to pop the elements off the queue while the value is smaller:
void remove_smaller_than(size_t minimum)
{
size_t element = my_queue.first(); // yes I know, should check if empty here too
while (element < minimum && !my_queue.empty())
{
my_queue.pop_front();
element = my_queue.first();
}
}
Now the thing is that everytime I have to do this I will have to iterate the queue from the other side (for another reason), ending at the position of the first element that is too far away. Just to clarify (because this is hard to explain), here again a short snippet:
void iterate_over_matches(size_t minimum)
{
for (auto it = my_queue.rbegin(), end = my_queue.rend(); it != end && *it > minimum; ++it)
do_something(*it);
}
(Something like that, this is only for demonstration).
So my idea was now that if I already have the iterator of the last valid (ot rather the first invalid) entry, is there a more efficient way to "clip" the deque at this position than popping all entries?
If I have a given iterator of a std::deque, is there a more efficient way to erase all elements starting at this iterator up to the end than popping them in a while loop?
While the fastest way to erase elements from std::deque is indeed the erase method, std::deque doesn't seem like an ideal data structure for your situation. Since your elements are sorted (they're ever increasing) you can find the index that you need to erase up to in O(log(n)) time. Unfortunately, std::deque::erase has O(n) complexity, so the gains of fast search are totally diminished. We can do better.
Since the elements you store in the data structure don't need to be destructed (as they are just integers), it's possible to make a data structure that erases these elements in constant time. For instance, here's a ring buffer implementation that does it:
template <typename T>
class RingBuffer
{
public:
static_assert(std::is_trivially_copyable_v<T>, "T must be trivially copyable!");
static_assert(std::is_trivially_destructible_v<T>, "T must be trivially destructable!");
RingBuffer() :
m_Items(nullptr),
m_Capacity(0),
m_StartIndex(0),
m_EndIndex(0),
m_Version(0)
{
}
RingBuffer(const RingBuffer&) = delete;
RingBuffer& operator=(const RingBuffer&) = delete;
~RingBuffer()
{
delete[] m_Items;
}
void Add(T item)
{
m_Version++;
if (m_EndIndex + 1 == m_StartIndex || (m_EndIndex >= m_StartIndex && m_EndIndex >= m_Capacity && m_StartIndex == 0))
Grow();
size_t elementIndex;
if (m_EndIndex >= m_Capacity)
{
elementIndex = 0;
m_EndIndex = 1;
}
else
{
elementIndex = m_EndIndex++;
}
m_Items[elementIndex] = std::move(item);
}
void EraseFirstN(size_t eraseCount)
{
m_Version++;
auto count = size();
assert(eraseCount <= count);
if (eraseCount == count)
{
m_StartIndex = m_EndIndex = 0;
return;
}
m_StartIndex += eraseCount;
if (m_StartIndex >= m_Capacity)
m_StartIndex -= m_Capacity;
}
size_t size() const
{
if (m_EndIndex >= m_StartIndex)
return m_EndIndex - m_StartIndex;
return m_Capacity - m_StartIndex + m_EndIndex;
}
struct Iterator : std::iterator<std::random_access_iterator_tag, T>
{
Iterator() :
m_Container(nullptr),
m_Index(0),
m_Version(0)
{
}
Iterator(RingBuffer<T>* container, size_t index, size_t version) :
m_Container(container),
m_Index(index),
m_Version(version)
{
}
Iterator& operator+=(ptrdiff_t value) { m_Index += value; return *this; }
Iterator& operator-=(ptrdiff_t value) { m_Index -= value; return *this; }
T& operator*() { assert(m_Version == m_Container->m_Version); return (*m_Container)[m_Index]; }
const T& operator*() const { assert(m_Version == m_Container->m_Version); return (*m_Container)[m_Index]; }
T* operator->() { assert(m_Version == m_Container->m_Version); return &(*m_Container)[m_Index]; }
const T* operator->() const { assert(m_Version == m_Container->m_Version); return &(*m_Container)[m_Index]; }
T& operator[](const int& index) { assert(m_Version == m_Container->m_Version); return (*m_Container)[m_Index + index]; }
const T& operator[](const int& index) const { assert(m_Version == m_Container->m_Version); return (*m_Container)[m_Index + index]; }
Iterator& operator++() { m_Index++; return *this; }
Iterator& operator--() { m_Index--; return *this; }
Iterator operator++(int) { return Iterator(m_Container, m_Index++, m_Version); }
Iterator operator--(int) { return Iterator(m_Container, m_Index--, m_Version); }
ptrdiff_t operator-(const Iterator& other) const { assert(m_Container == other.m_Container && m_Version == other.m_Version); return static_cast<ptrdiff_t>(m_Index - other.m_Index); }
Iterator operator+(const ptrdiff_t& index) const { return Iterator(m_Container, m_Index + index, m_Version); }
Iterator operator-(const ptrdiff_t& index) const { return Iterator(m_Container, m_Index - index, m_Version); }
friend Iterator operator+(const ptrdiff_t& index, const Iterator& other) { return other + index; }
friend Iterator operator-(const ptrdiff_t& index, const Iterator& other) { return Iterator(other.m_Container, index - other.m_Index, other.m_Version); }
bool operator==(const Iterator& other) const { assert(m_Container == other.m_Container && m_Version == other.m_Version); return m_Index == other,m_Index; }
bool operator!=(const Iterator& other) const { assert(m_Container == other.m_Container && m_Version == other.m_Version); return m_Index != other.m_Index; }
bool operator>(const Iterator& other) const { assert(m_Container == other.m_Container && m_Version == other.m_Version); return m_Index > other.m_Index; }
bool operator<(const Iterator& other) const { assert(m_Container == other.m_Container && m_Version == other.m_Version); return m_Index < other.m_Index; }
bool operator>=(const Iterator& other) const { assert(m_Container == other.m_Container && m_Version == other.m_Version); return m_Index >= other.m_Index; }
bool operator<=(const Iterator& other) const { assert(m_Container == other.m_Container && m_Version == other.m_Version); return m_Index <= other.m_Index; }
private:
RingBuffer<T>* m_Container;
size_t m_Index;
size_t m_Version;
};
Iterator begin()
{
return Iterator(this, 0, m_Version);
}
Iterator end()
{
return Iterator(this, size(), m_Version);
}
T& operator[](size_t index)
{
assert(index < size());
index += m_StartIndex;
if (index >= m_Capacity)
index -= m_Capacity;
return m_Items[index];
}
private:
void Grow()
{
auto newCapacity = std::max(m_Capacity * 2, m_Capacity + 4);
auto newItems = new T[newCapacity];
if (m_EndIndex >= m_StartIndex)
{
memcpy(newItems, m_Items + m_StartIndex, (m_EndIndex - m_StartIndex) * sizeof(T));
m_EndIndex = m_EndIndex - m_StartIndex;
}
else
{
memcpy(newItems, m_Items + m_StartIndex, (m_Capacity - m_StartIndex) * sizeof(T));
memcpy(newItems + m_Capacity - m_StartIndex, m_Items, m_EndIndex * sizeof(T));
m_EndIndex = m_Capacity - m_StartIndex + m_EndIndex;
}
delete[] m_Items;
m_StartIndex = 0;
m_Items = newItems;
m_Capacity = newCapacity;
}
private:
T* m_Items;
size_t m_Capacity;
size_t m_StartIndex;
size_t m_EndIndex;
size_t m_Version;
};
Erasing from this data structure is much, much faster than using std::deque. Here's the benchmarking code I used:
constexpr size_t kCount = 100 * 1000 * 1000;
size_t everIncreasingIndex = 0;
size_t elementToEraseUpTo = 5674112;
std::deque<size_t> deque;
RingBuffer<size_t> ringBuffer;
std::cout.setf(std::ios::fixed);
std::cout.precision(5);
for (size_t u = 0; u < 10; u++)
{
for (size_t i = 0; i < kCount; i++)
{
deque.push_back(everIncreasingIndex);
ringBuffer.Add(everIncreasingIndex);
everIncreasingIndex++;
}
{
Stopwatch stopwatch;
auto it = std::lower_bound(deque.begin(), deque.end(), elementToEraseUpTo);
deque.erase(deque.begin(), it);
auto elapsed = stopwatch.ElapsedSeconds();
std::cout << "std::deque took " << elapsed * 1000 << " ms." << std::endl;
}
{
Stopwatch stopwatch;
auto it = std::lower_bound(ringBuffer.begin(), ringBuffer.end(), elementToEraseUpTo);
ringBuffer.EraseFirstN(it - ringBuffer.begin());
auto elapsed = stopwatch.ElapsedSeconds();
std::cout << "Ring buffer took " << elapsed * 1000 << " ms." << std::endl;
}
elementToEraseUpTo *= 2;
}
On my machine, here are the results:
std::deque took 6.43080 ms.
Ring buffer took 0.00220 ms.
std::deque took 6.40030 ms.
Ring buffer took 0.00170 ms.
std::deque took 12.83000 ms.
Ring buffer took 0.00160 ms.
std::deque took 25.61430 ms.
Ring buffer took 0.00240 ms.
std::deque took 51.16480 ms.
Ring buffer took 0.00280 ms.
std::deque took 102.56710 ms.
Ring buffer took 0.00270 ms.
std::deque took 205.54640 ms.
Ring buffer took 0.00250 ms.
std::deque took 411.39580 ms.
Ring buffer took 0.00250 ms.
std::deque took 170.58990 ms.
Ring buffer took 0.00300 ms.
std::deque took 98.51280 ms.
Ring buffer took 0.00230 ms.