Giving the Arduino deques, vectors and streams with the standard template library

The Arduino IDE is extremely similar to C++, but judging from the sketches you can find on the Internet, you’d never know it. Simpler Arduino projects can make do with just toggling IO pins, reading values, and sending serial data between two points. More complex builds fall into the category of real software development, and this is where the standard Arduino IDE falls miserably short.

[Andy] saw this lack of proper libraries for more complicated pieces of software as a terrible situation and decided to do something about it. He ported the SGI Standard Template Library to bring all those fun algorithms and data structures to any AVR chip, including the Arduino.

Going over what’s included in [Andy]’s port reads just like a syllabus for an object-oriented programming class. Stacks, queues, and lists make the cut, as do strings and vectors. Also included is just about everything in the   and headers along with a few Arduino-oriented additions like a hardware serial and liquid crystal streams.

With all these objects floating around, [Andy] says it will make an impact on Flash and SRAM usage in an AVR. Still, with all the hullabaloo over faster and larger ARM micros, it’s nice to see the classic 8-bit microcontroller becoming a bit more refined.

20 thoughts on “Giving the Arduino deques, vectors and streams with the standard template library

  1. Somebody should have posted this link.

    Nevertheless, cool, but useless. I prefer using an adopted list.h ripped from linux kernel to implement queues/lists/stacks and all fancy goodies in plain C.

    And, honestly, C++ is the language I would really prefer to avoid while doing anything on bare-metal. It’s really hard to debug C++ on bare metal when things go wrong, especially with a big codebase. And when sticking to plain C, I hardly ever use gdb, since all the pitfalls are obvious.

      1. Hey dude, sorry you seem to think your precious Arduino is perfect for everything from washing machines to missile guidance, but here in the real world, I’d rather not waste tens or hundreds of instructions every call on an 8-bit (8-bit!! C++ on an 8-bit machine!! For the love of god!!) CPU for things like vtable lookups, running constructors and destructors, and other language intrinsics.

        I’m glad you think your Arduino runs at infinity MHz and can complete an infinite number of instructions per second, but that just isn’t the case, and it’s time to join us here in the real world rather than calling everyone a troll because they insult your precious, precious Arduino.

      2. @SFRH

        Constructors/destructors do not incur any overhead. You need to initialize/free data-structures in C too.

        Virtual functions do have a performance overhead, but quick grep shows that the only place this STL library has virtuals is in iostreams. So the basic data-structures have basically zero overhead compared to their C counterparts. And iostreams are bit clunky as an interface anyways, so I’d just ignore them for anything but debugging.

    1. Or even EASTL, an STL implementation designed specifically *for* systems with no disk and a fixed RAM capacity (i.e., game consoles, but the principle applies). If you’re willing to throw away a good fraction of your possible throughput on overhead from running such a high-level language on an 8-bit architecture, then EASTL will at least help mitigate part of your bad decision.

    1. Hey now, Alan, this is no place for logic, this is a place for blindly assuming the Arduino can run anything and run it well

  2. Arduino Integrated Development Environment (IDE) is similar to the programming language (C++)?

    Am I missing something here?

  3. Never in my life before now have I heard of a “deque”. Now that I’ve looked it up and know what it is, I can also say I’ve never used, or even needed one. On ANY platform, including PCs.

    Vectors and streams can be useful, but why implement something as specialized as a deque on a memory-limited MCU? Is there some actual real-world problem it best solves, that one would have significant chance of encountering on this platform?

    Really, I find simpler data structures done well, to be of more utility on small MCUs. I program PICs in C, and though obviously it has no inherent objects, I do follow object-oriented techniques. Here’s a description of an “object” I’ve written for my personal library, which I call a Virtual Ringbuffer:

    Stream-like interface. Can switch to a “virtual” write mode, where an alternate head pointer is used for writes; thus anything written in this mode is not immediately available for reading. Once in this mode, you can write, *seek*, and eventually either commit or cancel pending writes. Elegantly solves problems like writing complex packets where a length field is at the beginning, but the length isn’t easily determined in advance; the packet can be fully constructed random-access in the ringbuffer without either resorting to a wasteful intermediate buffer, or separately precomputing the actual length. Virtual reads are also supported.

    It can raise events. If an under or overflow occurs, it calls a user-supplied function, which can crash, wait, or return immediately allowing a partial transfer. Events can be also be raised if the amount of data in the buffer goes higher or lower than a certain threshold.

    Performance is excellent, despite the extra complexity, even with frequent small accesses. It precomputes and remembers the number of contiguous bytes that can be safely read/written without a collision with the opposing pointer, the end of the ringbuffer, or causing an event. This reduces the code path of the most calls to the multibyte read/write functions to only four lines: if length is <= safe length, memcpy, increase pointer, decrease safe length. Only when a collision or event is possible does it need to do anything else, and that's relatively infrequent. Since the normal code path is so short, this also makes possible an efficient inline version, that avoids the function call overhead for safe transfers. And a single-byte version too, which is even faster by avoiding memcpy overhead. Since the average speed is so good, it can often even be used in interrupts, so long as the maximum possible execution time for a transfer in worst-case scenarios doesn't cause an issue.

    I love this ringbuffer more every time I use it. I can't say I invented it, like most things I probably only reinvented it. But I've certainly never seen a ringbuffer like this out in the wild, or other clever implementations of basic structures (I've done some interesting things with doubly-linked lists too). That's the kind of thing I'd really like to see more of.

  4. What’s with all the hate? Maybe if certain PIC fans spent half the effort building and posting cool PIC projects that they do on flaming Arduino projects they would make HaD more often and they wouldn’t feel so threatened.

    So what if you use a lower level language and write more efficient code. I bet for some projects that makes or breaks it but for others it does not. Where the job wasn’t going to tax the processor anyway who is more impressive, the programmer that got the job done or the one who spent a month getting it just right?

    I don’t care if you built your project out of transistors and fat fingered in the code using dip switches. You don’t impress anyone by posting on other people’s projects how much more l33t you are. Somebody else probably built their micro out of homemade mechanical relays and coded it by touching raw wires together. They were just too mature to show up posting about how much better they are!

  5. What is with all the hate? Sure Arduino/8-bit Atmels have limited resources, but acting like you can write code of scale using C++ on one is pure ignorance. I have an entire hardware UI + mill cutting queue + mill hardware control + network and command stack running simultaneously in threads on a single one of these chips. Features don’t suck either. Such as position calibration, speed control w/reversal, manual control, and so forth. How about people learn to code efficiently before bashing others.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s