1

Is there an STL container which size can be limited, where inserting elements keep it sorted and can provide a raw pointer to the data in C++ or can it be built by assembling some stuff from the STL and C++ ?

In fact, I'm receiving real time data (epoch + data), and I noticed that they aren't "always" sent in an increasing order of the epoch.

I only save 1024 data points to plot them with a plotting API, thus, I need a double raw pointer to the data (x => epoch, y => data).

I wrote a class that fills a 1024 double arrays of times and values. After receiving the 1023th data point, the buffer is shifted to receive the next data points.

Adding sorting to the code below, might overcomplicate it, so is there a better way to code it ?

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;
};
Aminos
  • 754
  • 1
  • 20
  • 40
  • 1
    What about `std::array`? – πάντα ῥεῖ Jul 01 '19 at 18:01
  • Concerning your first question, answer is "no". Whether it can be built, probably yes. BTW, do you mean the STL or the C++ standard library? Those are two related but different beasts. – Ulrich Eckhardt Jul 01 '19 at 18:01
  • @UlrichEckhardt both ! – Aminos Jul 01 '19 at 18:05
  • 1
    @UlrichEckhardt, no, they are the same by definition. STL means C++ Standard Library. – SergeyA Jul 01 '19 at 18:20
  • "_After receiving the 1023th data point, the buffer is shifted to receive the next data points_" - You probably do not want that. Use one pointer for writing and one for reading so you don't have to shuffle data when it reaches its capacity. – Ted Lyngmo Jul 01 '19 at 18:20
  • 2
    @SergeyA: _Technically_ Ulrich is right. The STL is _technically_ the precursor to the C++ standard library, and has subtle differences. Notably, `std::string` did not have `begin` and `end` members in the STL, but do in the standard library. https://stackoverflow.com/questions/5205491/whats-the-difference-between-stl-and-c-standard-library – Mooing Duck Jul 01 '19 at 18:25
  • @MooingDuck hm... Apparently some people think more into acronyms than I do. I stand corrected. – SergeyA Jul 01 '19 at 18:31
  • The IOStreams library and the C library were other large contributors to the first C++ standard library, later ones were strongly influenced by Boost. It's not all from the STL. – Ulrich Eckhardt Jul 01 '19 at 18:31
  • @TedLyngmo the problem is that I want to feed the plotting API with a raw pointer to the data (for X and Y axis) + the actual number of elements in the buffer. – Aminos Jul 02 '19 at 08:18
  • @Aminos I was thinking in terms of iterators. With a circular buffer the `begin()` and `end()` iterators could point anywhere in the buffer. Your `add` function could search for `upper_bound` using those iterators and only shuffle the elements needed _if_ `upper_bound` doesn't return an interator to `end()`. The same iterators could be fed to your plotting API. – Ted Lyngmo Jul 02 '19 at 08:40
  • ... correction: `upper_bound` searches `begin()` -> `end()` so you'd need to reverse it to search `end()` -> `begin()` to be effective, since the insertion point is likely to be very close to `end()`. – Ted Lyngmo Jul 02 '19 at 08:50
  • @TedLyngmo not clear at all what you are saying ! anyway, you can take a look at the solution I posted below. If the data sent by the server (that does cuda stuff and multithreading) were always sent in an ascending order, I would not be confronted with this situation. – Aminos Jul 03 '19 at 10:00
  • @Aminos If I understand that solution correctly, it's a circular buffer that will just overwrite the oldest (timestamped) entry when the buffer is at max capacity. Only if an entry with a timestamp between _first_ and _last_ in the buffer is inserted will it actually move some of the existing entries? If so, that's what I tried suggesting :) – Ted Lyngmo Jul 03 '19 at 11:02

3 Answers3

2

Is there an STL container which size can be limited, where inserting elements keep it sorted and can provide a raw pointer to the data in C++

No. There is no such standard container.

or can it be built by assembling some stuff from the STL and C++ ?

Sure.

Size limitation can be implemented using an if-statement. Arrays can be iterated using a pointer, and there is standard algorithm for sorting.

What I want is to insert the element at the right place in the fixed size buffer (like a priority queue), starting from its end, I thought it's faster than pushing back the element and then sorting the container.

It depends. If you insert multiple elements at a time, then sorting has better worst case asymptotic complexity.

But if you insert one at a time, and especially if the elements are inserted in "mostly sorted" order, then it may be better for average case complexity to simply search for the correct position, and insert.

The searching can be done linearly (std::find), which may be most efficient depending on how well the input is ordered, or using binary search (std::lower_bound family of functions), which has better worst case complexity. Yet another option is exponential search, but there is no standard implementation of that.

Moreover, as I have a paired data but in two different buffers, I can't use std::sort !

It's unclear why the former would imply the latter.

eerorika
  • 232,697
  • 12
  • 197
  • 326
  • What I want is to insert the element at the right place in the fixed size buffer (like a priority queue), starting from its end, I thought it's faster than pushing back the element and then sorting the container. – Aminos Jul 02 '19 at 08:11
  • Moreover, as I have a paired data but in two different buffers, I can't use std::sort ! – Aminos Jul 02 '19 at 08:34
  • because if you sort the "times" array, you lose the link between the time and the value which is in the other array (named "bsl" in my code snippet), m_bsl[i] is the data corresponding to the time in m_times[i], if you sort m_times[i] you lose that information (key -> value). Anyway, take a look at the answer I posted, it works very well even if it's not a pretty code. – Aminos Jul 02 '19 at 14:48
2

Is there an STL container which size can be limited, where inserting elements keep it sorted and can provide a raw pointer to the data in C++ or can it be built by assembling some stuff from the STL and C++ ?

No, but you can keep a container sorted via e.g. std::lower_bound. If the container can be accessed randomly, the insertion will be O(log(N)) in time.

After receiving the 1023th data point, the buffer is shifted to receive the next data points.

That sounds like a circular buffer. However, if you want to keep the elements sorted, it won't be a circular buffer anymore; unless you are talking about a sorted view on top of a circular buffer.

Acorn
  • 24,970
  • 5
  • 40
  • 69
  • It looks like a circular buffer but elements are inserted in such way that the buffer stay sorted. I thought it's a little bit faster than pushing back the element in the end and then sorting the container. I want to insert the element like in the insertion sort but starting from the end (insert than shift). – Aminos Jul 02 '19 at 08:15
  • I ll try to code something with std::lower_bound to insert the element in a sorted fashion. Otherwise, what I am trying to do ressembles to the plot showing CPU usage over the time but with data that is not necessarily sorted. – Aminos Jul 02 '19 at 08:38
0

Following the advice of Acorn, I wrote this (I know it's ugly but it does what I want) 

    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;
        }
    }
Aminos
  • 754
  • 1
  • 20
  • 40