next topic »

[on:]

Hi all,

Is there, or has anyone got, a library to do the c++ map(), rather than the Arduino map which is completely different?

Cheers,

Simon
http://www.cplusplus.com/reference/stl/map/map/

[Reply #1 on:]

https://github.com/maniacbug/StandardCplusplus/blob/master/map

[Reply #2 on:]

Also the whole STL for Arduino:

http://andybrown.me.uk/ws/2011/01/15/the-standard-template-library-stl-for-avr-with-c-streams/

[Reply #3 on:]

Also the whole STL for Arduino:

http://andybrown.me.uk/ws/2011/01/15/the-standard-template-library-stl-for-avr-with-c-streams/

This is absolutely awesome!

[Reply #4 on:]

It *is* awesome isn't it?

I did some tests here:

http://www.gammon.com.au/forum/?id=11119

I found that using a map only added 2400 bytes to program memory. Not too bad, out of 32 Kb.

[Reply #5 on:]

Nice! On more than one occasion I have wished I had the STL available. I solved the memory consumption problem by selecting the 1284P for my primary project.

I wonder if I could write a malloc() and free() that operate against the EEPROM, so i could use the STL against the EEPROM instead of SRAM? That would be pretty cool...

[Reply #6 on:]

Yeah, the STL rocks.  Plus Andy has a nice implementation of the hardware serial as a UART, which I included in my version as well.

[Reply #7 on:]

I wonder if I could write a malloc() and free() that operate against the EEPROM, so i could use the STL against the EEPROM instead of SRAM? That would be pretty cool...

I wouldn't advise that, for more reasons than one. For one thing, the pointer would be to EEPROM, but the STL would try to access SRAM.

[Reply #8 on:]

Also the whole STL for Arduino:

http://andybrown.me.uk/ws/2011/01/15/the-standard-template-library-stl-for-avr-with-c-streams/

The link I provided is similar to yours (the whole STL), but my original post just showed the map function.
https://github.com/maniacbug/StandardCplusplus

[Reply #9 on:]

Sure. And when you've played with STL for a while you start wanting vectors, strings, dequeues and so on.

[Reply #10 on:]

Sure. And when you've played with STL for a while you start wanting vectors, strings, dequeues and so on.

True, but lets not forget we're programming for a microcontroller (limited code and data space).  I use many of the STL algorithms and containers in my desktop programs.

[Reply #11 on:]

Sure. And when you've played with STL for a while you start wanting vectors, strings, dequeues and so on.

True, but lets not forget we're programming for a microcontroller (limited code and data space).  I use many of the STL algorithms and containers in my desktop programs.

The overhead of the simpler containers is minimal. As for the more expensive ones, well that's a tradeoff you'll need to make. If you have the space, what the heck. If you're making thousands of something, then I can understand you want to use the smallest (cheapest) CPU possible.

[Reply #12 on:]

I would love for someone to do some performance testing with the various STL implementations with avr-gcc.  I use C++Builder on the desktop, and it uses the dinkumware's STL libraries which is optimized for MSVC.  It turns out those optimizations are not optimal for C++Builder.  As a result, the implementation for C++Builder is not that efficient.

[Reply #13 on:]

Here's an interesting test for you ...

Using the STL I linked to, we can generate and sort 800 ints (not too bad on a 2 Kb machine):

Code:

// STL sort test

#include <iterator>
#include <vector>
#include <algorithm>
#include <Streaming.h>

#define ITEMS 800

void setup ()
  {
  Serial.begin (115200);
  std::vector<int> v (ITEMS);

  std::generate (v.begin (), v.end (), rand);
 
  Serial << "Starting STL sort ... " << endl;
  unsigned long start = millis ();
  std::sort (v.begin (), v.end ());
  unsigned long finish = millis ();
  Serial << "Finished STL sort ... " << endl;

  for (std::vector<int>::const_iterator i = v.begin (); i != v.end (); i++)
    Serial << *i << endl;

  Serial << "Took: " << (int) (finish - start) << " milliseconds." << endl;
  }
 
  void loop () {}

Output:

Code:

Starting STL sort ...
Finished STL sort ...
57
62
100
103
240
261
343
363
395
396
421
457
478
487
493
493
498
522
534
...
32449
32520
32558
32647
32660
32703
32723
Took: 10 milliseconds.

Now using qsort (first, it reset with 800 items, so I had to drop the test down to 700 items):

Code:

// qsort test

#include <iterator>
#include <algorithm>
#include <Streaming.h>

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

#define ITEMS 700

int v [ITEMS];

void setup ()
  {
  Serial.begin (115200);
  std::generate_n (v, ITEMS, rand);
   
  Serial << "Starting qsort ... " << endl;
  unsigned long start = millis ();
  qsort (v, ITEMS, sizeof(int), compare);
  unsigned long finish = millis ();
  Serial << "Finished qsort ... " << endl;

  for (int i = 0; i < ITEMS; i++)
    Serial << v [i] << endl;

  Serial << "Took: " << (int) (finish - start) << " milliseconds." << endl;
  }
 
  void loop () {}

Output:

Code:

Starting qsort ...
Finished qsort ...
57
62
100
103
240
261
343
363
395
396
421
457
478
487
493
498
534
538
595
...
32006
32020
32059
32150
32291
32316
32320
32331
32334
32371
32449
32520
32558
32647
32660
32703
32723
Took: 32 milliseconds.

So qsort took 3 times as long to do 88% of the number of items!

And the STL version was more memory efficient. To compare apples with apples, dropping the STL sort down to 700 items, it only took 7 seconds.