The Standard Template Library (STL) for AVR with C++ streams

Yes you did read that correctly, this post will present a port of the Standard Template Library, or STL as it’s more commonly known, to the AVR microcontrollers.

Introduction

The STL has been around forever in computing terms with copyright notices appearing in the source code as far back as 1994 and is tried and trusted by C++ programmers the world over. These days most of the STL is a part of the Standard C++ library that ships with full-size C++ compilers.

Which version?

I chose the SGI STL, released in 2000. Other versions that I considered were the GNU STL that ships built in to libstdc++ with gcc. This version was too well woven into the libstdc++ build to be easily extracted.

The other version I looked at was uSTL. This one promised to eliminate the gcc bloat and so it had potential. However I found that on the AVR platform, using the example on the uSTL webpage the code generated was 70% larger than that produced by the SGI STL so I feel somewhat justified in my choice.

Installation and configuration

The STL consists only of header files with all the source code inline. Simply download the zip file from my downloads page and unzip to a folder on your hard disk.

Users of the Arduino IDE should be careful to get the correct version. If you’re on the latest Arduino 1.0 (or more recent) IDE then you’ll need to download at least version 1.1 due to recent changes in the Arduino package detailed below.

Those of you that use Eclipse or a command line environment simply need to configure their compiler to reference the avr-stl/include directory.

If you want to use the STL from within the popular Arduino IDE then all you need to do is copy all the files in the avr-stl/include directory into the hardware/tools/avr/avr/include subdirectory of the Arduino installation. For example, on my system I would copy all the header files into here: C:Program Files (x86)\arduino-1.0.1\hardware\tools\avr\avr\include.

Configuration

Configuration is optional. You only need to change the defaults if you want to influence the STL memory management strategy.

All configuration options may be found in avr_config.h. Here’s what the default looks like.

namespace avrstl {

// default alloc-ahead for vectors. quoting from the SGI docs:
//
//   "It is crucial that the amount of growth is proportional to the current capacity(),
//    rather than a fixed constant: in the former case inserting a series of elements
//    into a vector is a linear time operation, and in the latter case it is quadratic."
//
// If this advice pertains to you, then uncomment the first line and comment out the second.
// The default here in avr-land is to assume that memory is scarce.

//	template<typename T> size_t AvrVectorAllocAhead(size_t oldSize_) { return 2*oldSize_; }
	template<typename T> size_t AvrVectorAllocAhead(size_t oldSize_) { return 20+oldSize_; }
//	template<> size_t AvrVectorAllocAhead<char>(size_t oldSize_) { return 20+oldSize_; }     // sample specialization for char

// minimum buffer size allocated ahead by a deque

	inline size_t AvrDequeBufferSize() { return 20; }

// alloc-ahead additional memory increment for strings. The default SGI implementation will add
// the old size, doubling memory each time. We don't have memory to burn, so add 20 types each time

	template<typename T> size_t AvrStringAllocAheadIncrement(size_t oldSize_) { return 20; }
}

The first section shows how you can influence how many places a vector allocates-ahead so that it has storage in the bank ready for future allocation requests. The default allocates 20 places ahead. I have shown some commented out examples of how to change this strategy both for all vectors and just for vectors that contain a particular type (char in this example).

The second and third sections show how you can control the allocate-ahead strategy for deque’s and strings. Like vectors the default is to be conservative with memory use.

Stream support

The SGI STL is quite pure in that it does not attempt to supply a streams implementation itself, instead relying on its presence in the environment. avr-libc does not provide streams, so I have provided it via a port of the streams part of the uClibc++ project. Specifically, you get:

  • ostream, istream, iostream base classes
  • The istringstream and ostringstream string streams
  • Stream iterators

Plus some bonuses if you’re a user of the Arduino platform:

  • ohserialstream, ihserialstream, iohserialstream for reading and writing from and to the hardware serial ports on the Arduino. These streams wrap an instance of the HardwareSerial class.
  • olcdstream for writing to an LCD character display (wraps an instance of LiquidCrystal).

Memory considerations

No discussion of a microcontroller STL port is complete without taking into account memory considerations. Firstly, flash memory. Your flash usage is going to depend on the templates that you use because templates take up no space until they are declared.

If all you need are the most popular templates such as string and vector then even a 16K microcontroller may be enough. If you really go to town on the containers then even a 32K controller is going to start feeling tight. Heavy users would be wise to choose an ATmega1280 (Arduino mega).

Secondly, SRAM. Again, this depends on your usage. I have made modifications (that you can customise) to ensure that the growth policy of the popular vector and string classes is suitable for 2K controllers. The complex containers such as map and set use a memory-hungry backing tree to implement their structure. You would be wise to step up to an ATmega1280 if you want to use these with lots of objects.

I have verified that all the containers are neutral in their use of dynamic memory. That is, if you declare a container, use it as much as you want and then let it go out of scope then your controller’s dynamic memory is returned to exactly the state in which it started. To do this I used the dynamic memory monitoring tools from this post. I encourage you to use these to monitor your own code.

Operators new and delete

The STL requires implementations of new, placement new and delete. If your program does not already define them then exactly one of your project .cpp files must do the following.

Recent versions of the Arduino IDE (definitely 1.0 and possibly as early as 0022) have made an attempt to support operators new and delete by supplying their own version of new.cpp that automatically gets included in every IDE build.

Unfortunately the authors have only done half a job in that they’ve forgotten to include placement new so as yet I can’t entirely get rid of this kludge, but the procedure is now slightly different for Arduino 1.0 users.

Arduino 1.0

You will have downloaded avr-stl-1.1.zip and you need to do this:

#include <pnew.cpp>

Arduino 0021 and earlier

You will have downloaded avr-stl-1.0.zip and you need to do this:

#include <new.cpp>

That will ensure that the operators are defined. Failure to do this will result in the following compiler error: undefined reference to `operator new(unsigned int, void*)’.

A summary of what’s ported

Here is a summary of what you can use from the STL with some sample code. I’m not going to go crazy on the samples here as the web is awash with STL tutorials and samples.

vector

#include <vector>


/*
 * Test std::vector
 */

struct TestVector {

	static void RunTest() {

		std::ohserialstream serial(Serial);
		std::vector<int> vec;
		std::vector<int>::const_iterator it;
		int i;

		vec.reserve(50);
		for(i=0;i<50;i++)
			vec.push_back(i);

		for(it=vec.begin();it!=vec.end();it++)
			serial << *it << std::endl;
	}

};

Dynamic memory usage for a vector is quite good as there is almost no additional overhead over and above the space required for the objects themselves. I have implemented a default allocate-ahead policy of 20 objects which you can change if you want (see later). If you have a rough idea of how many objects you are going to need then you can greatly cut down on memory resizing by calling the reserve(n) function ahead of time.

Note that I have also ported the template specialisation of vector for bool, i.e. std::vector<bool>. This is implemented as an array of single bits that is highly efficient in its memory usage.

string

#include <string>


/*
 * Test std::vector
 */

struct TestString {

	static void RunTest() {

		std::ohserialstream serial(Serial);
		std::string str;
		char c;

		for(c='A';c<='Z';c++)
			str+=c;

		serial << str << std::endl;
	}

};

std::basic_string and its wildly popular typedef std::string are both there in full. The default allocate-ahead policy is for 20 objects but you can customize that for your needs.

bitset

#include <bitset>

/*
 * Test std::bitset
 */

struct TestBitset {

	static void RunTest() {

		std::ohserialstream serial(Serial);

		std::bitset<64> mybits(0);

	// set bits 63 and 31 using
	// different methods

		mybits[63]=1;
		mybits|=0x80000000;

		serial << mybits;
	}

};

std::bitset offers a fixed size set of bits that you can operate on using familar logical operators. This class is very efficient with memory.

deque, stack, queue, priority_queue

deque, stack and queue are all ported. deque is much like a vector but has a higher SRAM overhead and for that reason I prefer vector instead. stack and queue can be declared to use vector internally instead of the default deque, and the example below shows that.

#include <stack>
#include <vector>

/*
 * Test std::stack
 */

struct TestStack {

	static void RunTest() {

		std::ohserialstream serial(Serial);
		std::stack<int,std::vector<int> > stk;
		int i;

		for(i=0;i<20;i++)
			stk.push(i);

		while(!stk.empty()) {
			serial << stk.top() << ' ';
			stk.pop();
		}

		serial << std::endl;
	}

list

#include <list>

/*
 * Test std::list
 */

struct TestList {

	static void RunTest() {

		std::ohserialstream serial(Serial);
		std::list<int> lst;
		std::list<int>::const_iterator it;
		int i;

		for(i=0;i<50;i++)
			lst.push_back(i);

		for(it=lst.begin();it!=lst.end();it++)
			serial << *it << ' ';

		serial << std::endl;
	}

};

std::list is ported and may be used as expected. The chief advantage of a list over a vector is that modifications made away from the end of the data structure are faster. Memory usage is considerably higher for a list than a vector because of the overhead of maintaining the link structures so I recommend using a vector if you have the choice, despite the fact that a vector performs allocate-ahead and a list does not.

The std::slist (single linked list) SGI extension to the standard is also ported. You can use it if you like but I have found no advantage over the standard std::list.

set, multiset, hash_set, hash_multiset

Here come the heavyweights. set and multiset are standard containers, the hashed equivalents are SGI extensions that don’t maintain sorted order within the backing tree.

These containers are not too bad on flash consumption but they do have an impact on SRAM. Consider whether you really need them, and if you do then monitor your memory consumption and make your choice of AVR device appropriately.

#include <set>

/*
 * Test std::set
 */

struct TestSet {

	static void RunTest() {

		std::ohserialstream serial(Serial);

		std::set<int> s1,s2;
		int i;

		for(i=0;i<10;i++)
			s1.insert(i);

		for(i=5;i<15;i++)
			s2.insert(i);

		std::set_intersection(
				s1.begin(),s1.end(),
				s2.begin(),s2.end(),
				std::ostream_iterator<int>(serial," "));

		serial << std::endl;
	}
};

map, multimap, hash_map, hash_multimap

More heavyweights. Behind the scenes these containers use exactly the same tree structure as the set and for that reason the same cautions regarding SRAM usage apply.

map and multimap are standard, the hash equivalents are SGI extensions and may be useful if you don’t need to maintain sorted order.

#include <map>


/*
 * Test std::map
 */

struct TestMap {

	static void RunTest() {

		std::ohserialstream serial(Serial);

		std::map<int,const char *> days;
		int i;

		days[1]="Monday";
		days[2]="Tuesday";
		days[3]="Wednesday";
		days[4]="Thursday";
		days[5]="Friday";
		days[6]="Saturday";
		days[7]="Sunday";

		for(i=1;i<7;i++)
			serial << days[i] << std::endl;
	}
};

Algorithms

Everything in the <algorithm> and <functional> headers is available. Sorting, searching etc. It’s all there. Have fun!

Arduino Extras

I added in a few extras that will make programming against some of the common Arduino classes more natural in an STL/streams environment.

Hardware serial stream

This allows you to drop the clunky println() calls and use the more elegant streams. The constructor takes an instance of a HardwareSerial class. Arduino users only have Serial. Arduino Mega users have Serial1, Serial2, Serial3. I have added std::crlf to the namespace. This will expand to the two character sequence 13,10.

#include <HardwareSerial.h>
#include <serstream>
#include <iomanip>	// for setprecision()
#include <sstream>

/*
 * Run some tests on the hardware serial stream
 */

	static void RunTest() {

		std::ohserialstream serial(Serial);

		serial.begin(9600);

		serial << "Hello world" << std::crlf
					 << "Floating point: "
					 << std::setprecision(3) << 3.14159;
	}
};

LiquidCrystal stream

This allows you to write to an LCD character display using streams.

#include <LiquidCrystal.h>
#include <lcdostream>

LiquidCrystal lcd(2,3,4,5,6,7);


/*
 * Test the LCD output stream
 */

struct TestLcdOstream {

	static void RunTest() {

		lcd.begin(20,4);

		std::olcdstream stream(lcd);

		stream << std::clear()
					 << std::move(5,1) << "Hello World";
	}

};

I have added two functions to the std namespace: clear() clears the LCD screen and move(col,row) moves the cursor to a position on the display. As you can see from the code you still need to declare an instance of LiquidCrystal and call begin() on it before you can use the stream.

Update: 17th Feb 2012

There is a bug in the STL <string> class affecting version 1.1 and below of this package. You need to download at least 1.1.1 to fix it.

The bug is easily reproduced with a simple sketch:

#include <iterator>
#include <string>

void setup() {
  std::string str("abc");
  str.find_first_not_of("a");
}

void loop() {}

The compiler will spit out a typically cryptic succession of template errors, with the key error being this one:

dependent-name 'std::basic_string::size_type' is parsed as a non-type,
but instantiation yields a type c:/program files (x86)/arduino-1.0/
hardware/tools/avr/lib/gcc/../../avr/include/string:1106: note: 
say 'typename std::basic_string::size_type' if a type is meant

Basically the STL was written a long time ago when C++ compilers were a little more forgiving around dependent types inherited from templates. These days they are rightly more strict and you are forced to explicitly say that you mean a type using the typename keyword.

If you want to fix the bug manually then it’s very easy, the solution is to modify the <string> header file on line 1107 from this:

// ------------------------------------------------------------
// Non-inline declarations.

template <class _CharT, class _Traits, class _Alloc>
const typename basic_string<_CharT,_Traits,_Alloc>::size_type
basic_string<_CharT,_Traits,_Alloc>::npos
  = (basic_string<_CharT,_Traits,_Alloc>::size_type) -1;

To this (insert the typename keyword):

// ------------------------------------------------------------
// Non-inline declarations.

template <class _CharT, class _Traits, class _Alloc>
const typename basic_string<_CharT,_Traits,_Alloc>::size_type
basic_string<_CharT,_Traits,_Alloc>::npos
  = (typename basic_string<_CharT,_Traits,_Alloc>::size_type) -1;

For background information about why this happens, click here.

  • http://N/A Kevin

    Wow! I really needed to figure out adding vectors to arduino!!! Thanks so much!!

  • http://N/A Kevin

    I tried out your STL library tonight and hit a bit of a road block. I'm getting a giant error message at the bottom of the Arduino IDE when I compile. I feel like I'm probably making a stupid mistake… Any ideas?

    <code>

    #include

    void setup() {

    std::vector vec;

    }

    void loop() {

    }

    </code>

    • http://N/A Kevin

      for some reason its not showing it in my post but I did have "vector" in angle brackets in my post.

  • http://www.foxbat.me.uk Andy Brown

    Kevin, did you remember to parameterise your 'vec' variable with the type that is going to be stored in the vector?

    For example, if you were going to store int's then you would do:

    <code>

    std::vector<int> vec;

    </code>

    A giant error message suggests that avr-gcc has found the header file because syntax errors in template code are notorious for producing very hard to read errors.

  • Blend

    hi!

    thanks a lot for this library, got very handy. I have the same problem than Kevin, massive error while compiling

    #include

    void setup() {

    std::vector vec;

    }

    void loop() {

    }

    Errors are mostly refering to stl_iterator.h…

    • Blend

      haha, same problem than kevin.. i did declare "vector" in angle brackets and the type of data I would be storing…

      • http://www.andybrown.me.uk/ws Andy Brown

        Blend, Kevin, you need to include 'iterator' before 'vector'

        This minimal sketch compiles:

         
          
        #include &amp;lt;iterator&amp;gt; 
          
        #include &amp;lt;vector&amp;gt; 
          
         
          
        void setup() { 
          
          std::vector&amp;lt;int&amp;gt; myvec; 
          
        } 
          
         
          
        void loop() { 
          
        } 
          
        
  • Dale Eason

    Thank you for the STL port. I'm having trouble however. I'm using Arduino IDE 1.0 and when I include <vector> it gives several compiler errors. All having to do with the calls to wrap. It will say that on line 517 Wrap is called with 4 arguments and that wrap takes only 2. I guess somehow it is parsing the template arguments incorretly.

    So somehow maybe I don't have the compiler setup right but of course I did nothing to setup the compiler in the first place it just came with the Arduino IDE.

    Any help would be greatly appreciated..
    Dale Eason

    • http://www.andybrown.me.uk Andy Brown

      Hi Dale,

      It's probably the<iterator> header that your missing, it's a requirement for the use of <vector>. See my reply to the two people above you with example code.

      Regards,
      - Andy

  • Dale Eason

    More info on my include vector problem. Here is the first error line in the compile
    c:/users/doeadmin/code/teensy/arduino-1.0.1/hardware/tools/avr/lib/gcc/../../avr/include/stl_vector.h:517:68: error: macro "swap" passed 4 arguments, but takes just 2

    Dale Eason

  • Adam Watson

    Hi Andy,

    Unfortunately, I'm having the same issue as above in Arduino 1.0.1. I have installed as described, and when I create a new sketch and try to compile this code (or any code that includes any of the types in the stl library):

    ——–

    #include <vector>

    void setup() {

    }

    void loop() {

    }

    ——

    I get a large compiler error:

    In file included from /Applications/Arduino.app/Contents/Resources/Java/hardware/tools/avr/bin/../lib/gcc/avr/4.3.2/../../../../avr/include/stl_algobase.h:64,
    from /Applications/Arduino.app/Contents/Resources/Java/hardware/tools/avr/bin/../lib/gcc/avr/4.3.2/../../../../avr/include/vector:31,
    from stdtest.cpp:1:
    /Applications/Arduino.app/Contents/Resources/Java/hardware/tools/avr/bin/../lib/gcc/avr/4.3.2/../../../../avr/include/stl_iterator.h:589: error: expected type-specifier before 'char_traits'
    /Applications/Arduino.app/Contents/Resources/Java/hardware/tools/avr/bin/../lib/gcc/avr/4.3.2/../../../../avr/include/stl_iterator.h:589: error: expected '>' before 'char_traits'
    /Applications/Arduino.app/Contents/Resources/Java/hardware/tools/avr/bin/../lib/gcc/avr/4.3.2/../../../../avr/include/stl_iterator.h:595: error: expected ';' before '<' token
    /Applications/Arduino.app/Contents/Resources/Java/hardware/tools/avr/bin/../lib/gcc/avr/4.3.2/../../../../avr/include/stl_iterator.h:599: error: '_Dist' does not name a type
    /Applications/Arduino.app/Contents/Resources/Java/hardware/tools/avr/bin/../lib/gcc/avr/4.3.2/../../../../avr/include/stl_iterator.h:604: error: expected `)' before '&' token
    /Applications/Arduino.app/Contents/Resources/Java/hardware/tools/avr/bin/../lib/gcc/avr/4.3.2/../../../../avr/include/stl_iterator.h:623: error: expected ';' before '*' token
    /Applications/Arduino.app/Contents/Resources/Java/hardware/tools/avr/bin/../lib/gcc/avr/4.3.2/../../../../avr/include/stl_iterator.h: In constructor 'std::istream_iterator<_Tp, _CharT, _Traits>::istream_iterator()':
    /Applications/Arduino.app/Contents/Resources/Java/hardware/tools/avr/bin/../lib/gcc/avr/4.3.2/../../../../avr/include/stl_iterator.h:603: error: class 'std::istream_iterator<_Tp, _CharT, _Traits>' does not have any field named '_M_stream'
    /Applications/Arduino.app/Contents/Resources/Java/hardware/tools/avr/bin/../lib/gcc/avr/4.3.2/../../../../avr/include/stl_iterator.h: In member function 'bool std::istream_iterator<_Tp, _CharT, _Traits>::_M_equal(const std::istream_iterator<_Tp, _CharT, _Traits>&) const':
    /Applications/Arduino.app/Contents/Resources/Java/hardware/tools/avr/bin/../lib/gcc/avr/4.3.2/../../../../avr/include/stl_iterator.h:620: error: '_M_stream' was not declared in this scope

    … and there is more, but I'll need to email it to you, since the system won't allow me to post so much text in the comments, here.

    Any ideas?

    Thanks,
    Adam

  • Adam Watson

    Ah! Ignore my last comment—for some reason I was not seeing your replies to other posts, before. I've added an include to the iterator headers and all is compiling, now.

    Thanks for the excellent work!

  • Michael

    Thanks heaps for this Andy, this will make my arduino so much easier to work with :D

  • Royce

    You have put 10 pounds of.. err.. stuff, into a 5 pound bag! Impressive!

    I'm looking forward to trying this out! Thanks for the effort!

  • Adam Watson

    Hey Andy, any chance you'll be porting this for use on the new ARM-based Due?

    • http://www.andybrown.me.uk Andy Brown

      Yes I'll do that when I get my hands on one of the boards. I'm a big fan of the ARM CPUs.

  • jims.65311

    You, sir, are an amazing individual! I just discovered this, and I am *THRILLED*. Thank You VERY MUCH for your work on this, and for making it available

  • Chris

    Thanks for making this available to the public! It is very much appreciated. However, I am experiencing some trouble with reverse iteration of vectors while using Arduino 1.0.1.

    I wrote this short test program to demonstrate:

    —-

    #include <stdlib.h>
    #include <pnew.cpp>
    #include <iterator>
    #include <vector>
    #include <serstream>

    std::vector<int> vec;

    void setup()
    {
    int i;

    vec.reserve(50);

    for(i = 0; i < 50; ++i)
    {
    vec.push_back(i);
    }

    Serial.begin(9600);

    std::vector<int>::const_reverse_iterator it;
    std::ohserialstream serial(Serial);

    // for(it = vec.rbegin(); it != std::vector<int>::const_reverse_iterator(vec.begin()); ++it)
    for(it = vec.rbegin(); it != vec.rend(); ++it)
    {
    serial << *it << std::endl;
    }
    }

    void loop(){}

    —-

    And I get the following errors:

    sketch_nov17c.cpp: In function ‘void setup()’:
    sketch_nov17c:25: error: no match for ‘operator!=’ in ‘it != std::vector<_Tp, _Alloc>::rend() [with _Tp = int, _Alloc = std::allocator<int>]()’

    —-

    I've commented out another version of the for loop where it sends the vector to serial. That version works as it should. I've also gone into the stl source and commented out the reverse_iterator rend() method (line 210 of stl_vector.h, version 1.1) and that seems to fix the problem for me, though obviously is not a real fix. At this point, I'm wondering if I've discovered a real bug or just missed something simple.

    • http://www.andybrown.me.uk Andy Brown

      Hi Chris, yes you've come across a bug in the version of gcc shipped with the Arduino. The issue is nicely summed up here:
      http://stackoverflow.com/questions/5907078/revers

      The compiler fails to select the const version of rend() even though it's clearly available. The workaround is to use the non-const reverse iterator in your code.

  • Rick

    I'm trying to implement the vector portion of this code and I keep getting some errors. Any help woyuld be greatly appreciated.

    #include <pnew.cpp>
    #include <iterator>
    #include <vector>

    void setup()
    {
    Serial.begin(57600);
    std::vector<int> vec;
    std::vector<int>::const_reverse_iterator rcit;
    std::vector<int>::const_reverse_iterator tit=vec.rend();
    int i;

    vec.reserve(50);
    for(i=0;i<50;i++)
    {
    vec.push_back(i);
    }

    for(rcit = vec.rbegin();rcit != tit ;++rcit)
    {
    Serial.println(*rcit);
    }
    }

    void loop()
    {

    }

    Error:
    In file included from BareMinimum.cpp:1:
    c:/rick work/arduino-1.0.1/hardware/tools/avr/lib/gcc/../../avr/include/pnew.cpp:12: error: declaration of 'operator new' as non-function
    c:/rick work/arduino-1.0.1/hardware/tools/avr/lib/gcc/../../avr/include/pnew.cpp:12: error: 'size_t' was not declared in this scope
    c:/rick work/arduino-1.0.1/hardware/tools/avr/lib/gcc/../../avr/include/pnew.cpp:12: error: expected primary-expression before 'void'

    • http://www.andybrown.me.uk Andy Brown

      Hi Rick,

      Please move <pnew.cpp> from being the first #include to being the last one. It shouldn't make a difference but I think the way that the Arduino IDE "pre-processes" your sketch before feeding it to the compiler is quite buggy.

      Regards,
      - Andy

      • Mike

        Hey Andy I get the error with your suggested fix:

        include iterator
        include vector
        include pnew.cpp

        size_t not declared…

        I am using ino, the command line builder.

    • http://blog.ciderspace.ch Marco

      Hi
      I'm facing the same problem/error messages when compiling my project. Tryed to play around with the includes (didn't include the pnew.cpp at all) but that didn't help. Any suggestions/solutions to that problem ?

      btw: thanks a lot for your effort in porting the stl to arduino! The crappy Arduino String forced me to take the move

      • http://blog.ciderspace.ch marco

        ok…just figured it out…..
        had to exclude the file (pnew.cpp) ffrom the build (in Eclipse). It's working now.

  • colinirwin

    Hi,
    I was trying out this port of the libraries with the latest gcc 4.7.0 and glibc 1.8.0 and found that the string example shown above, under the 17th Feb 2012 section even after applying the fix mentioned, generated an error.

    The details were as follows:

    D:\projects\eclipse\avr_stl\include/string: In instantiation of 'void std::_String_base<_Tp, _Alloc>::_M_deallocate_block() [with _Tp = char; _Alloc = std::allocator<char>]':
    D:\projects\eclipse\avr_stl\include/string:182:21: required from 'std::_String_base<_Tp, _Alloc>::~_String_base() [with _Tp = char; _Alloc = std::allocator<char>]'
    D:\projects\eclipse\avr_stl\include/string:331:16: required from 'std::basic_string<_CharT, _Traits, _Alloc>::basic_string(const _CharT*, const allocator_type&) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>; std::basic_string<_CharT, _Traits, _Alloc>::allocator_type = std::allocator<char>]'
    ../gpsdo.cpp:33:26: required from here
    D:\projects\eclipse\avr_stl\include/string:173:7: error: '_M_deallocate' was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation [-fpermissive]
    D:\projects\eclipse\avr_stl\include/string:173:7: note: declarations in dependent base 'std::_String_alloc_base<char, std::allocator<char>, true>' are not found by unqualified lookup
    D:\projects\eclipse\avr_stl\include/string:173:7: note: use 'this->_M_deallocate' instead
    make: *** [gpsdo.o] Error 1

    This was easily fixed by adding a "this->" prior to the member function "_M_deallocate" on line 173 of the file string, as the compiler error suggests. I haven't tried out anything else just yet, so there conceivably could be other instances of this change being required.

    Regardless, many thanks for making this available. Fantastic!

    Colin

  • Gionata

    Hey thank you very much for this!! Using find_if algorithm on an Arduino is wonderful!!
    But guys be careful with vectors, because of their capacity property: I found the heap memory almost full after only 2 push_back call in a very big project (big for an Arduino Uno). Correct me if I am wrong but I think that's because "vector containers may allocate some extra storage to accommodate for possible growth, and thus the container may have an actual capacity greater than the storage strictly needed to contain its elements (i.e., its size)" (http://www.cplusplus.com/reference/vector/vector/).
    Memory problems like this can be really HARD to debug, especially on a platform like Arduino!
    And thanks again Andy!

  • Yaraeovento

    Hi Andy, thank you so much for your amazing work!!!
    I have a very silly question, if you don't mind. I am using ubuntu and just couldn't copy the files to the right location. (Tried a few places, it didn't work).
    Would you by any chance know where to cp your include files to in ubuntu? Sorry…
    Once again, many many thanks!

    • http://www.andybrown.me.uk Andy Brown

      I haven't got access to my Ubuntu installation from here but I just took a look inside the Arduino Linux distro and it seems the correct location is here:

      arduino-1.0.5/hardware/tools/avr/lib/avr/include

      • Yaraeovento

        Wow, thank you so much for the quick answer! Again, congrats on the great work!

  • Gerben

    It's lovely, but it does not work.

    The problem I have is that I try to make the examples work, just by copy-pasting. And they don't work.
    From the comments I gther that I might need to include 'iterator' first. It is NOT in the example, but I tried it anyway. Didn't work.
    There is mention of including new.cpp. Again, not in the example and it doesn't work.

    I'd like to have a working example.

    Including iterator and vector, in the vector example, gives me this error:

    In file included from /usr/lib/gcc/avr/4.7.2/../../../avr/include/vector:35:0,
    from vector_test.ino:4:
    /usr/lib/gcc/avr/4.7.2/../../../avr/include/stl_vector.h: In instantiation of ‘std::_Vector_base<_Tp, _Alloc>::~_Vector_base() [with _Tp = int; _Alloc = std::allocator<int>]’:
    /usr/lib/gcc/avr/4.7.2/../../../avr/include/stl_vector.h:240:16: required from ‘std::vector<_Tp, _Alloc>::vector(const allocator_type&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<int>]’
    vector_test.ino:16:22: required from here
    /usr/lib/gcc/avr/4.7.2/../../../avr/include/stl_vector.h:117:21: error: ‘_M_deallocate’ was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation [-fpermissive]
    /usr/lib/gcc/avr/4.7.2/../../../avr/include/stl_vector.h:117:21: note: declarations in dependent base ‘std::_Vector_alloc_base<int, std::allocator<int>, true>’ are not found by unqualified lookup
    /usr/lib/gcc/avr/4.7.2/../../../avr/include/stl_vector.h:117:21: note: use ‘this->_M_deallocate’ instead

    and when I include new.cpp, I get

    In file included from vector_test.ino:2:0:
    /usr/lib/gcc/avr/4.7.2/../../../avr/include/pnew.cpp:12:20: error: declaration of ‘operator new’ as non-function
    /usr/lib/gcc/avr/4.7.2/../../../avr/include/pnew.cpp:12:20: error: ‘size_t’ was not declared in this scope
    /usr/lib/gcc/avr/4.7.2/../../../avr/include/pnew.cpp:12:33: error: expected primary-expression before ‘void’
    In file included from /usr/lib/gcc/avr/4.7.2/../../../avr/include/vector:35:0,
    from vector_test.ino:4:
    /usr/lib/gcc/avr/4.7.2/../../../avr/include/stl_vector.h: In instantiation of ‘std::_Vector_base<_Tp, _Alloc>::~_Vector_base() [with _Tp = int; _Alloc = std::allocator<int>]’:
    /usr/lib/gcc/avr/4.7.2/../../../avr/include/stl_vector.h:240:16: required from ‘std::vector<_Tp, _Alloc>::vector(const allocator_type&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<int>]’
    vector_test.ino:16:22: required from here
    /usr/lib/gcc/avr/4.7.2/../../../avr/include/stl_vector.h:117:21: error: ‘_M_deallocate’ was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation [-fpermissive]
    /usr/lib/gcc/avr/4.7.2/../../../avr/include/stl_vector.h:117:21: note: declarations in dependent base ‘std::_Vector_alloc_base<int, std::allocator<int>, true>’ are not found by unqualified lookup
    /usr/lib/gcc/avr/4.7.2/../../../avr/include/stl_vector.h:117:21: note: use ‘this->_M_deallocate’ instead

    • http://www.andybrown.me.uk Andy Brown

      Hi,Which version of the Arduino IDE are you using. The latest I have tested with is 1.0.5.Regards, – Andy

    • http://www.andybrown.me.uk Andy Brown

      Hi, from the error messages that identify gcc as 4.7.2 can I assume that you're not using a standard Arduino IDE installation? If so then please see Colin Irwin's comment above as his error messages seem to be the same as yours.

  • http://blog.ciderspace.ch marco

    Hi Any

    when using streams i get duplicated symbols for all the stream-destructors (see example below). Any idea whats going wrong ?
    Setup is eclipse with Arduino-IDE 1.5.2 for the toolchain.

    D:workspaceMiniDROstlinclude/iosfwd:48: multiple definition of `non-virtual thunk to std::basic_stringstream<char, std::char_traits<char>, std::allocator<char> >::~basic_stringstream()'
    ./DigitalReadout.cpp.o:D:workspaceMiniDROstlinclude/iosfwd:48: first defined here

    • http://blog.ciderspace.ch marco

      Hi – it's me again

      I prepared an example, wich reprocudes the above mentioned error. It looks, like the stream libraries are the problem. As soon as the stringstream in either cpp file below is commented out, the sketch links without any problem. Any idea what problem might be ?

      —————– loop.cpp ————–
      #include <Arduino.h>

      #include <iterator>
      #include <sstream>
      #include <pnew.cpp>

      #include "Foo.h"

      void setup() {

      }

      void loop() {
      std::stringstream ss;
      ss << "hello";

      Foo f;
      f.bar();
      }

      ——————— foo.h —————————–
      #ifndef FOO_H_
      #define FOO_H_

      #include <string>

      struct Foo {
      std::string bar();
      };

      #endif

      ——————– foo.cpp ————————
      #include "Foo.h"

      #include <sstream>

      std::string Foo::bar() {
      std::stringstream ss;
      return ss.str();
      }

      ./loop.cpp.o: In function `virtual thunk to std::basic_iostream<char, std::char_traits<char> >::~basic_iostream()':
      D:stlinclude/iosfwd:43: multiple definition of `virtual thunk to std::basic_iostream<char, std::char_traits<char> >::~basic_iostream()'
      ./Foo.cpp.o:D:stlinclude/iosfwd:43: first defined here
      ./loop.cpp.o: In function `non-virtual thunk to std::basic_iostream<char, std::char_traits<char> >::~basic_iostream()':

  • Steve

    Is there a simple way to extract Bytes from a Bitset? I thought they are just Integer types internally.

  • Pavel

    I've encountered a problem using classes with vector (and consequently, everything like deque and priority_queue) which are obviously related to object destruction. Meanwhile, I didn't find a solution (except for using pointers/indices and store the class elsewhere).

    In file included from t:arduinoarduino-1.0.4hardwaretoolsavrbin../lib/gcc/avr/4.7.2/../../../../avr/include/vector:33:0,
    from T:Arduinoarduino-1.0.4librariesSchedulerScheduler.h:34,
    from T:Arduinoarduino-1.0.4librariesSchedulerScheduler.cpp:30:
    t:arduinoarduino-1.0.4hardwaretoolsavrbin../lib/gcc/avr/4.7.2/../../../../avr/include/stl_construct.h: In instantiation of 'void std::__destroy_aux(_ForwardIterator, _ForwardIterator, __false_type) [with _ForwardIterator = Dummy*]':
    t:arduinoarduino-1.0.4hardwaretoolsavrbin../lib/gcc/avr/4.7.2/../../../../avr/include/stl_construct.h:78:3: required from 'void std::__destroy(_ForwardIterator, _ForwardIterator, _Tp*) [with _ForwardIterator = Dummy*; _Tp = Dummy]'
    t:arduinoarduino-1.0.4hardwaretoolsavrbin../lib/gcc/avr/4.7.2/../../../../avr/include/stl_construct.h:83:3: required from 'void std::_Destroy(_ForwardIterator, _ForwardIterator) [with _ForwardIterator = Dummy*]'
    t:arduinoarduino-1.0.4hardwaretoolsavrbin../lib/gcc/avr/4.7.2/../../../../avr/include/stl_construct.h:115:3: required from 'void std::destroy(_ForwardIterator, _ForwardIterator) [with _ForwardIterator = Dummy*]'
    t:arduinoarduino-1.0.4hardwaretoolsavrbin../lib/gcc/avr/4.7.2/../../../../avr/include/stl_vector.h:284:15: required from 'std::vector<_Tp, _Alloc>::~vector() [with _Tp = Dummy; _Alloc = std::allocator<Dummy>]'
    t:arduinoarduino-1.0.4hardwaretoolsavrbin../lib/gcc/avr/4.7.2/../../../../avr/include/stl_queue.h:150:7: required from here
    t:arduinoarduino-1.0.4hardwaretoolsavrbin../lib/gcc/avr/4.7.2/../../../../avr/include/stl_construct.h:66:5: error: 'destroy' was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation [-fpermissive]
    t:arduinoarduino-1.0.4hardwaretoolsavrbin../lib/gcc/avr/4.7.2/../../../../avr/include/stl_construct.h:114:13: note: 'template<class _ForwardIterator> void std::destroy(_ForwardIterator, _ForwardIterator)' declared here, later in the translation unit

    • http://www.andybrown.me.uk Andy Brown

      Hi Pavel,

      Most of the containers depend on iterator. Have you got #include <iterator> before the include for the container? If this doesn't fix it then please send me an example sketch using my contact form and I'll correct it for you.

      - Andy

      • Pavel

        Hi Andy,

        Thank you for the reply! I have found the solution to the problem and posting it below. One should add forward declaration for flavors of destroy() function. Paste these to line 61, and the problem would be solved:

        template <class _ForwardIterator>
        inline void destroy(_ForwardIterator __first, _ForwardIterator __last);

        template <class _Tp>
        inline void destroy(_Tp* __pointer);

        Hope, this helps somebody else.

        • http://www.andybrown.me.uk Andy Brown

          Ah I see. Thanks for the tip!

  • Michal

    Hi Andy,
    I am trying your STL library with Arduino Leonardo and I cannot get working serialstream from your examples. I got this error:

    Arduino: 1.5.5-r2 (Windows 8), Board: "Arduino Leonardo"

    sketch_feb15a.ino: In function 'void RunTest()':
    sketch_feb15a:12: error: no matching function for call to 'std::basic_oserialstream<char, std::char_traits<char>, HardwareSerial>::basic_oserialstream(Serial_&)'
    c:/ptak/arduino/hardware/tools/avr/lib/gcc/../../avr/include/serstream:215: note: candidates are: std::basic_oserialstream<charT, traits, Tserial>::basic_oserialstream(Tserial&) [with charT = char, traits = std::char_traits<char>, Tserial = HardwareSerial]
    c:/ptak/arduino/hardware/tools/avr/lib/gcc/../../avr/include/iosfwd:91: note: std::basic_oserialstream<char, std::char_traits<char>, HardwareSerial>::basic_oserialstream(const std::basic_oserialstream<char, std::char_traits<char>, HardwareSerial>&)

    Is it some easy way how to fix that?
    Thanks,

    Michal

    • http://www.andybrown.me.uk Andy Brown

      Hi Michal,

      The Leonardo has multiple hardware serial ports so you must use a constructor that takes Serial1, Serial2 or Serial3 as a parameter instead of just 'Serial'. Example:

      std::ohserialstream serial(Serial1);

  • http://twitter.com/8draws @8draws

    isn't there 'thread'?

  • Garry Smyda

    Hi Andy,

    I'm getting an error when I simply try to include vector (after iterator and pnew.cpp are included)

    The debug message shows 4 similar references to:

    /home/gwsmyda/arduino-1.0.5/hardware/tools/avr/bin/../lib/gcc/avr/4.3.2/../../../avr/include/stl_vector.h:517:68: error: macro "swap" passed 4 arguments, but takes just 2

    as well as 2 of these:

    /home/gwsmyda/arduino-1.0.5/hardware/tools/avr/bin/../lib/gcc/avr/4.3.2/../../../avr/include/stl_algobase.h:92: error: expected unqualified-id before ‘{’ token

    Thank you so much for your time, I really appreciate it.

    • http://www.andybrown.me.uk Andy Brown

      Hi Gary, please post your sketch to me using my Contact form and I'll find the issue.

  • Hank Barta

    Thank you so much for posting a port of STL for the Arduino environment. I've written and tested some code on my host and would now like to compile for the Arduino using the "arduino" IDE. My environment is hosted on Linux and I'm using the Debian packages (Debian/sid, version 1.0.5 of the IDE.) I simply cannot find where to install the headers or barring that, the search path that the IDE uses when it compiles my sketch. Any help on that would be appreciated.

    Perhaps I should just abandon the Debian packages and install the IDE as downloaded from the Arduino website.

    • http://www.andybrown.me.uk Andy Brown

      Hi Hank,

      Assuming that you know where you've installed the base Arduino package then the correct location relative to that root is:

      hardware/tools/avr/avr/include

      The directory should exist and contain system headers such as stdio.h, stdlib.h etc. If you 'cd' into the Arduino directory on linux then you could just run a shell command to find the correct directory:

      $ find . -name stdio.h -print

      • Hank Barta

        Thanks for the help with that. Seeing so many other Arduino headers in their own directories, I was trying to do that. Also I was reluctant to add a bunch of headers to a directory that already held headers. But eventually I got to that point and that's what worked.