Blog: November 2014

C++ STL for Embedded Developers

| John Hinke | Comments 13

Introduction

C++ embedded programming is very difficult. There are some limitations that are not always present in traditional programming environments such as limited memory, slower processors, and older C++ compilers. Embedded C++ programmers must typically avoid using new and delete to avoid memory fragmentation and to maximize the amount of memory that they can use for their applications. Writing C++ applications that don’t use new and delete is quite the challenge! Unfortunately this means that most of the standard C++ library is not usable. But what if we could use the STL? Wouldn’t it be nice to write something like this:

void processCANFrames(const vector<CANFrame>& frames)
{
    for(vector<CANFrame>::const_iterator frame = frames.cbegin();
                                         frame != frames.cend();
                                         ++frame)
    {
        // do something interesting with the CANFrame
    }
}

Now you can!

At E.S.R. Labs, we have many years of experience writing high-quality embedded C++ applications. We have developed a set of best-practice processes and frameworks to support writing high-quality embedded applications. One of the libraries that has been very useful is our Embedded STL (ESTL). Our ESTL looks and feels very similar to the normal C++ STL. However, our ESTL does not use new or delete and is optimized for embedded development. Our ESTL also uses only C++98 features since those are more portable to the various embedded devices we are supporting.

Rewriting the STL to avoid new and delete is a challenge. Nearly all of the container classes in the STL use new or delete in some way. This means we must change the way we think about the containers. In some cases this requires us to impose limitations on the container that are not present in the standard STL.

No new or delete

What can programmers do if they shouldn’t use new or delete? This is the tricky part. The size of a collection or the elements in the collection must be defined at development time. It cannot be done at runtime. While this might seem like an unreasonable limitation for most applications, for embedded systems it is actually quite common and leads to more robust applications.

For example if you are building an application for a car it is much better to know during development that you don’t have enough memory than to have the car application crash while the car is driving due to a random out of memory error caused by memory fragmentation. That wouldn’t be very nice and would probably be quite difficult to debug.

Design Goals

When we designed the ESTL we had the following design goals:

  • Improve the quality of our embedded C++ code.
  • An API that looked as close to the normal STL as possible to reduce the time necessary for new developers to learn our library.
  • Re-use as much of the STL as possible such as the algorithms and iterator concepts.
  • Remove implementation defined behavior.
  • Improve the debugging of embedded applications.

We wanted to provide a library that would reduce or eliminate some common development problems we had experienced such as the previously mentioned memory fragmentation issues. By also providing an API that looks and feels like a standard STL API we can reduce the learning curve for developers who are already familiar with the STL. And most importantly we wanted to eliminate any implementation defined behavior that can be quite common in the STL.

Container Overview

Our ESTL API has a good suite of STL-like containers.

  • Array
  • Sorted array
  • Forward list. An intrusive list.
  • Deque. A double-ended queue.
  • Stack
  • Queue
  • Priority Queue
  • Array map
  • Vector

There are some differences however. The forward list is an intrusive list which means that the elements in the list must inherit from a common node base class. This requirement is because we cannot use new and delete so the elements inserted into the list must contain the next pointer.

The sorted array class doesn’t exist in the STL but we added it because we found that it was a very useful class to have.

The array_map class is slightly different from a normal map. In the array map we must specify the maximum number of key elements in the map. In our case the map class is implemented as a sorted array of pairs.

Simple Example

Our first example looks at the common vector class. To avoid using new and delete we must tell the container how much space we will need in the vector. And we have to do that at compile time, not run time. We make the size of the vector part of the template signature. For example:

template <class T, size_t N> class vector;

We can then create vectors of different sizes:

vector<int, 10> aVec;
vector<int, 50> anotherVec;

The keen observer will notice that any function that accepts a vector will need to be templatized on the size_t parameter. But this seems silly since we would then need to change all of our functions to accept a size parameter. We have solved this problem in a very clever way. We have two vector classes. One is used to declare a vector while the other is for using a vector. For example:

namespace estl {
  // use this vector as parameters to functions
  template<class T> class vector { }

  namespace declare {
    // use this to declare a vector
    template<class T, size_t N> class vector : public vector<T> 
    {}
  }
}

class MyClass
{
  public:
    // use a vector of int. The size does not matter.
    void myFunction(const estl::vector<int>& vec);
  private:
    // declare a vector and specify the size.
    estl::declare::vector<int, 10> actualVec;
};

This way your code can use vectors of any size. Our vectors also support the standard iterator methods so you can continue to use the standard algorithms. All of our containers support this pattern. The data structures can be used without knowing the size of the containers. Only when you declare the container do you need to specify the size. We have placed all of the declaration classes into a declare namespace.

API Changes

We had to make a few changes to the normal STL API to make it efficient and obvious. For example in the normal STL vector there are methods that will change the capacity or size of a vector. Those methods do not make sense for a fixed-sized vector. Another example is the push_back method of the vector class. There are several subtle issues with this method when using a fixed-size vector. In the normal STL the method looks like this:

void push_back(const value_type& val);

In our embedded STL we have two methods:

void push_back(const value_type& val); // 1
value_type& push_back();               // 2

There are two reasons to have these two methods. The first method (1) is the normal STL method. It makes a copy of the parameter and adds it to the vector. But that might not always work. In embedded C++ programming a lot of objects are uncopyable. Copying objects can lead to shared pointers or confusing object ownership problems. This is why we have the second (2) method. We return a reference to the underlying object and can then set the object to the value we want.

As a reminder, the vector’s size is fixed. We cannot increase the size of the vector. What should happen if push_back is called on a full vector? In the normal STL the vector would just dynamically increase the size which would mean that new memory is allocated and the vector data is copied and the old data is deleted. These are features that are not possible in an embedded environment. In our ESTL the methods are implemented like this:

void push_back(const value_type& val)
{
  // if we are not full
  if(!full())
  {
    // copy the item
    data[size++] = val;
  }
}

value_type& push_back()
{
  // if we are full then we need to fail!
  assert(!full());
  // return a reference to the underlying item
  return data[size++];
}

We have made a decision to assert if the program calls push_back when the vector is full. This might not always be the best behavior but it was the only way to enforce safe C++ code. We felt that it would be more dangerous to return a reference to random data that might cause a crash. With the assert we would immediately know that we have done something wrong.

Conclusion

Using the STL in an embedded environment was previously not allowed due to memory management limitations. With the new E.S.R. Labs ESTL we have made it possible for developers to use STL-like data structures in their embedded applications.

Interested? Check it out on GitHub.

A good discussion can be found on Reddit.