时间戳

首页 > 解决方案 > 固定大小的容器，其中元素被排序，并且可以提供指向 C++ 中数据的原始指针

c++ - 固定大小的容器，其中元素被排序，并且可以提供指向 C++ 中数据的原始指针

问题描述

是否有可以限制大小的 STL 容器，在其中插入元素使其保持排序并可以提供指向 C++ 中数据的原始指针，或者可以通过组装 STL 和 C++ 中的一些东西来构建它？

事实上，我正在接收实时数据（纪元 + 数据），我注意到它们并非“总是”以纪元的递增顺序发送。

我只保存 1024 个数据点来使用绘图 API 绘制它们，因此，我需要一个指向数据的双原始指针（x => epoch，y => data）。

我写了一个类，它填充了 1024 个时间和值的双精度数组。在接收到第 1023 个数据点后，缓冲区被移位以接收下一个数据点。

在下面的代码中添加排序可能会使它过于复杂，那么有更好的编码方法吗？

struct TemporalData
{
    TemporalData(const unsigned capacity) :
       m_timestamps(new double[capacity]),
       m_bsl(new double[capacity]),
       m_capacity(capacity),
       m_size(0),
       m_lastPos(capacity - 1)
    {

    }

    TemporalData(TemporalData&& moved) :
       m_capacity(moved.m_capacity),
       m_lastPos(moved.m_lastPos)
    {
       m_size     = moved.m_size;

       m_timestamps = moved.m_timestamps;
       moved.m_timestamps = nullptr;

       m_bsl = moved.m_bsl;
       moved.m_bsl = nullptr;
    }

    TemporalData(const TemporalData& copied) :
       m_capacity(copied.m_capacity),
       m_lastPos(copied.m_lastPos)
    {
       m_size     = copied.m_size;
       m_timestamps = new double[m_capacity];
       m_bsl = new double[m_capacity];

       std::copy(copied.m_timestamps, copied.m_timestamps + m_size, m_timestamps);
       std::copy(copied.m_bsl,        copied.m_bsl        + m_size, m_bsl);
    }

    TemporalData& operator=(const TemporalData& copied) = delete;
    TemporalData& operator=(TemporalData&& moved) = delete;

    inline void add(const double timestamp, const double bsl)
    {
       if (m_size >= m_capacity)
       {
          std::move(m_timestamps + 1, m_timestamps + 1 + m_lastPos, m_timestamps);
          std::move(m_bsl + 1,        m_bsl        + 1 + m_lastPos, m_bsl);

          m_timestamps[m_lastPos] = timestamp;
          m_bsl[m_lastPos] = bsl;
       }
       else
       {
          m_timestamps[m_size] = timestamp;
          m_bsl[m_size] = bsl;
          ++m_size;
       }
    }

    inline void removeDataBefore(const double ptTime)
    {
        auto itRangeToEraseEnd = std::lower_bound(m_timestamps,
                                                  m_timestamps + m_size,
                                                  ptTime);
        auto timesToEraseCount = itRangeToEraseEnd - m_timestamps;
        if (timesToEraseCount > 0)
        {
            // shift
            std::move(m_timestamps + timesToEraseCount, m_timestamps + m_size, m_timestamps);
            std::move(m_bsl        + timesToEraseCount, m_bsl        + m_size, m_bsl);

            m_size -= timesToEraseCount;
        }
    }

    inline void clear() { m_size = 0; }

    inline double* x() const { return m_timestamps; }
    inline double* y() const { return m_bsl; }
    inline unsigned size() const { return m_size; }
    inline unsigned capacity() const { return m_capacity; }

    ~TemporalData()
    {
       delete [] m_timestamps;
       delete [] m_bsl;
    }
private:
    double*  m_timestamps; // x axis
    double*  m_bsl;        // y axis
    const unsigned m_capacity;
    unsigned       m_size;
    const unsigned m_lastPos;
};

标签： c++sortingcontainers

解决方案

是否有可以限制大小的 STL 容器，插入元素使其保持排序并可以提供指向 C++ 中数据的原始指针

不，没有这样的标准容器。

还是可以通过从 STL 和 C++ 组装一些东西来构建它？

当然。

大小限制可以使用 if 语句来实现。数组可以使用指针进行迭代，并且有标准的排序算法。

我想要的是在固定大小的缓冲区（如优先级队列）中的正确位置插入元素，从它的末端开始，我认为它比推回元素然后对容器进行排序要快。

这取决于。如果一次插入多个元素，则排序具有更好的最坏情况渐近复杂度。

但是如果你一次插入一个，特别是如果元素以“大部分排序”的顺序插入，那么对于平均案例复杂度来说，简单地搜索正确的位置并插入可能会更好。

搜索可以线性进行std::find（std::lower_bound另一种选择是指数搜索，但没有标准实现。

此外，由于我有一对数据但在两个不同的缓冲区中，我不能使用 std::sort ！

尚不清楚为什么前者会暗示后者。

推荐阅读