LinuxQuestions.org
Download your favorite Linux distribution at LQ ISO.
Go Back   LinuxQuestions.org > Blogs > rainbowsally
User Name
Password

Notices


Rate this Entry

STL Template Experiment (Lists)

Posted 12-24-2012 at 10:24 AM by rainbowsally
Updated 08-06-2014 at 09:00 AM by rainbowsally (added link, grammar error, makefile line correction)

We've resurrected some dead code that was pretty ugly but the only worse MESS (officially sanctioned, no less) than STL that we've ever seen is the spaghetti in lex/flex output. -- The Computer Mad Science Dept.

So...

Now what?

Well...

...what would ANY good Computer Mad Scientist do in a situation like this?

Today's features are
  • Creating lists using the std::list STL template.
  • Identifying the critical 'operators' needed by STL.
  • Another usage example using "foreach" to make dealing with iterators easy.
  • Playing with the STL 'reverse' <algroithm> and...
  • How to '-I(nclude) from the STL folder when you don't know where the files are.
  • A peek at another 32 bit hash algorithm that really scrambles the bits (excellent uniqueness) for fast almost foolproof comparisons.

Let's start with the STL stuff. How do we find that stuff to include it?

Makefiles don't deal with bash types of wildcards the way you might need it to work but makefiles do have wildcards. Use a '%' token instead of a '*' et. voila! :-)

For example, if you can find (lets say) the stl <vector> header using
Code:
ls /usr/include/c++/4.*/vector
then you can include all the files along with <vector> by doing this in your makefile or mc2 definitions:
Code:
-I/usr/include/c++/4.%
That includes the stl stuff for any version of gcc >= 4.0 and < 5.0.

Your paths may differ, but it's pretty unlikely. That's where gcc built from source code likes to put that stuff.

So now that we know how to find the headers here's a stripped down mc2.def file for making today's code toy.

[If you don't have mc2, but do know how to hand-write Makefiles this should be pretty easy to figure out.]

file: mc2.def
purpose: makefile definitions for an STL application
Code:
# this is the makefile equivalent of 
#   /usr/include/c++/4.<version_minor>/
# which is where the stl files are.
STLDIR = /usr/include/c++/4.%/

OUTNAME = stl-list-test

SRCDIR = src
OBJDIR = o
BINDIR = .

COMPILE = g++ -c -o # COMPILE <output_file> ...
CFLAGS = -Wall -g3 # debug
#CFLAGS = -Wall -O2 # optimized
INCLUDE = -I $(SRCDIR) -I$(PREFIX)/include -I /usr/include -I"/usr/include/c++/4.%"

LINK = g++ -o # LINK <output_file> ...
LDFLAGS = 
LIB = -L/usr/lib -L$(PREFIX)/lib

clean:
@rm -f $(MAIN) $(OBJ) 
@rm -f *~ */*~ */*/*~ */*/*/*~


The makefile will build with debug info and if you have kdbg (>= 5.0 recommended) or some other insight-like debugger, you can watch the variables and even step through the stl functions.

Here's today's 'featured' snip of Computer Mad Science. :-) It's fairly large because it also shows usage of the foreach macro we created recently and tests a simple list as well as a list of objects with more complex fields.


file: src/stl-list-test.cpp
purpose: source file
Code:
// stl-list-test.cpp

// To include stl, since it's version-dependent use the makefile wildcard '%'.
// like so:
// ... -I"/usr/include/c++/4.%" ...
// This includes the stl headers for any gcc version >= 4.0 and < 5.0

#include <stdio.h>
#include <list>
#include <algorithm>
#include <string.h> // strdup()

void dbg(){}

extern "C"
{
// from lq lib v 3.0.14+.  The odd names are for creating this 
// as an assembly language routine.
int hash32_enum(const char* name_8ebp) 
{
  if(!name_8ebp) return 0;
  if(!*name_8ebp) return -1;
  const char* p_edx = name_8ebp;
  int prime_ecx = 16777619;
  int ob_eax = -2128831035;
  while(*p_edx) {
    ob_eax ^= *p_edx++;
    ob_eax *= prime_ecx;
  }
  // if hi bit not set, flip all bits
  if(ob_eax < 0)
    return ob_eax;
  else
    return ~ob_eax;
}
} // C

// so we don't have to type std:: in front of all these stl things...
using namespace std;

// A simple class
class Uint {
  public:
    uint value; 
    Uint() // no inputs, no inheritance
    { 
      value = 0;
    }
    Uint(uint x) 
  : value(x) // setup inputs, no inheritance to init
    { }      // no memory to allocate
};


// A more involved class
class Str
{
  public:
    int id;
    char* str;
    int length;

    // constructor if there is no input parameter.
    Str() // no input, no inheritance
    { 
      // set up default
      str = 0;  
      id = length = 0;
    }

    // constructor copies the input string if not null
    // and sets a unique id for quick checking for equality
    Str(const char* what_it_is) // no inheritance
    {
      if(what_it_is == 0)
      {
        str = 0; 
        length = id = 0;
      }
      else
      {
        str = strdup(what_it_is); // doesn't work???
        length = strlen(what_it_is);
        id = hash32_enum(str);
      }      
    }
    
    // destructor checks if it's a null pointer or if it
    // can be freed and marks it as freed in either case.
    ~Str()
    {
      if(str) 
        free(str); 
      str = 0;
      id = length = 0;
    }

    // in C++ the & in this position indicates that the object
    // on the stack can be addressed as the struct itself, not
    // just a pointer, though the object itself may or may not 
    // actually be the entire struct.
    static bool is_equal(const Str& a, const Str& b)
    {
      return a.id == b.id;
    }

};



// We need, as bare a minimum, an operator for '==' for the STL algorithms
// to work.  Here's the operator for Uint.
bool operator==(const Uint& a, const Uint& b)
{
  return a.value == b.value;
}

// And for the Str we use a call in the class that (for this example) just 
// compares the hash IDs.
bool operator == (const Str& a, const Str& b)
{
  return Str::is_equal(a, b);
}

// Here's foreach again.  This allows setting up several vars in the 
// first field of a for() loop
template <typename T>
    class ForIter {
      public:
        const T _t;       // type
        int _f;           // break flag for outer loop
        typename T::const_iterator _i, end;
        inline ForIter(const T& t) 
        : _t(t), _f(0), _i(_t.begin()), end(_t.end()) { }
    };

// With the __extension__ flag, this allows multiple operations in each
// for() field, which are split up for clarity below.  And there are two 
// for() blocks, the outer one is the loop, the inner one just creates 
// the name we use to address the iterator and handles 'break;' within 
// the loop.  It always performs break; itself, to return the decremented 
// counter (_f) which will always be zero as long as it keeps looping.  
// See "!_classT_._f" below.  That is where it will exit the loop if a 
// break is done in the user supplied code section.
#define foreach(name, classT)                             \
    for(                                                  \
        ForIter<__typeof__(classT)> _classT_(classT);     \
        !_classT_._f && _classT_._i != _classT_.end;      \
        __extension__ ({ ++_classT_._f; ++_classT_._i; }) \
      )                                                   \
    for(                                                  \
        name = *_classT_._i;                              \
        /* nothing here */ ;                              \
        __extension__ ({--_classT_._f; break;})           \
       )


int main()
{
  dbg();
  
  const char* test_str[] = { "just", "some", "random", "strings" };
  
  list<Uint> Uint_list1, Uint_list2;
  list<Str> Str_list1, Str_list2;

  // *** We put theStr pointer for new Str objects outside the loop!  Otherwise
  // the objects get automatically deleted by the ingenious C++ mechanism that 
  // removes them as execution leaves the scope.  Try putting this 'Str* pStr' 
  // inside the loop below and see what happens.  Try creating the Str object 
  // the same way the Uint objects are created.  That doesn't work either.
  // [Same reason but more subtle.  In fact they are deleted immediately, even 
  // before the next one is created if you do it the way the Uints are done.
  // Interesting, no?  (Ick!)]

  Str* pStr;
      
  for(uint i=0; i < 4; i++) 
  {
    // load one Uint list from 0 to 3 and the other from 3 to 0
    Uint_list1.push_back(Uint(i));
    Uint_list2.push_back(Uint(3 - i));
  
    // load one Str list forward and the other backward
    // Note the "*"+"pStr" below.  An object pointer here
    // will not work and a literal instance created on the 
    // fly won't either!  Doncha just love STL?
    pStr = new Str(test_str[i]);
    Str_list1.push_back(*pStr);
    
    pStr = new Str(test_str[3 - i]);
    Str_list2.push_back(*pStr);
  }
  
  printf("Testing '==' operator and the STL algorithm to reverse\n"
      "a list of objects of any arbitrary class\n\n"
  );

  reverse(Uint_list1.begin(), Uint_list1.end());

  printf("Testing Uint class: ");
  if(Uint_list1 == Uint_list2) 
    printf("PASSED\n");
  else
    printf("FAILED\n");

#define SHOWIT 0
#if SHOWIT
 // Enable this printout if you want to see the strings. 's' below is a genuine 
 // C++/STL iterator.  Look how simple the syntax is with the foreach() macro.
 
  // Almost bash.  The varName needs a class type before the varName and 
  // the object to get the values from must be a container understood by STL.
  // In this case it's an instance of an 'std::list' that contains the Str
  // objects to iterate over.
  foreach(Str s, Str_list1)
    printf("id: 0x%8X, length: %d, value: %s\n", s.id, s.length, s.str);
  printf("\n");
  
  // for each Str s in List..
  foreach(Str s, Str_list2)
    printf("id: 0x%8X, length: %d, value: %s\n", s.id, s.length, s.str);
  printf("\n");
#endif

  reverse(Str_list2.begin(), Str_list2.end());    
  
  printf("Testing Str class: ");
  if(Str_list1 == Str_list2) 
    printf("PASSED\n");
  else
    printf("FAILED\n");
  
}

The good magic of STL is in its ability to iterate over the list regardless of the type of object in the list, and it can do this with very little 'required' code at the user's end.

The bad magic of STL is that the error messages are written in a 7th Century Martian dialect. You won't get far very quickly without a GOOD debugger. And even then it's a challenge. Between C++ tricks and STL tricks there are two ways to get clobbered.

Check out "Doncha just love STL" comment and context above. Try it if you don't believe it. Try making the Str objects as non-pointer refs (i.e., without "new") like the ones in the Uint lists. In fact try creating the pointers inside the loop.

That mine field is loaded with surprises. But once it works, if the code is hidden deep enough to not cause any trouble, it might save you a lot of time coding.

We shall see. :-)

[More about the hash algorithm in the next blog entry. http://www.linuxquestions.org/questi...nd-asm-35224/]

- The Computer Mad Science Team

:-)
Posted in Uncategorized
Views 2302 Comments 1
« Prev     Main     Next »
Total Comments 1

Comments

  1. Old Comment
    Code:
      // *** We put theStr pointer for new Str objects outside the loop!  Otherwise
      // the objects get automatically deleted by the ingenious C++ mechanism that 
      // removes them as execution leaves the scope.  Try putting this 'Str* pStr' 
      // inside the loop below and see what happens.
    Pretty sure this is wrong. Objects created by new are never deleted automatically. You are leaking those objects.

    Code:
      // Try creating the Str object 
      // the same way the Uint objects are created.  That doesn't work either.
      // [Same reason but more subtle.  In fact they are deleted immediately, even 
      // before the next one is created if you do it the way the Uints are done.
      // Interesting, no?  (Ick!)]
    You didn't make a copy constructor for your Str objects, so both copies try to free() the same string.
    Posted 09-10-2013 at 03:24 PM by ntubski ntubski is offline
 

  



All times are GMT -5. The time now is 12:07 AM.

Main Menu
Advertisement
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration