Контейнер фиксированного размера, в котором элементы сортируются и могут предоставить необработанный указатель на данные в C ++

Question

Существует ли контейнер 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;
};

Answer 1

Существует ли контейнер STL, размер которого может быть ограничен, когда вставка элементов сохраняет его сортировку и может обеспечить необработанный указатель на данные в C ++ или он может быть собран путем сборки некоторого материала из STL и C ++?

Нет, но вы можете сохранить контейнер отсортированным, например, через. std::lower_bound. Если доступ к контейнеру возможен случайным образом, время вставки будет равно O (log (N)).

После получения 1023-й точки данных буфер смещается для получения следующих точек данных.

Звучит как круговой буфер. Однако, если вы хотите сохранить элементы отсортированными, это больше не будет циклический буфер; если вы не говорите о отсортированном виде поверх кольцевого буфера.

Answer 2

Существует ли контейнер STL, размер которого может быть ограничен, когда вставка элементов сохраняет его сортировку и может предоставить необработанный указатель на данные в C ++

Нет.Нет такого стандартного контейнера.

или он может быть собран путем сборки некоторых вещей из STL и C ++?

Конечно.

Ограничение размераможет быть реализовано с помощью оператора if.Массивы могут быть перебраны с помощью указателя, и есть стандартный алгоритм сортировки.

Я хочу вставить элемент в нужное место в буфере фиксированного размера (например, в очередь с приоритетами), начиная сс его конца я думал, что это быстрее, чем сдвинуть элемент назад и затем отсортировать контейнер.

Это зависит.Если вы вставляете несколько элементов за раз, сортировка имеет худшую асимптотическую сложность в худшем случае.

Но если вы вставляете по одному, особенно если элементы вставляются в порядке «в основном отсортированных», то это можетдля средней сложности случая лучше просто найти правильную позицию и вставить.

Поиск может быть выполнен линейно (std::find), что может быть наиболее эффективным в зависимости от того, насколько хорошо упорядочен вход, илииспользуя бинарный поиск (std::lower_bound семейство функций), который имеет лучшую сложность в худшем случае.Еще один вариант - экспоненциальный поиск, но стандартной реализации этого не существует.

Более того, поскольку у меня есть парные данные, но в двух разных буферах, я не могу использовать std :: sort!

Неясно, почему первое подразумевает второе.

Answer 3

Следуя совету Acorn, я написал это (я знаю, что это некрасиво, но делает то, что я хочу)

    inline void add(const double timestamp, const double bsl)
    {
        if (m_size >= m_capacity)
        {
            const auto insertPositionIterator = std::lower_bound(m_timestamps,
                                                                 m_timestamps + m_size,
                                                                 timestamp);
            if (insertPositionIterator == m_timestamps)
            {
                if (*insertPositionIterator == timestamp)
                {
                    m_timestamps[0] = timestamp;
                    m_bsl[0]        = bsl;
                }
                // then return...
            }
            else
            {
                const auto shiftIndex = insertPositionIterator - m_timestamps; // for data

                std::move(m_timestamps + 1, insertPositionIterator, m_timestamps);
                std::move(m_bsl        + 1, m_bsl + shiftIndex,     m_bsl);

                *(insertPositionIterator - 1) = timestamp;
                m_bsl[shiftIndex - 1]         = bsl;
            }
        }
        else
        {
            auto insertPositionIterator = std::lower_bound(m_timestamps,
                                                           m_timestamps + m_size,
                                                           timestamp);
            if (insertPositionIterator == m_timestamps + m_size)
            {
                // the new inserted element is strictly greater than the already
                // existing element or the buffer is empty, let's push it at the back
                m_timestamps[m_size] = timestamp;
                m_bsl[m_size] = bsl;
            }
            else
            {
                // the new inserted element is equal or lesser than an already
                // existing element, let's insert it at its right place
                // to keep the time buffer sorted in ascending order
                const auto shiftIndex = insertPositionIterator - m_timestamps; // for data

                // shift
                assert(insertPositionIterator == m_timestamps + shiftIndex);
                std::move_backward(insertPositionIterator, m_timestamps + m_size, m_timestamps + m_size + 1);
                std::move_backward(m_bsl + shiftIndex,     m_bsl        + m_size, m_bsl        + m_size + 1);

                *insertPositionIterator = timestamp; // or m_timestamps[shiftIndex] = timestamp;
                m_bsl[shiftIndex] = bsl;
            }

            ++m_size;
        }
    }