Introduction
STL (Standard Template Library) is a good skill for anyone programming C++ in the modern day. I must say that it takes some getting used to, i.e. there is a fairly steep learning curve, and some of the names that are used are not very intuitive (perhaps because all of the good names had been used up). The upside is once learned they will save you headaches down the road. Compared to MFC containers, they are more flexible and powerful.
Listed advantages:
- Can sort and search easily
- They are safer and easier to debug
- You can understand code written by the UNIX crowd.
- It is another acronym to add to your resume
Background
This guide has been written so that the reader can get a running start at this challenging part of computer science, without having to wade through the endless mass of jargon and stifling exactitude that STL'er have created for their own amusement.
Using the Code
The code here is mainly instructive on the practical ways to use STL.
Definitions
- Template - A macro for classes (and structures and data types and functions). Sometimes called a cookie cutter. Also formally known as generic - a template of a class is called a generic class. A template of a function is called, wait for it, a generic function.
- STL - Standard Template Library, templates written by a bunch of smart people, now used by everyone part of the C++ standard language.
- Container - A class that holds data. STL examples are vectors, sets, maps, multimaps, and deques.
- Vector - Your basic array template. It is a container.
- Iterator - A fancy word for a pointer to an element inside an STL container. It does other stuff too.
Hello World Program
I always wanted to write one and here is my golden 24 karet opportunity: a hello world program. This transfers a char string into a vector of characters and then displays the string one character at a time. A vector is your basic garden variety array-like template. Probably, about half of all STL containers are vectors, so if you grasp this program, you are half way to a complete understanding of STL.
#include <vector> // STL vector header. There is no ".h"
#include <iostream> // for cout
using namespace std;
char* szHW = "Hello World";
int main(int argc, char* argv[])
{
vector <char> vec;
vector <char>::iterator vi;
char* cptr = szHW;
while (*cptr != '\0')
{ vec.push_back(*cptr); cptr++; }
for (vi=vec.begin(); vi!=vec.end(); vi++)
{ cout << *vi; }
cout << endl;
return 0;
}
push_back is the standard function for putting data into a vector or deque. insert is a similar function and does much the same, and works with all containers, but is more complicated. The end() is actually the end plus one, to allow the loop to operate properly - it actually points to the point just beyond the limits of the data. Just like in a regular loop in which you say for (i=0; i<6; i++) {ar[i] = i;} - ar[6] does not exist, but it is never reached in the loop so it does not matter.
STL Annoyance #1:
One of the first annoyances of STL makes itself known. To initialize it with data is more difficult than is the case in C/C++ arrays. You basically must do it element by element, or first initialize an array and then transfer it. People are working on this I understand.
#include <cstring> // same as <string.h>
#include <vector>
using namespace std;
int ar[10] = { 12, 45, 234, 64, 12, 35, 63, 23, 12, 55 };
char* str = "Hello World";
int main(int argc, char* argv[])
{
vector <int> vec1(ar, ar+10);
vector <char> vec2(str, str+strlen(str));
return 0;
}
In programming, there are many ways of doing the same task. Another way to fill a vector is to use the more familiar square brackets, like so:
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;
char* szHW = "Hello World";
int main(int argc, char* argv[])
{
vector <char> vec(strlen(sHW));
int i, k = 0;
char* cptr = szHW;
while (*cptr != '\0')
{ vec[k] = *cptr; cptr++; k++; }
for (i=0; i<vec.size(); i++)
{ cout << vec[i]; }
cout << endl;
return 0;
}
This example is cleaner, but allows you less control of the iterator, and has an extra integer counter, and you must explicitly set the memory footprint.
Namespaces
Hand in hand with STL is the concept of Namespaces. STL is defined within the std namespace. There are 3 ways to specify it:
- USE that namespace, near the top of all files, but below headers.
using namespace std;
This is the simplest and best for simple projects, limits you to the std namespace, anything you add is improperly put in the std namespace (I think you go to heck for doing this).
- Specify each and every template before use (like prototyping)
using std::cout;
using std::endl;
using std::flush;
using std::set;
using std::inserter;
This is slightly more tedious, although a good mnemonic for the functions that will be used, and you can interlace other namespaces easily.
- EVERY time you use a template from the
std namespace, use the std scope specifier. typedef std::vector<std::string> VEC_STR;
This is tedious but the best way if you are mixing and matching lots of namespaces. Some STL zealots will always use this and call anyone evil who does not. Some people will create macros to simplify matters.
In addition, you can put using namespace std within any scope, for example, at the top of a function or within a control loop.
Some Tips
To avoid an annoying error code in debug mode, use the following compiler pragma:
#pragma warning(disable: 4786)
Another gotcha is: you must make sure that the spaces are placed between your angle brackets and the name. This is because >> is the bit shift operator, so:
vector <list<int>> veclis;
will give an error. Instead, write it:
vector <list <int> > veclis;
to avoid compilation errors.
Another Container - The set
This is the explanation lifted from the MS help file of the set: "The template class describes an object that controls a varying-length sequence of elements of type const Key. Each element serves as both a sort key and a value. The sequence is represented in a way that permits lookup, insertion, and removal of an arbitrary element with a number of operations proportional to the logarithm of the number of elements in the sequence (logarithmic time). Moreover, inserting an element invalidates no iterators, and removing an element invalidates only those iterators that point at the removed element."
An alternate, more practical, definition is: A set is a container that contains all unique values. This is useful for cases in which you are required to collect the occurrence of value. It is sorted in an order that is specified at the instantiation of the set. If you need to store data with a key/value pair, then a map is a better choice. A set is organized as a linked list, is faster than a vector on insertion and removal, but slightly slower on search and addition to end.
An example program would be:
#include <string>
#include <set>
#include <iostream>
using namespace std;
int main(int argc, char* argv[])
{
set <string> strset;
set <string>::iterator si;
strset.insert("cantaloupes");
strset.insert("apple");
strset.insert("orange");
strset.insert("banana");
strset.insert("grapes");
strset.insert("grapes");
for (si=strset.begin(); si!=strset.end(); si++)
{ cout << *si << " "; }
cout << endl;
return 0;
}
If you want to become an STL fanatic, you can also replace the output loop in the program with the following lines.
copy(strset.begin(), strset.end(), ostream_iterator<string>(cout, " "));
While instructive, I find this personally less clear and prone to error. If you see it, now you know what it does.
All the STL Containers
Containers pre-date templates and are computer science concepts that have been incorporated into STL. The following are the seven containers implemented in STL.
- vector - Your standard safe array. It is expanded in the "front" direction only.
- deque - Functionally the same as a vector. Internally, it is different. It can be expanded in both the front and back.
- list - Can only be traversed one step at time. If you are already familiar with the concept of a list, an STL list is doubly linked (contains pointer to both the previous and next value).
- set - contains unique values that are sorted.
- map - sorted set of paired values, one of which is the key on which sorts and searches occur, and the value which is retrieved from the container. E.g. instead of ar[43] = "overripe", a map lets you do this ar["banana"] = "overripe". So if you wanted to draw up a bit of information keyed on full name is easily done.
- multiset - same as a set, but does not necessarily have unique values.
- multimap - same as a map, but does not necessarily have unique keys.
Note: If you are reading the MFC help then you will also come across the efficiency statement of each container. I.E. (log n * n) insertion time. Unless you are dealing with very large number of values, you should ignore this. If you start to get a noticeable lag or are dealing with time critical stuff then you should learn more about the proper efficiency of various containers.
How to Use a Map with some Class
The map is a template that uses a key to obtain a value.
Another issue is that you will want to use your own classes instead of data types, like int that has been used up to now. To create a class that is "template-ready", you must be ensure that the class contains certain member functions and operators. The basics are:
- default constructor (empty, usually)
- copy constructor
- overload "
="
You would overload more operators as required in a specific template, for example, if you plan to have a class that is a key in a map you would have to overload relational operators. But that is another story.
#include <string>
#include <iostream>
#include <vector>
#include <map>
using namespace std;
class CStudent
{
public :
int nStudentID;
int nAge;
public :
CStudent() { }
CStudent(int nSID, int nA) { nStudentID=nSID; nAge=nA; }
CStudent(const CStudent& ob)
{ nStudentID=ob.nStudentID; nAge=ob.nAge; }
void operator = (const CStudent& ob)
{ nStudentID=ob.nStudentID; nAge=ob.nAge; }
};
int main(int argc, char* argv[])
{
map <string, CStudent> mapStudent;
mapStudent["Joe Lennon"] = CStudent(103547, 22);
mapStudent["Phil McCartney"] = CStudent(100723, 22);
mapStudent["Raoul Starr"] = CStudent(107350, 24);
mapStudent["Gordon Hamilton"] = CStudent(102330, 22);
cout << "The Student number for Joe Lennon is " <<
(mapStudent["Joe Lennon"].nStudentID) << endl;
return 0;
}
TYPEDEF
If you like to use typedef, this an example:
typedef set <int> SET_INT;
typedef SET_INT::iterator SET_INT_ITER
One convention is to make them upper case with underscores.
ANSI / ISO string
ANSI/ISO strings are commonly used within STL containers. It is your standard string class, widely praised except for its deficiency of no format statement. You must instead use << and the iostream codes (dec, width, etc.) to string together your string.
Use c_str() to retrieve a character pointer, when necessary.
Iterators
I said that iterators are pointers, but there is more. They look like pointers, act like pointers, but they are actually embedded in which the indirection operator (unary *) and -> have been overloaded to return a value from the container. It is a bad idea to store them for any length of time, as they usually invalid after a value has been added or removed from a container. They are something like handles in this regard. The plain iterator can be altered, so that the container is to be traversed in different ways:
- iterator - For any container other than the vector, you can only step one at a time in a forward direction through the container. That is you can only use the
++ operator, not the -- or += operator on it. For vector only you can use any of +=, --, -=, ++, and all the comparison operators <, <=, >, >=, ==, !=.
- reverse_iterator - If you want to step backwards instead of forwards through a non-vector container, replace iterator with
reverse_iterator, begin() with rbegin(), and end() with rend(), ++ will then traverse backwards.
- const_iterator - a forward iterator that returns a
const value. Use this if you want to make it clear that this points to a read-only value.
- const_reverse_iterator - a reverse iterator that returns a
const value.
Sorting Order in Sets and Maps
Templates have other parameters besides the type of value. You can also pass callback functions (known as predicates - this is a function of one argument that returns a bool value). For example, say you want a set of strings that are automatically sorting in ascending order. You would simply create a set class in this way:
set <int, greater<int> > set1
greater <int> is another template for a function (generic function) which is used to sort values, as they are placed into the container. If you wanted the set to be sorted in descending order, you would write:
set <int, less<int> > set1
There are many other cased you must pass a predicate as parameter to the STL class, in algorithms, described below.
STL Annoyance #2 - Long Error Messages
The templated names get expanded for the compiler, so when the compiler chokes on something, it spits out extremely long error messages that are difficult to read. I have found no good way around this. The best is to develop the ability to find and focus on the end of the error code where the explanation is located. Another related annoyance: if you double click on the template error, it will take you to the point in the code within the template code, which is also difficult to read. Sometimes, it is best just to carefully re-examine your code, and ignore the error messages completely.
Algorithms
Algorithms are functions that apply to templates. This is where the real power of STL starts to show up. You can learn a few function names that usually apply to most of the template containers. You can sort, search, manipulate, and swap with the greatest of ease. They always contain a range within which the algorithm performs. E.g.: sort(vec.begin()+1, vec.end()-1) sorts everything but the first and last values.
The container itself is not passed to the algorithm, just two iterators from the container that bookend a range. In this way, algorithms are not restricted by containers directly, but by the iterators supported by that specific algorithm. In addition, many times you will also pass a name of a specially prepared function (those afore mentioned predicates) as an argument. You can even pass plain old values.
Example of algorithms in play:
#include <algorithm> // If you want to use an
#include <numeric> // (For Accumulate)
#include <vector>
#include <iostream>
using namespace std;
int testscore[] = {67, 56, 24, 78, 99, 87, 56};
bool passed_test(int n)
{
return (n >= 60);
}
bool failed_test(int n)
{
return (n < 60);
}
int main(int argc, char* argv[])
{
int total;
vector <int> vecTestScore(testscore,
testscore + sizeof(testscore) / sizeof(int));
vector <int>::iterator vi;
sort(vecTestScore.begin(), vecTestScore.end());
cout << "Sorted Test Scores:" << endl;
for (vi=vecTestScore.begin(); vi != vecTestScore.end(); vi++)
{ cout << *vi << ", "; }
cout << endl;
vi = min_element(vecTestScore.begin(), vecTestScore.end());
cout << "The lowest score was " << *vi << "." << endl;
vi = max_element(vecTestScore.begin(), vecTestScore.end());
cout << "The highest score was " << *vi << "." << endl;
cout << count_if(vecTestScore.begin(), vecTestScore.end(), passed_test) <<
" out of " << vecTestScore.size() <<
" students passed the test" << endl;
cout << count_if(vecTestScore.begin(),
vecTestScore.end(), failed_test) <<
" out of " << vecTestScore.size() <<
" students failed the test" << endl;
total = accumulate(vecTestScore.begin(),
vecTestScore.end(), 0);
cout << "Average score was " <<
(total / (int)(vecTestScore.size())) << endl;
return 0;
}
See you later, Allocator
These are used in the initialization stages of a template. They are mysterious behind the scenes type of creatures, and really only of concern if you are doing high level memory optimization, and are best considered to be black boxes. Usually, you never even specify them as they are default parameters that are generally not tinkered with. It is best to know what they are though in case they show up on one of those employment tests.
Derive or Embed Templates
Any way that you use a regular class, you can use an STL class.
It can be embedded:
class CParam
{
string name;
string unit;
vector <double> vecData;
};
or used as a base class:
class CParam : public vector <double>
{
string name;
string unit;
};
Derivation should be used with some caution. It is up to you as to the form that fits your programming style.
Templates within Templates
To create a more complex data structure, you can nest a template within a template. It is best to typedef beforehand on the internal template as you will certainly need to use the inner template again.
#include <iostream>
#include <vector>
using namespace std;
typedef vector <int> VEC_INT;
int inp[2][2] = {{1, 1}, {2, 0}};
int main(int argc, char* argv[])
{
int i, j;
vector <VEC_INT> vecvec;
VEC_INT v0(inp[0], inp[0]+2);
VEC_INT v1(inp[1], inp[1]+2);
vecvec.push_back(v0);
vecvec.push_back(v1);
for (i=0; i<2; i++)
{
for (j=0; j<2; j++)
{
cout << vecvec[i][j] << " ";
}
cout << endl;
}
return 0;
}
Although cumbersome to initialize, once completed and filled in, you have a 2 dimensional array that is indefinitely expandable (until memory space runs out). The same can be done for any combination of containers, as the situation requires.
Conclusion
STL is useful, but not without its annoyances. As the Chinese say: if you learn it, you will be like a tiger with the claws of a lion.
Related Links
History
- Submitted on March 23, 2004
- Edited on April 2, 2004
|
|
 |
 | STL Passing
Mahashan | 5:24 29 Dec '09 |
|
|
Sir,
I am new to the STL List
I have a Classs InputManager and OutPutManager
InputManager Class Populate the UDP Data on a list
typedef list<string, allocator<string> > lstData;
Example
=======
lstData lstr;
void PopulateIncomingData(char rstring[])
{
lstr.push_back(rstring);
lstr.back();
}
I Running a thread, in this i called this function,
Now i have another class OutputManger, here i need to read the list(lstr) and i write the list data on a txt file. here how to share the STL list from one class to another,How we can get the list data.
Please replay me sir
hhh
|
|
|
|
|
| Error
asdfbasdfase | 19:05 18 Aug '09 |
|
|
The comment in the following code
set <string> strset;
...
strset.insert("grapes");
strset.insert("grapes");
is misleading (simply wrong). set is a unique associative container for which 'insert' operations only insert into the set if the set does not already contain an element with the same key.
In the example, the semantics of the comment correspond with the semantics of the code, yet the comment demonstrates a lack of actual experience in the use of sets and will lead to failure.
When sets are used more extensively (in the real world), one will typically use objects as elements of a set combined with a self-defined 'Less' comparator. It is very common to reuse keys for different objects.
Likewise for a map. To validate the comment
the following code must be used:
strset.insert("grapes");
pair<set <string>::iterator, bool> result(strset.insert("grapes"));
if ( result.second == false ) {
strset.erase("grapes");
strset.insert("grapes");
}
Granted, this is not obvious if you've never actually used sets for anything else than strings or integer types. Note that when using different objects with the same key, one may use an arbitrary object to erase an existing element of the set, as long as both object's keys are equal.
See the Expression Semantics @ http://www.sgi.com/tech/stl/UniqueAssociativeContainer.html
How this works when inserting a range of elements into a set is left as an exercise to the reader.
|
|
|
|
|
| Nice article
Pratima Kudale | 1:14 1 Feb '08 |
|
|
Very well organized and nice "how to" for startup programmer
|
|
|
|
|
| Job well done
-Dy | 8:01 16 Jul '06 |
|
|
An excellent article, mainly for the content, but also for the discussions it's generated below.
Would be good to see you write some more...
- Dy
|
|
|
|
|
| Some Suggestions [modified]
Zac Howland | 8:10 17 May '06 |
|
|
I know this article is over a year old, but just in case someone new to STL comes across it, here are a few suggestions:
1) A simpler first example. Hello, world shouldn't take but a very few lines of code to write:
main.cpp
#include <iostream>
using namespace std;
void main()
{
cout << "Hello, World!" << endl;
}
2) To demonstrate vectors (or any STL container), use a more practical example. Your accumulation example later in the article would go good for this.
3) Instead of showing examples that use custom loops, show ones that use the STL algorithms. You should ALWAYS use algorithms instead of custom loops (for the reasons why, check out Scott Meyer's books Effective C++ and Effective STL). Showing examples using them helps beginners to learn that from the start. I cannot tell you how many experienced programmers I run into that don't realize this because beginning examples didn't show it and once a habit is formed, it is very difficult to stop.
4) NEVER put using directives in header files. The reasons are very simple. First, you are not allowed to add anything to the standard library. By adding "using namespace std" to your class definition's header file, you do just that (albiet, on accident since I'm sure you didn't mean to add a class to the standard library). Second, as soon as someone else goes to use your code (e.g. #includes that header file), they are now forced with the using namespace directive. That is, lets say someone declared a vector class in their own namespace and included your utility class that uses STL vectors internally. If you placed the using directive in your header file, their code will not compile because now there is a name conflict in their code.
Along those same lines, when you declare functions that use STL templates as arguments or return values or member variables that are STL templated types, either typedef them or use the fully-quantified name. You mention this in your article, but it didn't seem clear when I read it.
5) The pragma directive is only valid for Visual C++. Another compiler may not have the same problem, or may require a different pragma statement or compiler directive.
6) Don't discount the efficiency notations for small sets. Using the correct container for what you are trying to do can decrease the development time and many headaches. In other words, learn when vector is a better choice than list (and vice versa); learn when a binary tree sorting scheme will be better than a linear, etc. That way, when you go to declare your container/algorithm, at least you know why you picked it over another one (instead of saying, "I'm use to using vectors ...")
7) In general, typedefs are NOT uppercase'd and underscored. Only constants and macros get those rules (in general). Some development houses may have their own coding standards, but that is not a general case one. Typically, typedef's are treated the same as class/type names. Example:
typedef std::vector LongVector;
8) Just a note that STL's string container uses reference counting, which can cause some debugging headaches in multithreaded applications. If you intend to pass strings around between threads, use vector<char> instead (note that you can access a null-terminated ANSI string in a vector by using &vec[0]).
9) With regard to the long error messages. One technique is to slowly unwind the templated junk in the message to get it down to an understandable message. For example, if you get an error related to string, it will start with basic_string<...> where the ... is all the junk you really don't care much about. Copy the message to a text file and match up the <> pairs (and delete them) until you get the message down to that.
10) NEVER derive from the STL containers. They are not meant to be derived from. In fact, do not derive classes from classes that do not declare a virtual destructor (even outside of STL).
Overall, a very good and thorough article. These things I mention are just ones that I've seen experienced programmers choke on and are good to point out earlier rather than later.
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
| Postfix vs. Prefix incrementer
Jeff Bogan | 10:00 22 Apr '04 |
|
|
I just did a speed test of the prefix and postfix incrementer. I created two nested loops of around a null operation. The vec is a vector of 10000 objects.
for (j=0; j<32000; j++)
for (vi=vec.begin(); vi!=vec.end(); v++)
;
and
for (j=0; j<32000; j++)
for (vi=vec.begin(); vi!=vec.end(); ++v)
;
Results:
Prefix: 880 ms
Postfix: 880 ms
To me this says that it does not create any temporary objects.
|
|
|
|
|
|
|
I assume you tested with VC 6 without optimizations. If not, your measurements are indeed surprising.
In the old Dinkumware libraray that is shipped with VC6 vector::iterator is a pointer. So I would be very surprising to have a difference between pre & postincrement.
It is not possible to test with vector::iterator temporaries in VC6, there simply are none.
But in most(all?) other implementations of the standard library, e.g. the new one that is shipped with VC7, vector::iterator is a class.
So, in your simple testcase replace vector with list, then you will get a difference.
Turning on optimizations decreases the difference between pre & postinkrement but most often cannot remove it altogether.
But this is obviously not possible with your testcode because it gets optimized away completely.
|
|
|
|
|
|
|
I guess I should have been more specific by what I meant by "it". Yes - it is the VC6 compiler. So the iterator is a 32-bit pointer which would be no quicker postfix or prefix, and the iterator is not a pointer (VC7 case) but an object and that it's operation gets optimized. I used maximize speed optimization set in the IDE's compliler setup. This is my typical of my practical approach.
|
|
|
|
|
|
|
What he was really getting at has more to do with how the compiler implements pre/postfix incrementers. Most compilers implement postfix in terms of prefix. For example, lets assume prefix is defined for some object like so:
int A::operator++() {return ++a;}
Most compilers will (and should) define a postfix incrementer like so:
int A::operator++(int) {int b = a; ++a; return b;}
Thus, if you are looping with a postfix incrementer (and your compiler didn't optimize this mistake for you), you will be doing 2 extra operations per call (granted, they are fast operations, but 2 extra fast operations is still wasted CPU time when you need to optimize).
Most modern compilers will look at both of the following loops and optimize it to use a prefix incrementer (that is, it will optimize it to correct your code).
Postfix:
for (int i = 0; i < SOME_BIG_NUMBER; i++)
Prefix:
for (int i = 0; i < SOME_BIG_NUMBER; ++i)
Even though the compiler will generally fix this for you, it is always better to write it correctly instead of relying on the compiler's features to fix it for you. You never know when you will be asked to port the code to a system that doesn't have an up-to-date compiler with those cool features and will wonder why you lose performance with the same code on that system.
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
|
|
Have you ever considered that the prefix / postfix issue may be a complete urban myth and it is just an excuse to try to get everyone to change an arbitrary and mostly esthetic programming decision to their way?
A cynic is a man who, when he smells flowers, looks around for a coffin.
-H.L. Mencken
|
|
|
|
|
|
|
JWood wrote: Have you ever considered that the prefix / postfix issue may be a complete urban myth and it is just an excuse to try to get everyone to change an arbitrary and mostly esthetic programming decision to their way?
And if you did consider that, you would be both wrong and paranoid. I was going to go into why, but I've already explained it in the post you responded to, so there is no need to do so further.
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
|
|
OK that was a dumb comment I admit - I was wrong but I think you have missed the point here. You are wrong as well and I think you missed an important point in Summand's post.
If iterator is defined in the template library as a pointer - and it is in VC 6.0 then it is a simple data type and so postfix and prefix are simply order of operation decisions which take the same amount of time - the instructions are just switched around.
If it is a compilers that uses more complex iterators with a higher level of abstraction- that defines iterators as an object, or the iterator is defined as a class then your explanation applies, the original value must be stored so that it can be returned, the iterator is incremented, which takes extra runtime. I don't know how the optimizations work in later compilers, but in this case that is not what happened - looking at the VC 6.0 template headers it can be seen that they are defined as pointers.
A cynic is a man who, when he smells flowers, looks around for a coffin.
-H.L. Mencken
|
|
|
|
|
|
|
JWood wrote: You are wrong as well and I think you missed an important point in Summand's post.
I don't think you understood what I was saying. I wasn't talking about complex iterators vs simple ones (aka pointers). I was talking in general.
JWood wrote: If iterator is defined in the template library as a pointer - and it is in VC 6.0 then it is a simple data type and so postfix and prefix are simply order of operation decisions which take the same amount of time - the instructions are just switched around.
It is much more than JUST and order of operation decision. The following pseudo-code shows the assembly instructions that are used for both:
increment i
push i to stack
copy i to r
increment i
push r to stack
For for loops, that is happening each iteration. So, for 100,000 iterations on a for loop using a post-fix operation, you wasted 100,000 instructions. Granted, they are fast instructions, but still wasted nonetheless.
As you can see, I'm using a simple integer for this example (which is all a pointer is). So, when the iterators become more complex, you end up becoming even more inefficient.
My entire point is to write your code so that it is efficient instead of relying on a compiler to optimize it all for you. If you don't need to previous value of a iterator/integer/pointer/etc, use prefix increment/decrement.
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
|
|
What you call "optimization" I would call competence. I don't work for my compiler, my compiler works for me.
A cynic is a man who, when he smells flowers, looks around for a coffin.
-H.L. Mencken
|
|
|
|
|
|
|
JWood wrote: What you call "optimization" I would call competence. I don't work for my compiler, my compiler works for me.
You can only expect a compiler to do so much for you. At some point, you have to actually think about the code you are writing and write it correctly for yourself instead of hoping the computer will correct it for you. Keep in mind that computers only do exactly what you tell them to, and a compiler is nothing but a computer program.
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
| A good topic
edger | 17:26 15 Apr '04 |
|
|
I wish to give my 5, not just for that this article makes a fairly good point
on what it means to in itsself , but also the INSTRUCTIVE discussion it arouses below.
This is what I really love here. people come to share, people come to
correct and people come to improve.
|
|
|
|
|
| A few more suggestions...
KevinHall | 20:47 13 Apr '04 |
|
|
First of all, I think this is a very good article. I just wanted to point out what IMHO would be a few minor improvements -- but something that will make your tutorial a bit clearer.
* "Vector Demo 2" does not do the same thing as "Vector Demo 1" -- it prints to cout as well. You should probably make "Vector Demo 1" print to cout -- perhaps even using for_each and ostream_iterator. (BTW, I don't know that I'd agree that "Vector Demo 2" is cleaner -- it certainly is easier to understand for the STL newbie, but cleaner???)
* Since this is a tutorial, you probably shouldn't introduce something in your code samples without fully explaining it. In particular, I am talking about "#include <cstring> // same as <string.h>". This does not really explain why someone should use <cstring> over <string.h> or why the ISO comittee created <cstring> -- it probably leaves the newbie with more questions than it really answers. For the sake of the tutorial, you could just use <string.h>. (Either that or you could provide more in depth information.)
* I tend to disagree with your statement "Note: If you are reading the MFC help then you will also come across the efficiency statement of each container. I.E. (log n * n) insertion time. Unless you are dealing with very large number of values, you should ignore this." I don't think this is really something that should be ignored. I would rather write "Note: If you are reading the MFC help then you will also come across the efficiency statement of each container. I.E. (log n * n) insertion time. This information is not important to this introduction, but is an important part of a more in depth study of the STL."
* Suggest some other resources for getting started with the STL. Perhaps Scott Meyers' book "Effective STL"
|
|
|
|
|
| Correction on your conclusion
Anthony_Yio | 17:13 6 Apr '04 |
|
|
As the Chinese say: if you learn it, you will be like a tiger with the claws of an lion.
It should be like a tiger with a pair of wings 如虎添翼
Tiger does not need claws of a lion as it already has it.
Sonork 100.41263:Anthony_Yio
Life is about experiencing ...
|
|
|
|
|
|
|
Hehe I know - It's kind of a joke. Liu Bei and the gang.
|
|
|
|
|
| Some comments and corrections
Summand | 3:52 2 Apr '04 |
|
|
Hi!
I have some comments:
---
Definitions:
A macro for classes? That isn't nearly half the truth. e.g. Functions can be templates too.
An iterator is not a fancy word for pointer, often iterators are classes not pointers.
---
char* szHW = "Hello World";
// This is - as we all know - a character array,
// terminated with a null character
This is not correct. szHW is a pointer to a constant string literal!
So either add a const and change the comment or make an array out of it:
1) const char* szHW = "Hello World";
2) char szHW[] = "Hello World";
---
Also I don't understand why you say that Vector Demo 2 is cleaner, it is quite ugly and hard to understand compared to Demo 1
---
Namespaces: Maybe an advice would be good that using declaration/directives should not be used in headers. There full qualification should be used!
---
vector - Your standard safe array. It is expanded in the "front" direction only.
I dont find this description very good. What does safe mean? And front?
list is not circular. I dont know if the implementation of Plaugher is circular, but there is no guarantee that other implementations are.
And I dont think it is a good advice to tell the people to ignore the efficiency statements in the MFC.
---
Default constructible is _not_ a requirement for classes to be used in Containers. It is also not necessary to overload operator= [If the automatic one does the wrong thing you have to write, thats clear]
The requirements for containers are:
CopyConstructible and Assignable
It is also not required that keys in a map are comparable, you can provide a Compare Functor instead.
class CStudent
{
public :
CStudent(int nSID, int nA)
{ nStudentID=nSID; nAge=nA; }
int nStudentID;
int nAge;
};
is a perfectly valid class to put into a container.
mapStudent["Joe Lennon"] = CStudent(103547, 22);
Okay, with using operator[] you introduce the need for "default constructible".
Use insert instead and and the need for a default constructor disappears:
mapStudent.insert(make_pair(string("Joe Lennon"), CStudent(103547, 22)));
---
typedef:
Never heard of that convention.
Its quite ugly too.
---
ANSI/ISO strings is a very uncommon term. Better use std::string and remove the ANSI/ISO part.
c_str() returns a constant string, that might be a copy(!). This is sometimes overlooked.
---
Iterator: Your description is very unclear and partly plain wrong.
There are several iterator categories, Output, Input, Forward, Bidirectional, Random Access.
e.g. vector provides a random access iterator, list a bidirectional one.
Their meaning is quite clearly explained in the MSDN.
reverse_bidirectional_iterator does not exist.
---
greater is functor not a function.
---
Derive or Embed Template
The second example is very bad style. You should not derive from a container unless it is absolutely necessary and/or you know exactly what you do.
|
|
|
|
|
|
|
Thanks for your comments - you clearly have very good grasp of STL and definite ideas on what is correct and what is not. Please take this in the spirit of practical learning, though, which is the theme of the article. People with a firm grasp of the medium are often the worst teachers, becuase you far removed from someone starting with zero experience. I understand the wish to instill good habits, but at the same time you must bridge the gap to allow a student to have a running start at a subject and not discourage them.
My personal experience with STL: What I found was that STL was so wrapped up in "exactitude" that it is very difficult to learn. I wrote this to deliberately cut away at the unnecessary subjects that do not need to be introduced yet.
I don't think anything here is wrong. It might be considered sloppy and you may not agree with it - but if you don't like it don't read the article - it is not meant for someone already knows STL.
|
|
|
|
|
|
|
First, I teach C++ and since the students evaluate me very good I think I'm quite good at it. But I demand much, thats for sure.
Your article gives a very good introduction to the STL and its contents, but there are some mistakes in it. In my opinion, a teacher has the responsibility to be as accurate as possible.
I did not mean my comments as an attack or something, I just wanted to highlight points I think are problematic.
|
|
|
|
|
|
|
Yes you have some very good points - I have just updated the article to reflect this.
|
|
|
|
|
|
|
Summand wrote:
Derive or Embed Template
The second example is very bad style. You should not derive from a container unless it is absolutely necessary and/or you know exactly what you do.
Summand,
I have heard this before and so I have blindly avoided this practice without understanding exactly why. In some cases I resorted to providing "wrapper" member functions in my container class to reference an internal STL container. This becomes tedious. I have heard some state that most STL containers do not have virtual destructors, so a destructor in the derived class will never be called. Is this true? Do you know WHY this is not a good idea?
|
|
|
|
|
|
|
Its difficult to explain this in few words but I will try.
First, most of the time it is not a problem if a destructor of a base class is not virtual. There is just one case, when there is a problem:
class Base {}; // No virtual destructor
class Derived : public Base {};
Base * base = new Derived;
delete base;
delete is very bad here because it calls only the destructor of Base and not the destructor of Derived. This may lead to very evil errors.
With a virtual destructor you are always on the safe side but it is less efficient.
If you can avoid to delete an object through a base pointer you also have no problem.
In designing a new class you have to make the choice, virtual or not.
For very good reasons the containers in the STL have no virtual destructors.
The main reason for my statement that you shouldn't derive public from vector is not the above but that "derive public" means "IS A".
So you say in your example "CParam is a vector". That statement is only seldom true.
Also, you should strige to minimize the coupling between classes. If you derive from a class they are coupled very tight. It often becomes impossible to replace vector by another class thats more suitable because you don't know which functions of vector might be used somewhere.
Deriving to inherit code isn't that good, but if you need it, often this is a better way:
class CParam : private vector<double>
{
public:
using vector::size;
using vector::push_back;
// And so on.
};
With using you make all functions visible you need, but not more.
But, although it is tedious, prefer to aggregate.
|
|
|
|
|
|
|
Last Updated 13 Apr 2004 |
Advertise |
Privacy |
Terms of Use |
Copyright ©
CodeProject, 1999-2010
