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)
Updated 08-06-2014 at 09:00 AM by rainbowsally (added link, grammar error, makefile line correction)
Tags computer mad science, stl, template
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
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
then you can include all the files along with <vector> by doing this in your makefile or mc2 definitions:
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
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
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
:-)
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
Code:
-I/usr/include/c++/4.%
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
:-)
Total Comments 1
Comments
-
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.
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!)]
Posted 09-10-2013 at 03:24 PM by ntubski