Effective STL

Scott Meyers

Mentioned 78

"This is Effective C++ volume three - it's really that good." - Herb Sutter, independent consultant and secretary of the ISO/ANSI C++ standards committee "There are very few books which all C++ programmers must have. Add Effective STL to that list." - Thomas Becker, Senior Software Engineer, Zephyr Associates, Inc., and columnist, C/C++ Users Journal C++'s Standard Template Library is revolutionary, but learning to use it well has always been a challenge. Until now. In this book, best-selling author Scott Meyers ( Effective C++ , and More Effective C++ ) reveals the critical rules of thumb employed by the experts - the things they almost always do or almost always avoid doing - to get the most out of the library. Other books describe what's in the STL. Effective STL shows you how to use it. Each of the book's 50 guidelines is backed by Meyers' legendary analysis and incisive examples, so you'll learn not only what to do, but also when to do it - and why. Highlights of Effective STL include: Advice on choosing among standard STL containers (like vector and list), nonstandard STL containers (like hash_set and hash_map), and non-STL containers (like bitset). Techniques to maximize the efficiency of the STL and the programs that use it. Insights into the behavior of iterators, function objects, and allocators, including things you should not do. Guidance for the proper use of algorithms and member functions whose names are the same (e.g., find), but whose actions differ in subtle (but important) ways. Discussions of potential portability problems, including straightforward ways to avoid them. Like Meyers' previous books, Effective STL is filled with proven wisdom that comes only from experience. Its clear, concise, penetrating style makes it an essential resource for every STL programmer.

More on Amazon.com

Mentioned in questions and answers.

This question attempts to collect the few pearls among the dozens of bad C++ books that are published every year.

Unlike many other programming languages, which are often picked up on the go from tutorials found on the Internet, few are able to quickly pick up C++ without studying a well-written C++ book. It is way too big and complex for doing this. In fact, it is so big and complex, that there are very many very bad C++ books out there. And we are not talking about bad style, but things like sporting glaringly obvious factual errors and promoting abysmally bad programming styles.

Please edit the accepted answer to provide quality books and an approximate skill level — preferably after discussing your addition in the C++ chat room. (The regulars might mercilessly undo your work if they disagree with a recommendation.) Add a short blurb/description about each book that you have personally read/benefited from. Feel free to debate quality, headings, etc. Books that meet the criteria will be added to the list. Books that have reviews by the Association of C and C++ Users (ACCU) have links to the review.

Note: FAQs and other resources can be found in the C++ tag info and under . There is also a similar post for C: The Definitive C Book Guide and List


Introductory, no previous programming experience

  • Programming: Principles and Practice Using C++ (Bjarne Stroustrup) (updated for C++11/C++14) An introduction to programming using C++ by the creator of the language. A good read, that assumes no previous programming experience, but is not only for beginners.

Introductory, with previous programming experience

  • C++ Primer * (Stanley Lippman, Josée Lajoie, and Barbara E. Moo) (updated for C++11) Coming at 1k pages, this is a very thorough introduction into C++ that covers just about everything in the language in a very accessible format and in great detail. The fifth edition (released August 16, 2012) covers C++11. [Review]

  • A Tour of C++ (Bjarne Stroustrup) (EBOOK) The “tour” is a quick (about 180 pages and 14 chapters) tutorial overview of all of standard C++ (language and standard library, and using C++11) at a moderately high level for people who already know C++ or at least are experienced programmers. This book is an extended version of the material that constitutes Chapters 2-5 of The C++ Programming Language, 4th edition.

  • Accelerated C++ (Andrew Koenig and Barbara Moo) This basically covers the same ground as the C++ Primer, but does so on a fourth of its space. This is largely because it does not attempt to be an introduction to programming, but an introduction to C++ for people who've previously programmed in some other language. It has a steeper learning curve, but, for those who can cope with this, it is a very compact introduction into the language. (Historically, it broke new ground by being the first beginner's book to use a modern approach at teaching the language.) [Review]

  • Thinking in C++ (Bruce Eckel) Two volumes; is a tutorial style free set of intro level books. Downloads: vol 1, vol 2. Unfortunately they’re marred by a number of trivial errors (e.g. maintaining that temporaries are automatically const), with no official errata list. A partial 3rd party errata list is available at (http://www.computersciencelab.com/Eckel.htm), but it’s apparently not maintained.

* Not to be confused with C++ Primer Plus (Stephen Prata), with a significantly less favorable review.

Best practices

  • Effective C++ (Scott Meyers) This was written with the aim of being the best second book C++ programmers should read, and it succeeded. Earlier editions were aimed at programmers coming from C, the third edition changes this and targets programmers coming from languages like Java. It presents ~50 easy-to-remember rules of thumb along with their rationale in a very accessible (and enjoyable) style. For C++11 and C++14 the examples and a few issues are outdated and Effective Modern C++ should be preferred. [Review]

  • Effective Modern C++ (Scott Meyers) This is basically the new version of Effective C++, aimed at C++ programmers making the transition from C++03 to C++11 and C++14.

  • Effective STL (Scott Meyers) This aims to do the same to the part of the standard library coming from the STL what Effective C++ did to the language as a whole: It presents rules of thumb along with their rationale. [Review]


  • More Effective C++ (Scott Meyers) Even more rules of thumb than Effective C++. Not as important as the ones in the first book, but still good to know.

  • Exceptional C++ (Herb Sutter) Presented as a set of puzzles, this has one of the best and thorough discussions of the proper resource management and exception safety in C++ through Resource Acquisition is Initialization (RAII) in addition to in-depth coverage of a variety of other topics including the pimpl idiom, name lookup, good class design, and the C++ memory model. [Review]

  • More Exceptional C++ (Herb Sutter) Covers additional exception safety topics not covered in Exceptional C++, in addition to discussion of effective object oriented programming in C++ and correct use of the STL. [Review]

  • Exceptional C++ Style (Herb Sutter) Discusses generic programming, optimization, and resource management; this book also has an excellent exposition of how to write modular code in C++ by using nonmember functions and the single responsibility principle. [Review]

  • C++ Coding Standards (Herb Sutter and Andrei Alexandrescu) “Coding standards” here doesn't mean “how many spaces should I indent my code?” This book contains 101 best practices, idioms, and common pitfalls that can help you to write correct, understandable, and efficient C++ code. [Review]

  • C++ Templates: The Complete Guide (David Vandevoorde and Nicolai M. Josuttis) This is the book about templates as they existed before C++11. It covers everything from the very basics to some of the most advanced template metaprogramming and explains every detail of how templates work (both conceptually and at how they are implemented) and discusses many common pitfalls. Has excellent summaries of the One Definition Rule (ODR) and overload resolution in the appendices. A second edition is scheduled for 2017. [Review]


  • Modern C++ Design (Andrei Alexandrescu) A groundbreaking book on advanced generic programming techniques. Introduces policy-based design, type lists, and fundamental generic programming idioms then explains how many useful design patterns (including small object allocators, functors, factories, visitors, and multimethods) can be implemented efficiently, modularly, and cleanly using generic programming. [Review]

  • C++ Template Metaprogramming (David Abrahams and Aleksey Gurtovoy)

  • C++ Concurrency In Action (Anthony Williams) A book covering C++11 concurrency support including the thread library, the atomics library, the C++ memory model, locks and mutexes, as well as issues of designing and debugging multithreaded applications.

  • Advanced C++ Metaprogramming (Davide Di Gennaro) A pre-C++11 manual of TMP techniques, focused more on practice than theory. There are a ton of snippets in this book, some of which are made obsolete by typetraits, but the techniques, are nonetheless useful to know. If you can put up with the quirky formatting/editing, it is easier to read than Alexandrescu, and arguably, more rewarding. For more experienced developers, there is a good chance that you may pick up something about a dark corner of C++ (a quirk) that usually only comes about through extensive experience.

Reference Style - All Levels

  • The C++ Programming Language (Bjarne Stroustrup) (updated for C++11) The classic introduction to C++ by its creator. Written to parallel the classic K&R, this indeed reads very much alike it and covers just about everything from the core language to the standard library, to programming paradigms to the language's philosophy. [Review]

  • C++ Standard Library Tutorial and Reference (Nicolai Josuttis) (updated for C++11) The introduction and reference for the C++ Standard Library. The second edition (released on April 9, 2012) covers C++11. [Review]

  • The C++ IO Streams and Locales (Angelika Langer and Klaus Kreft) There's very little to say about this book except that, if you want to know anything about streams and locales, then this is the one place to find definitive answers. [Review]

C++11/14 References:

  • The C++ Standard (INCITS/ISO/IEC 14882-2011) This, of course, is the final arbiter of all that is or isn't C++. Be aware, however, that it is intended purely as a reference for experienced users willing to devote considerable time and effort to its understanding. As usual, the first release was quite expensive ($300+ US), but it has now been released in electronic form for $60US.

  • The C++14 standard is available, but seemingly not in an economical form – directly from the ISO it costs 198 Swiss Francs (about $200 US). For most people, the final draft before standardization is more than adequate (and free). Many will prefer an even newer draft, documenting new features that are likely to be included in C++17.

  • Overview of the New C++ (C++11/14) (PDF only) (Scott Meyers) (updated for C++1y/C++14) These are the presentation materials (slides and some lecture notes) of a three-day training course offered by Scott Meyers, who's a highly respected author on C++. Even though the list of items is short, the quality is high.

  • The C++ Core Guidelines (C++11/14/17/…) (edited by Bjarne Stroustrup and Herb Sutter) is an evolving online document consisting of a set of guidelines for using modern C++ well. The guidelines are focused on relatively higher-level issues, such as interfaces, resource management, memory management and concurrency affecting application architecture and library design. The project was announced at CppCon'15 by Bjarne Stroustrup and others and welcomes contributions from the community. Most guidelines are supplemented with a rationale and examples as well as discussions of possible tool support. Many rules are designed specifically to be automatically checkable by static analysis tools.

  • The C++ Super-FAQ (Marshall Cline, Bjarne Stroustrup and others) is an effort by the Standard C++ Foundation to unify the C++ FAQs previously maintained individually by Marshall Cline and Bjarne Stroustrup and also incorporating new contributions. The items mostly address issues at an intermediate level and are often written with a humorous tone. Not all items might be fully up to date with the latest edition of the C++ standard yet.

  • cppreference.com (C++03/11/14/17/…) (initiated by Nate Kohl) is a wiki that summarizes the basic core-language features and has extensive documentation of the C++ standard library. The documentation is very precise but is easier to read than the official standard document and provides better navigation due to its wiki nature. The project documents all versions of the C++ standard and the site allows filtering the display for a specific version. The project was presented by Nate Kohl at CppCon'14.

Classics / Older

Note: Some information contained within these books may not be up-to-date or no longer considered best practice.

  • The Design and Evolution of C++ (Bjarne Stroustrup) If you want to know why the language is the way it is, this book is where you find answers. This covers everything before the standardization of C++.

  • Ruminations on C++ - (Andrew Koenig and Barbara Moo) [Review]

  • Advanced C++ Programming Styles and Idioms (James Coplien) A predecessor of the pattern movement, it describes many C++-specific “idioms”. It's certainly a very good book and might still be worth a read if you can spare the time, but quite old and not up-to-date with current C++.

  • Large Scale C++ Software Design (John Lakos) Lakos explains techniques to manage very big C++ software projects. Certainly a good read, if it only was up to date. It was written long before C++98, and misses on many features (e.g. namespaces) important for large scale projects. If you need to work in a big C++ software project, you might want to read it, although you need to take more than a grain of salt with it. The first volume of a new edition is expected in 2015.

  • Inside the C++ Object Model (Stanley Lippman) If you want to know how virtual member functions are commonly implemented and how base objects are commonly laid out in memory in a multi-inheritance scenario, and how all this affects performance, this is where you will find thorough discussions of such topics.

  • The Annotated C++ Reference Manual (Bjarne Stroustrup, Margaret A. Ellis) This book is quite outdated in the fact that it explores the 1989 C++ 2.0 version - Templates, exceptions, namespaces and new casts were not yet introduced. Saying that however this is book goes through the entire C++ standard of the time explaining the rationale, the possible implementations and features of the language. This is not a book not learn programming principles and patterns on C++, but to understand every aspect of the C++ language.

Someone brought this article to my attention that claims (I'm paraphrasing) the STL term is misused to refer to the entire C++ Standard Library instead of the parts that were taken from SGI STL.

(...) it refers to the "STL", despite the fact that very few people still use the STL (which was designed at SGI).

Parts of the C++ Standard Library were based on parts of the STL, and it is these parts that many people (including several authors and the notoriously error-ridden cplusplus.com) still refer to as "the STL". However, this is inaccurate; indeed, the C++ standard never mentions "STL", and there are content differences between the two.

(...) "STL" is rarely used to refer to the bits of the stdlib that happen to be based on the SGI STL. People think it's the entire standard library. It gets put on CVs. And it is misleading.

I hardly know anything about C++'s history so I can't judge the article's correctness. Should I refrain from using the term STL? Or is this an isolated opinion?

I've made this same argument recently, but I believe a little tolerance can be allowed. If Scott Meyers makes the same mistake, you're in good company.

It wasn't that long ago that I was a beginning coder, trying to find good books/tutorials on languages I wanted to learn. Even still, there are times I need to pick up a language relatively quickly for a new project I am working on. The point of this post is to document some of the best tutorials and books for these languages. I will start the list with the best I can find, but hope you guys out there can help with better suggestions/new languages. Here is what I found:

Since this is now wiki editable, I am giving control up to the community. If you have a suggestion, please put it in this section. I decided to also add a section for general be a better programmer books and online references as well. Once again, all recommendations are welcome.

General Programming

Online Tutorials
Foundations of Programming By Karl Seguin - From Codebetter, its C# based but the ideas ring true across the board, can't believe no-one's posted this yet actually.
How to Write Unmaintainable Code - An anti manual that teaches you how to write code in the most unmaintable way possible. It would be funny if a lot of these suggestions didn't ring so true.
The Programming Section of Wiki Books - suggested by Jim Robert as having a large amount of books/tutorials on multiple languages in various stages of completion
Just the Basics To get a feel for a language.

Code Complete - This book goes without saying, it is truely brilliant in too many ways to mention.
The Pragmatic Programmer - The next best thing to working with a master coder, teaching you everything they know.
Mastering Regular Expressions - Regular Expressions are an essential tool in every programmer's toolbox. This book, recommended by Patrick Lozzi is a great way to learn what they are capable of.
Algorithms in C, C++, and Java - A great way to learn all the classic algorithms if you find Knuth's books a bit too in depth.


Online Tutorials
This tutorial seems to pretty consise and thourough, looked over the material and seems to be pretty good. Not sure how friendly it would be to new programmers though.
K&R C - a classic for sure. It might be argued that all programmers should read it.
C Primer Plus - Suggested by Imran as being the ultimate C book for beginning programmers.
C: A Reference Manual - A great reference recommended by Patrick Lozzi.


Online Tutorials
The tutorial on cplusplus.com seems to be the most complete. I found another tutorial here but it doesn't include topics like polymorphism, which I believe is essential. If you are coming from C, this tutorial might be the best for you.

Another useful tutorial, C++ Annotation. In Ubuntu family you can get the ebook on multiple format(pdf, txt, Postscript, and LaTex) by installing c++-annotation package from Synaptic(installed package can be found in /usr/share/doc/c++-annotation/.

The C++ Programming Language - crucial for any C++ programmer.
C++ Primer Plus - Orginally added as a typo, but the amazon reviews are so good, I am going to keep it here until someone says it is a dud.
Effective C++ - Ways to improve your C++ programs.
More Effective C++ - Continuation of Effective C++.
Effective STL - Ways to improve your use of the STL.
Thinking in C++ - Great book, both volumes. Written by Bruce Eckel and Chuck Ellison.
Programming: Principles and Practice Using C++ - Stroustrup's introduction to C++.
Accelerated C++ - Andy Koenig and Barbara Moo - An excellent introduction to C++ that doesn't treat C++ as "C with extra bits bolted on", in fact you dive straight in and start using STL early on.


FORTH, a text and reference. Mahlon G. Kelly and Nicholas Spies. ISBN 0-13-326349-5 / ISBN 0-13-326331-2. 1986 Prentice-Hall. Leo Brodie's books are good but this book is even better. For instance it covers defining words and the interpreter in depth.


Online Tutorials
Sun's Java Tutorials - An official tutorial that seems thourough, but I am not a java expert. You guys know of any better ones?
Head First Java - Recommended as a great introductory text by Patrick Lozzi.
Effective Java - Recommended by pek as a great intermediate text.
Core Java Volume 1 and Core Java Volume 2 - Suggested by FreeMemory as some of the best java references available.
Java Concurrency in Practice - Recommended by MDC as great resource for concurrent programming in Java.

The Java Programing Language


Online Tutorials
Python.org - The online documentation for this language is pretty good. If you know of any better let me know.
Dive Into Python - Suggested by Nickola. Seems to be a python book online.


Online Tutorials
perldoc perl - This is how I personally got started with the language, and I don't think you will be able to beat it.
Learning Perl - a great way to introduce yourself to the language.
Programming Perl - greatly referred to as the Perl Bible. Essential reference for any serious perl programmer.
Perl Cookbook - A great book that has solutions to many common problems.
Modern Perl Programming - newly released, contains the latest wisdom on modern techniques and tools, including Moose and DBIx::Class.


Online Tutorials
Adam Mika suggested Why's (Poignant) Guide to Ruby but after taking a look at it, I don't know if it is for everyone. Found this site which seems to offer several tutorials for Ruby on Rails.
Programming Ruby - suggested as a great reference for all things ruby.

Visual Basic

Online Tutorials
Found this site which seems to devote itself to visual basic tutorials. Not sure how good they are though.


Online Tutorials
The main PHP site - A simple tutorial that allows user comments for each page, which I really like. PHPFreaks Tutorials - Various tutorials of different difficulty lengths.
Quakenet/PHP tutorials - PHP tutorial that will guide you from ground up.


Online Tutorials
Found a decent tutorial here geared toward non-programmers. Found another more advanced one here. Nickolay suggested A reintroduction to javascript as a good read here.

Head first JavaScript
JavaScript: The Good Parts (with a Google Tech Talk video by the author)


Online Tutorials
C# Station Tutorial - Seems to be a decent tutorial that I dug up, but I am not a C# guy.
C# Language Specification - Suggested by tamberg. Not really a tutorial, but a great reference on all the elements of C#
C# to the point - suggested by tamberg as a short text that explains the language in amazing depth


nlucaroni suggested the following:
OCaml for Scientists Introduction to ocaml
Using Understand and unraveling ocaml: practice to theory and vice versa
Developing Applications using Ocaml - O'Reilly
The Objective Caml System - Official Manua


Online Tutorials
nlucaroni suggested the following:
Explore functional programming with Haskell
Real World Haskell
Total Functional Programming


wfarr suggested the following:
The Little Schemer - Introduction to Scheme and functional programming in general
The Seasoned Schemer - Followup to Little Schemer.
Structure and Interpretation of Computer Programs - The definitive book on Lisp (also available online).
Practical Common Lisp - A good introduction to Lisp with several examples of practical use.
On Lisp - Advanced Topics in Lisp
How to Design Programs - An Introduction to Computing and Programming
Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp - an approach to high quality Lisp programming

What about you guys? Am I totally off on some of there? Did I leave out your favorite language? I will take the best comments and modify the question with the suggestions.

Java: SCJP for Java 6. I still use it as a reference.


O'Reilly Book:

  1. Real World Haskell, a great tutorial-oriented book on Haskell, available online and in print.

My favorite general, less academic online tutorials:

  1. The Haskell wikibook which contains all of the excellent Yet Another Haskell Tutorial. (This tutorial helps with specifics of setting up a Haskell distro and running example programs, for example.)
  2. Learn you a Haskell for Great Good, in the spirit of Why's Poignant Guide to Ruby but more to the point.
  3. Write yourself a Scheme in 48 hours. Get your hands dirty learning Haskell with a real project.

Books on Functional Programming with Haskell:

  1. Lambda calculus, combinators, more theoretical, but in a very down to earth manner: Davie's Introduction to Functional Programming Systems Using Haskell
  2. Laziness and program correctness, thinking functionally: Bird's Introduction to Functional Programming Using Haskell

Some books on Java I'd recommend:

For Beginners: Head First Java is an excellent introduction to the language. And I must also mention Head First Design Patterns which is a great resource for learners to grasp what can be quite challenging concepts. The easy-going fun style of these books are ideal for ppl new to programming.

A really thorough, comprehensive book on Java SE is Bruce Eckel's Thinking In Java v4. (At just under 1500 pages it's good for weight-training as well!) For those of us not on fat bank-bonuses there are older versions available for free download.

Of course, as many ppl have already mentioned, Josh Bloch's Effective Java v2 is an essential part of any Java developer's library.

Let's not forget Head First Java, which could be considered the essential first step in this language or maybe the step after the online tutorials by Sun. It's great for the purpose of grasping the language concisely, while adding a bit of fun, serving as a stepping stone for the more in-depth books already mentioned.

Sedgewick offers great series on Algorithms which are a must-have if you find Knuth's books to be too in-depth. Knuth aside, Sedgewick brings a solid approach to the field and he offers his books in C, C++ and Java. The C++ books could be used backwardly on C since he doesn't make a very large distinction between the two languages in his presentation.

Whenever I'm working on C, C:A Reference Manual, by Harbison and Steele, goes with me everywhere. It's concise and efficient while being extremely thorough making it priceless(to me anyways).

Languages aside, and if this thread is to become a go-to for references in which I think it's heading that way due to the number of solid contributions, please include Mastering Regular Expressions, for reasons I think most of us are aware of... some would also say that regex can be considered a language in its own right. Further, its usefulness in a wide array of languages makes it invaluable.

C: “Programming in C”, Stephen G. Kochan, Developer's Library.

Organized, clear, elaborate, beautiful.


The first one is good for beginners and the second one requires more advanced level in C++.

I know this is a cross post from here... but, I think one of the best Java books is Java Concurrency in Practice by Brian Goetz. A rather advanced book - but, it will wear well on your concurrent code and Java development in general.


C# to the Point by Hanspeter Mössenböck. On a mere 200 pages he explains C# in astonishing depth, focusing on underlying concepts and concise examples rather than hand waving and Visual Studio screenshots.

For additional information on specific language features, check the C# language specification ECMA-334.

Framework Design Guidelines, a book by Krzysztof Cwalina and Brad Abrams from Microsoft, provides further insight into the main design decisions behind the .NET library.

For Lisp and Scheme (hell, functional programming in general), there are few things that provide a more solid foundation than The Little Schemer and The Seasoned Schemer. Both provide a very simple and intuitive introduction to both Scheme and functional programming that proves far simpler for new students or hobbyists than any of the typical volumes that rub off like a nonfiction rendition of War & Peace.

Once they've moved beyond the Schemer series, SICP and On Lisp are both fantastic choices.

For C++ I am a big fan of C++ Common Knowledge: Essential Intermediate Programming, I like that it is organized into small sections (usually less than 5 pages per topic) So it is easy for me to grab it and read up on concepts that I need to review.

It is a must read for me the night before and on the plane to a job interview.

C Primer Plus, 5th Edition - The C book to get if you're learning C without any prior programming experience. It's a personal favorite of mine as I learned to program from this book. It has all the qualities a beginner friendly book should have:

  • Doesn't assume any prior exposure to programming
  • Enjoyable to read (without becoming annoying like For Dummies /
  • Doesn't oversimplify

For Javascript:

For PHP:

For OO design & programming, patterns:

For Refactoring:


  • C - The C Programming Language - Obviously I had to reference K&R, one of the best programming books out there full stop.
  • C++ - Accelerated C++ - This clear, well written introduction to C++ goes straight to using the STL and gives nice, clear, practical examples. Lives up to its name.
  • C# - Pro C# 2008 and the .NET 3.5 Platform - Bit of a mouthful but wonderfully written and huge depth.
  • F# - Expert F# - Designed to take experienced programmers from zero to expert in F#. Very well written, one of the author's invented F# so you can't go far wrong!
  • Scheme - The Little Schemer - Really unique approach to teaching a programming language done really well.
  • Ruby - Programming Ruby - Affectionately known as the 'pick axe' book, this is THE defacto introduction to Ruby. Very well written, clear and detailed.

Are there guidelines on how one should write new container which will behave like any STL container?

You will need to read the C++ Standard section about Containers and requirements the C++ Standard imposes for container implementations.

The relevant chapter in C++03 standard is:

Section 23.1 Container Requirements

The relevant chapter in C++11 standard is:

Section 23.2 Container Requirements

The near-final draft of the C++11 standard is freely available here.

You might as well, read some excellent books which will help you understand the requirements from an perspective of user of the container. Two excellent books which struck my mind easily are:

Effective STL by Scott Meyers &
The C++ Standard Library: A Tutorial and Reference by Nicolai Josutils

Assuming a map where you want to preserve existing entries. 20% of the time, the entry you are inserting is new data. Is there an advantage to doing std::map::find then std::map::insert using that returned iterator? Or is it quicker to attempt the insert and then act based on whether or not the iterator indicates the record was or was not inserted?

The answer is you do neither. Instead you want to do something suggested by Item 24 of Effective STL by Scott Meyers:

typedef map<int, int> MapType;    // Your map type may vary, just change the typedef

MapType mymap;
// Add elements to map here
int k = 4;   // assume we're searching for keys equal to 4
int v = 0;   // assume we want the value 0 associated with the key of 4

MapType::iterator lb = mymap.lower_bound(k);

if(lb != mymap.end() && !(mymap.key_comp()(k, lb->first)))
    // key already exists
    // update lb->second if you care to
    // the key does not exist in the map
    // add it to the map
    mymap.insert(lb, MapType::value_type(k, v));    // Use lb as a hint to insert,
                                                    // so it can avoid another lookup

Parentheses in C++ are used in many places: e.g. in function calls and grouping expressions to override operator precedence. Apart from illegal extra parentheses (such as around function call argument lists), a general -but not absolute- rule of C++ is that extra parentheses never hurt:

5.1 Primary expressions [expr.prim]

5.1.1 General [expr.prim.general]

6 A parenthesized expression is a primary expression whose type and value are identical to those of the enclosed expression. The presence of parentheses does not affect whether the expression is an lvalue. The parenthesized expression can be used in exactly the same contexts as those where the enclosed expression can be used, and with the same meaning, except as otherwise indicated.

Question: in which contexts do extra parentheses change the meaning of a C++ program, other than overriding basic operator precedence?

NOTE: I consider the restriction of pointer-to-member syntax to &qualified-id without parentheses to be outside the scope because it restricts syntax rather than allowing two syntaxes with different meanings. Similarly, the use of parentheses inside preprocessor macro definitions also guards against unwanted operator precedence.


Extra parentheses change the meaning of a C++ program in the following contexts:

  • preventing argument-dependent name lookup
  • enabling the comma operator in list contexts
  • ambiguity resolution of vexing parses
  • deducing referenceness in decltype expressions
  • preventing preprocessor macro errors

Preventing argument-dependent name lookup

As is detailed in Annex A of the Standard, a post-fix expression of the form (expression) is a primary expression, but not an id-expression, and therefore not an unqualified-id. This means that argument-dependent name lookup is prevented in function calls of the form (fun)(arg) compared to the conventional form fun(arg).

3.4.2 Argument-dependent name lookup [basic.lookup.argdep]

1 When the postfix-expression in a function call (5.2.2) is an unqualified-id, other namespaces not considered during the usual unqualified lookup (3.4.1) may be searched, and in those namespaces, namespace-scope friend function or function template declarations (11.3) not otherwise visible may be found. These modifications to the search depend on the types of the arguments (and for template template arguments, the namespace of the template argument). [ Example:

namespace N {
    struct S { };
    void f(S);

void g() {
    N::S s;
    f(s);   // OK: calls N::f
    (f)(s); // error: N::f not considered; parentheses
            // prevent argument-dependent lookup

—end example ]

Enabling the comma operator in list contexts

The comma operator has a special meaning in most list-like contexts (function and template arguments, initializer lists etc.). Parentheses of the form a, (b, c), d in such contexts can enable the comma operator compared to the regular form a, b, c, d where the comma operator does not apply.

5.18 Comma operator [expr.comma]

2 In contexts where comma is given a special meaning, [ Example: in lists of arguments to functions (5.2.2) and lists of initializers (8.5) —end example ] the comma operator as described in Clause 5 can appear only in parentheses. [ Example:

f(a, (t=3, t+2), c);

has three arguments, the second of which has the value 5. —end example ]

Ambiguity resolution of vexing parses

Backward compatibility with C and its arcane function declaration syntax can lead to surprising parsing ambiguities, known as vexing parses. Essentially, anything that can be parsed as a declaration will be parsed as one, even though a competing parse would also apply.

6.8 Ambiguity resolution [stmt.ambig]

1 There is an ambiguity in the grammar involving expression-statements and declarations: An expression-statement with a function-style explicit type conversion (5.2.3) as its leftmost subexpression can be indistinguishable from a declaration where the first declarator starts with a (. In those cases the statement is a declaration.

8.2 Ambiguity resolution [dcl.ambig.res]

1 The ambiguity arising from the similarity between a function-style cast and a declaration mentioned in 6.8 can also occur in the context of a declaration. In that context, the choice is between a function declaration with a redundant set of parentheses around a parameter name and an object declaration with a function-style cast as the initializer. Just as for the ambiguities mentioned in 6.8, the resolution is to consider any construct that could possibly be a declaration a declaration. [ Note: A declaration can be explicitly disambiguated by a nonfunction-style cast, by an = to indicate initialization or by removing the redundant parentheses around the parameter name. —end note ] [ Example:

struct S {

void foo(double a) {
    S w(int(a));  // function declaration
    S x(int());   // function declaration
    S y((int)a);  // object declaration
    S z = int(a); // object declaration

—end example ]

A famous example of this is the Most Vexing Parse, a name popularized by Scott Meyers in Item 6 of his Effective STL book:

ifstream dataFile("ints.dat");
list<int> data(istream_iterator<int>(dataFile), // warning! this doesn't do
               istream_iterator<int>());        // what you think it does

This declares a function, data, whose return type is list<int>. The function data takes two parameters:

  • The first parameter is named dataFile. It's type is istream_iterator<int>. The parentheses around dataFile are superfluous and are ignored.
  • The second parameter has no name. Its type is pointer to function taking nothing and returning an istream_iterator<int>.

Placing extra parentheses around the first function argument (parentheses around the second argument are illegal) will resolve the ambiguity

list<int> data((istream_iterator<int>(dataFile)), // note new parens
                istream_iterator<int>());          // around first argument
                                                  // to list's constructor

C++11 has brace-initializer syntax that allows to side-step such parsing problems in many contexts.

Deducing referenceness in decltype expressions

In contrast to auto type deduction, decltype allows referenceness (lvalue and rvalue references) to be deduced. The rules distinguish between decltype(e) and decltype((e)) expressions: Simple type specifiers [dcl.type.simple]

4 For an expression e, the type denoted by decltype(e) is defined as follows:

— if e is an unparenthesized id-expression or an unparenthesized class member access (5.2.5), decltype(e) is the type of the entity named by e. If there is no such entity, or if e names a set of overloaded functions, the program is ill-formed;

— otherwise, if e is an xvalue, decltype(e) is T&&, where T is the type of e;

— otherwise, if e is an lvalue, decltype(e) is T&, where T is the type of e;

— otherwise, decltype(e) is the type of e.

The operand of the decltype specifier is an unevaluated operand (Clause 5). [ Example:

const int&& foo();
int i;
struct A { double x; };
const A* a = new A();
decltype(foo()) x1 = 0;   // type is const int&&
decltype(i) x2;           // type is int
decltype(a->x) x3;        // type is double
decltype((a->x)) x4 = x3; // type is const double&

—end example ] [ Note: The rules for determining types involving decltype(auto) are specified in —end note ]

The rules for decltype(auto) have a similar meaning for extra parentheses in the RHS of the initializing expression. Here's an example from the C++FAQ and this related Q&A

decltype(auto) look_up_a_string_1() { auto str = lookup1(); return str; }  //A
decltype(auto) look_up_a_string_2() { auto str = lookup1(); return(str); } //B

The first returns string, the second returns string &, which is a reference to the local variable str.

Preventing preprocessor macro related errors

There is a host of subtleties with preprocessor macros in their interaction with the C++ language proper, the most common of which are listed below

  • using parentheses around macro parameters inside the macro definition #define TIMES(A, B) (A) * (B); in order to avoid unwanted operator precedence (e.g. in TIMES(1 + 2, 2 + 1) which yields 9 but would yield 6 without the parentheses around (A) and (B)
  • using parentheses around macro arguments having commas inside: assert((std::is_same<int, int>::value)); which would otherwise not compile
  • using parentheses around a function to protect against macro expansion in included headers: (min)(a, b) (with the unwanted side effect of also disabling ADL)

I remember first learning about vectors in the STL and after some time, I wanted to use a vector of bools for one of my projects. After seeing some strange behavior and doing some research, I learned that a vector of bools is not really a vector of bools.

Are there any other common pitfalls to avoid in C++?

Some must have C++ books that will help you avoid common C++ pitfalls:

Effective C++
More Effective C++
Effective STL

The Effective STL book explains the vector of bools issue :)

I've already mentioned it a few times, but Scott Meyers' books Effective C++ and Effective STL are really worth their weight in gold for helping with C++.

Come to think of it, Steven Dewhurst's C++ Gotchas is also an excellent "from the trenches" resource. His item on rolling your own exceptions and how they should be constructed really helped me in one project.

I am curious to know how std::string is implemented and how does it differ from c string?If the standard does not specify any implementation then any implementation with explanation would be great with how it satisfies the string requirement given by standard?

Virtually every compiler I've used provides source code for the runtime - so whether you're using GCC or MSVC or whatever, you have the capability to look at the implementation. However, a large part or all of std::string will be implemented as template code, which can make for very difficult reading.

Scott Meyer's book, Effective STL, has a chapter on std::string implementations that's a decent overview of the common variations: "Item 15: Be aware of variations in string implementations".

He talks about 4 variations:

  • several variations on a ref-counted implementation (commonly known as copy on write) - when a string object is copied unchanged, the refcount is incremented but the actual string data is not. Both object point to the same refcounted data until one of the objects modifies it, causing a 'copy on write' of the data. The variations are in where things like the refcount, locks etc are stored.

  • a "short string optimization" (SSO) implementation. In this variant, the object contains the usual pointer to data, length, size of the dynamically allocated buffer, etc. But if the string is short enough, it will use that area to hold the string instead of dynamically allocating a buffer

Also, Herb Sutter's "More Exceptional C++" has an appendix (Appendix A: "Optimizations that aren't (in a Multithreaded World)") that discusses why copy on write refcounted implementations often have performance problems in multithreaded applications due to synchronization issues. That article is also available online (but I'm not sure if it's exactly the same as what's in the book):

Both those chapters would be worthwhile reading.

Could someone point me to an article, or write some tips right here about some c++ programming habits that are generally valid (no real drawbacks) and improves performance? I do not mean programming patterns and algorithm complexity - I need small things like how you define your functions, things to do/to avoid in loops, what to allocate on the stack, what on the heap, and so on.

It's not about making a particular software faster, also it's not about how to create a clean software design, but rather programming habits that - if you always apply them, you will make your code rather a little bit faster than a little bit slower.

Thanks :)

I took the habit to prefer writing ++i rather than i++ not that it brings any performance boost when i is an int but things are different when i is an iterator which might have a complex implementation.

Then let's say you come from the C programming language, lose your habit to declare all your variables at the beginning on the function: declare your variables when they are needed in the function flow since the function might contain early return statements before some variables that were initialized at the beginning are effectively used.

Apart from that, another resource is C++ Coding Standards: 101 Rules, Guidelines, and Best Practices by Herb Sutter (him again) and Alexei Alexandrescu.

There is also a more recent edition of Scott Meyers' Effective C++: Effective C++: 55 specific ways to improve your programs and designs.

Finally, I would like to mention Tony Albrecht's Pitfalls of Object Oriented Programming presentation: not that it contains rules of thumb you can follow blindly but it's a very interesting read.

A number of the tips in Effective C++, More Effective C++, Effective STL and C++ Coding Standards are along this line.

A simple example of such a tip: use preincrement (++i) rather than postincrement (i++) when possible. This is especially important with iterators, as postincrement involves copying the iterator. You optimizer may be able to undo this, but it isn't any extra work to write preincrement instead, so why take the risk?

I have a Phone interview coming up next with with a company which works in financial software industry. The interview is mainly going to be in C++ and problem solving and logic. Please tell me the method of preparation for this interview. I have started skimming through Thinking in C++ and brushing up the concepts. Is there any other way I can prepare?? Please help.


Thank you all everyone for the advice. I just want to add that I am currently fresh out of grad school and have no previous experience. So Can you suggest some type of questions that will be asked to new grads??

Read (or skim, depending on how much time you have to prepare) "Large-Scale C++ Software Design" by John Lakos. Chances are, you will need it.

Make sure you know your basic data structures and algorithms. You're more likely to be asked about that stuff than something higher up the food chain. Those are usually saved for the in-person interview.

Put another way: be solid with the fundamentals and solid with your C++ syntax. Also, knowledge of common libraries like STL and Boost couldn't hurt...but be sure you know what those libraries give you! In the end phone screens are there to cull out people who can't do the basics. Prove you can and you should move on to the next step. Good luck!

Here's some links of interview questions to check out:

Now, for completion's sake, some books:

I consider myself an experienced Java developer and am planning to get started with learning C++.

If you had same experience, i.e learn C++ after Java, I would like to hear your thoughts on what is the best approach at doing this.

[Update] "the best approach" was not well quantified. What I am looking for is to leverage my existing java knowledge and programming experience so that I can quickly ramp up on C++.

K&R and Stroustrup are classics, and eventually you should get them, but I don't think they are good introduction for C++ beginners. Thinking in modern C++ is thinking in classes, templates, exceptions, and streams, none of which available in C language.

I would recommend a college-level textbook on C++ like Deitel and Deitel. alt text

After playing around, you should focus on learning to write a class that behaves like a built-in class. That means providing a copy constructor, operator=, operator==, operator<<, etc.. Along the way you'll meet various concepts embedded in the language of C++. I would agree with others on Effective C++ is a must read once you are comfortable with the basics.

Others have already specified the required books. I would like to add just couple of points to be noted: ( as background is java)

  • C++ doesnot provide you the Garbage collection ( as in Java). Hence, you must be very perticular about memory leaks. Always use delete the memory allocated on heap using new. Try to remember the Free-Store management in FAQ while writing the C++ applications.
  • Most often in C++ you may have to work with pointers ( missing in Java). Learn pointers ( books suggested by @Charlie Martin) effectively and use them.
  • One you are familiar with C++, learn the basics of STL and use effectively. ( Book By Josuttis and Scott Meyers)

Good luck.

I've taught C++ to Java people, even though I learned them the other direction.

Are you comfortable with C? If not, read Kernighan and Ritchie. Many many peculiarities of C++ are explained by the desire for C++ to be a "Better C" with C's basic expression syntax.

You should get Stroustrup.

I think well of Thinking in C++ by Bruce Eckels.

I've used The C++ FAQ Book, by Cline, Lomow, and Girou; I refer to it pretty often. Marshall Cline has C++ FAQ content on his site, too.


You might also look at C++ for Java Programmers. I don't know the book but it looks decent.

I am learning templates. Which book is worth buying for doing template programming?

I already have The C++ Programming Language and Effective C++.

"C++ Templates: The Complete Guide (Vandevoorde & Josuttis)" is excellent for the theory. Then you can learn even more about actual templating practice by looking at how templates are used in the Boost library.

Those two books are pretty good in my opinion and they helped me a lot


The first one explains how templates work. The second book is more about how to use them. I recommend you to read the first book before starting with Modern C++ Design because that's heavy stuff.

Maybe a bit mind-boggling if you are just learning, but after the books you mention, you may want to read Andrei Alexandrescu's Modern C++ Design, if only to learn what can be accomplished through templates. Besides, it discusses many advanced aspects of templates wonderfully.

C++ Templates: The Complete Guide is your best bet. You could also learn about the Standard Library which heavily uses templates.

Effective STL by Scott Meyers

There is a hidden treasure in C++ templates that very few people are aware of: C++ Common Knowledge: Essential Intermediate Programming.

The last 15 chapters of that book both teaches better and complements C++ Template Metaprogramming in some respects. I strongly recommend anyone who is to learn templates to read this book foremost.

Both Modern C++ design and C++ Template Metaprogramming are very good (and quite advanced) books on the subject. I have a strong personal preference for the first.

The following code is supposed to find the key 3.0in a std::map which exists. But due to floating point precision it won't be found.

map<double, double> mymap;
mymap[3.0] = 1.0;

double t = 0.0;
for(int i = 0; i < 31; i++)
  t += 0.1;
  bool contains = (mymap.count(t) > 0);

In the above example, contains will always be false. My current workaround is just multiply t by 0.1 instead of adding 0.1, like this:

for(int i = 0; i < 31; i++)
  t = 0.1 * i;
  bool contains = (mymap.count(t) > 0);

Now the question:

Is there a way to introduce a fuzzyCompare to the std::map if I use double keys? The common solution for floating point number comparison is usually something like a-b < epsilon. But I don't see a straightforward way to do this with std::map. Do I really have to encapsulate the double type in a class and overwrite operator<(...) to implement this functionality?

You could implement own compare function.

#include <functional>

class own_double_less : public std::binary_function<double,double,bool>
  own_double_less( double arg_ = 1e-7 ) : epsilon(arg_) {}
  bool operator()( const double &left, const double &right  ) const
    // you can choose other way to make decision
    // (The original version is: return left < right;) 
    return (abs(left - right) > epsilon) && (left < right);
  double epsilon;
// your map:
map<double,double,own_double_less> mymap;

Updated: see Item 40 in Effective STL! Updated based on suggestions.

I'm trying to find a least-resistance path from C# to C++, and while I feel I handle C# pretty well after two solid years, I'm still not sure I've gotten the "groove" of C++, despite numerous attempts.

Are there any particular books or websites that might be suitable for this transition?

About two years ago, I made the switch from C# to C++ (after 10 years of writing java). The most useful book for me was Bruce Eckel's Thinking in C++ [AMZN]. You can also read the book online at Eckel's website. It's a well-written book--the kind you can read in bed--that's also useful as a keyboard-side reference. It assumes a significant level of comfort with OO and general programming concepts.

Stroustrup [AMZN] is invaluable as a reference, but basically impenetrable unless you're trying to answer a very specific question--and even then, it's a struggle. I haven't cracked my K&R [AMZN] in a few years. I don't think it's got much value as a C++ reference. Myers' Effective C++ [AMZN] (and, once you get there, Effective STL [AMZN]) are fantastic books. They're very specific, though (e.g., "36. Design functor classes for pass-by-value"), and hence not as useful as Eckel for making the transition.

My experience writing C++ after many years writing managed languages has been great. C++ is a hundred times more expressive than C#, and extremely satisfying to write--where it's warranted. On the other hand, on the rare occasions when I still get to write C#, I'm always amazed by how quickly and succinctly I can get things done.

Anyway, Eckel's Effective C++ can help you make the transition. There's a second volume that's good, but not as good. Stick with the original.

Good luck!

You should read one of the other books posted, but then also The Design & Evolution of C++. It helps you to get inside the head of what the language is trying to do.

This code doesn't behave how I expect it to.

using namespace std;

class Class
        cout<<"default constructor called";

        cout<<"destrutor called";

int main()
    Class object();

I expected the output 'default constructor called', but I did not see anything as the output. What is the problem?

Nope. Your line Class object(); Declared a function. What you want to write is Class object;

Try it out.

You may also be interested in the most vexing parse (as others have noted). A great example is in Effective STL Item 6 on page 33. (In 12th printing, September 2009.) Specifically the example at the top of page 35 is what you did, and it explains why the parser handles it as a function declaration.

I would like to write a container class in a style which fits very neatly into STL. It should look and behave as if it where a standard STL container.

Is there a manual, report, Q&A, etc., out there that describes how to write code with these set of features? Such a text should compromise design principles of the STL, pitfalls, coding conventions, and the like.

PS: This question has been partly inspired by that one: C++ vector with dynamic item size although that idea is not about template classes.

I recommend reading Herb Sutter's "Unstrung". It's an in-depth look at std::string, covering what went right and what could've been done better. I highly value his opinion on C++ programming matters. It's a long read, but I guarantee you'll learn a few useful things about writing classes in the style of the C++ standard library (and about writing classes in general).

You could also take a look at Scott Meyers' Effective STL. That book will give you a good overview of the expectations levied on the users of standard library containers. Having that insight will help you write better container classes yourself.

This question is a lot like Good book for learning the C++ standard template library? but aimed at the cash-strapped student type. I remember searching for some reference material about the STL a while back, but I couldn't find any good links.

Are there any worthwile free tutorials / references / best-practises available?

This book helped me a lot understanding the "STL way":

Generic Programming and the STL: Using and Extending the C++ Standard Template Library

And it is also a really great reference once you learned how to use the STL.

STL Tutorial and Reference Guide: C++ Programming with the Standard Template Library is a good book, but personally when developing and I need to know anything about the STL I keep the libstdc++ API documentation open next to me, but this won't teach you anything about generic programming though.

I suggest "Effective STL" by Scott Meyers.

Also here is free online STL guide.

Good luck!

The C++ Standard Library: A Tutorial and Reference is an excellent book for both learning and reference. Perhaps you can barrow it from a friend or library.

I've got about 2/3 years C++ experience but I've spent most of my career doing Java. I'm about to go for an interview for a C++ programming role and I've been thinking about the best way to brush up my C++ to make sure I don't get caught out by any awkward questions. What would you recommend?

Specifically, I have a class which currently uses a vector and push_back. There is an element inside the vector I want to keep track of. Pushing back on the vector may invalidate the iterator, so I keep its index around. It's cheap to find the iterator again using the index. I can't reserve the vector as I don't know how many items will be inserted.

I've considered making the data structure a template parameter, and perhaps list may be used instead. In that case, finding an iterator from the index is not a trivial operation. Since pushing back on a list doesn't invalidate iterators to existing elements, I could just store this iterator instead.

But how can I code a generic class which handles both cases easily?

If I can find out whether push_back will invalidate the iterator, I could store the iterator and update it after each push_back by storing the distance from the beginning before the operation.

You should probably try to avoid this flexibility. Quote from Item 2 "Beware the illusion of container-independent code" from Effective STL by Scott Meyers:

Face the truth: it's not worth it. The different containers are different, and they have strengths and weaknesses that vary in significant ways. They're not designed to be interchangeable, and there's littel you can do to paper that over. If you try, you're merely tempting fate, and fate doesn't like to be tempted.

If you really, positively, definitely have to maintain valid iterators, use std::list. If you also need to have random access, try Boost.MultiIndex (although you'll lose contiguous memory access).

If you look at the standard container adapators (std::stack, std::queue) you see that they support the intersection of the adaptable containers interfaces, not their union.

The following have been proposed for an upcoming C++ project.

  • C++ Coding Standards, by Sutter and Alexandrescu
  • JSF Air Vehicle C++ coding standards
  • The Elements of C++ Style
  • Effective C++ 3rd Edition, by Scott Meyers

Are there other choices? Or is the list above what be should used on a C++ project?

Some related links

I've written a coding standard for a major British company and was very conscious of putting reasons why I selected certain things rather than just make it a bunch of "Thou shalt" pronouncements. (-:

As a quick way out, I'd suggest mandating:

  • Scott Meyers's Effective C++ 3rd Edition (Amazon link) - if you can find a copy of the 1st edition of this book then buy it for the overview of OO design which was removed from later editions. )-:
  • Scott Meyer's book Effective STL (Amazon link) - you must use STL to use C++ efficiently.
  • Steve McConnell's book Code Complete 2 (Amazon link) - not C++ specific but full of great insights.

C++ Coding Standards: 101 Rules, Guidelines, and Best Practices (C++ In-Depth Series) by Herb Sutter and, Andrei Alexandrescu.

Every IDE I've tried fails to provide code-completion when something template-related is used. For example,

boost::shared_ptr<Object> ptr;
ptr->[cursor is here]

Is there IDE that can provide code completion in this case?


As an aside, I'd highly recommend Scott Meyers's excellent "Effective STL" book.

Item 49 "Learn to decipher STL-related compiler diagnostics" is worth the price of admission alone! The info therein is also applicable to decoding complex template related diagnostics beyond STL, e.g. for Boost.

Have fun.

BTW +1 for an interesting question.


I have spent the last several years fighting tooth and nail to avoid working with C++ so I'm probably one of a very small number of people who likes systems programming and template meta programming but has absolutely no experience when it comes to the STL and very little C++ template experience.

  • Does anyone know of a good document for getting started using STL?

I'd prefer PDF or something else I can kill trees with and I'm looking for something more along the lines of a reference than a tutorial (although an 80/20 split would be nice there).

I ended up using the docs from here, pringing them out via a PDF driver and tacking them together with this idea. Now I'm off to print them off 2-up double sided (190 pages even so, but I have >1k pages in my quota and only 4 months till graduation).

In general, it is best to use the documentation that comes with your C++ toolchain. For general-purpose docs, I like the GNU libstdc++ documentation.

If you're looking for a proper reference, then, truly, nothing can beat "ISO/IEC 14882:2003 - Programming Language C++" - after all, it's the primary source. I'm not aware of any legal way to get the PDF for that for free. You can buy the PDF from ISO, but they ask ~$300 for that, way too much in my opinion. A cheaper option is to go to one of the national standard bodies that make ISO - they republish those standards under their own name (but otherwise unchanged), and usually the prices are more sane. The cheapest paper version I'm aware of is published by British Standards Institute - available on Amazon for $85. The cheapest download PDF seems to be $40 from the shop of the Australian member organization.

And once you are done reading all the references suggested here, be sure to take a look at "Effective STL" by Scott Meyers.

If you want dead trees, maybe you'd be better off with a proper book? I found this one indispensable: The C++ Standard Library: A Tutorial and Reference by Nicolai M. Josuttis

I'm in high school and taking a class where basically we design our own course and choose what we learn. I've chosen to learn about C++ and game programming.

I'd like to learn as much about using C++ with OpenGL or DirectX or some other API as I can.

After I finish learning C++ where should I go? Can you recommend a book on game programming?

I too have once thought I knew most of C++... Then I read "Effective C++","Effective STL" , "C++ Gotchas" and "Modern C++ Design", and I realized just how wrong I was.

If you are looking to continue with gaming, C++ is a darn good place to start. You could also check out C# as it is used by Microsoft in XNA (XBox), Second Life, and by Unity on smart phones.

While I would not disagree with anybody about the math and reading you need to do, I think it is better to just roll up your sleeves and program. Read other people's code and then read so that you can understand why they are doing what they are doing.

If you think you know C++ well, the next step is to learn how to use it to make better software. For that, I would start with reading Effective C++.

If you really have a handle on C++ then perhaps this StackOverflow thread will answer your question about game books.

Personally, even if your goal is game programming, I would branch out from that to get a solid grounding as a developer.

Perhaps you should do a little web programming to get a feel for what that is all about. Maybe something like Ruby on Rails.

Alternatively, you could try to write a simple compiler or even an operating system to get a feel for what goes on under the hood and to learn that these too are just programs written by mortals.

Instead of writing your own, you could also get involved in an Open Source project. If I had the time, I would be all over spending time reading the code of Haiku and finding somewhere to contribute. Here is a list of open source game projects that you could consider joining as well.

Your chances of getting a decent job probably go up quite a bit if you know Java or .NET so those are also options. If you decide on .NET, I recommend checking out Mono.

I've discovered that std::strings are very slow compared to old-fashioned null-terminated strings, so much slow that they significantly slow down my overall program by a factor of 2.

I expected STL to be slower, I didn't realise it was going to be this much slower.

I'm using Visual Studio 2008, release mode. It shows assignment of a string to be 100-1000 times slower than char* assignment (it's very difficult to test the run-time of a char* assignment). I know it's not a fair comparison, a pointer assignment versus string copy, but my program has lots of string assignments and I'm not sure I could use the "const reference" trick in all places. With a reference counting implementation my program would have been fine, but these implementations don't seem to exist anymore.

My real question is: why don't people use reference counting implementations anymore, and does this mean we all need to be much more careful about avoiding common performance pitfalls of std::string?

My full code is below.

#include <string>
#include <iostream>
#include <time.h>

using std::cout;

void stop()

int main(int argc, char* argv[])
    #define LIMIT 100000000
    clock_t start;
    std::string foo1 = "Hello there buddy";
    std::string foo2 = "Hello there buddy, yeah you too";
    std::string f;
    start = clock();
    for (int i=0; i < LIMIT; i++) {
        f = foo1;
        foo1 = foo2;
        foo2 = f;
    double stl = double(clock() - start) / CLOCKS\_PER\_SEC;

    start = clock();
    for (int i=0; i < LIMIT; i++) {
    double emptyLoop = double(clock() - start) / CLOCKS_PER_SEC;

    char* goo1 = "Hello there buddy";
    char* goo2 = "Hello there buddy, yeah you too";
    char *g;
    start = clock();
    for (int i=0; i < LIMIT; i++) {
        g = goo1;
        goo1 = goo2;
        goo2 = g;
    double charLoop = double(clock() - start) / CLOCKS_PER_SEC;
    cout << "Empty loop = " << emptyLoop << "\n";
    cout << "char* loop = " << charLoop << "\n";
    cout << "std::string = " << stl << "\n";
    cout << "slowdown = " << (stl - emptyLoop) / (charLoop - emptyLoop) << "\n";
    std::string wait;
    std::cin >> wait;
    return 0;

Good performance isn't always easy with STL, but generally, it is designed to give you the power. I found Scott Meyers' "Effective STL" an eye-opener for understanding how to deal with the STL efficiently. Read!

As others said, you are probably running into frequent deep copies of the string, and compare that to a pointer assignment / reference counting implementation.

Generally, any class designed towards your specific needs, will beat a generic class that's designed for the general case. But learn to use the generic class well, and learn to ride the 80:20 rules, and you will be much more efficient than someone rolling everything on their own.

One specific drawback of std::string is that it doesn't give performance guarantees, which makes sense. As Tim Cooper mentioned, STL does not say whether a string assignment creates a deep copy. That's good for a generic class, because reference counting can become a real killer in highly concurrent applications, even though it's usually the best way for a single threaded app.

What are the common misuse of using STL containers with iterators?

Forgetting that iterators are quite often invalidated if you change the container by inserting or erasing container members.

For many great tips on using STL I highly recommend Scott Meyers's book "Effective STL" (sanitised Amazon link)

I recently forced myself to study C++ and I just finished reading the book C++: The Complete Reference, by Herbert Schildt. I liked the book and think I got more or less the big picture. I noticed though that when I try to check with other people the things I code using the material I learned, they are usually considered non-idiomatic and superseded by an STL way to do it that is safer and easier (well, the book doesn't cover STL and Boost libraries).

So I'd like to ask: what are good sources to learn the patterns of a good C++ program? Where can I learn basic patterns from the "C++ way" to do things and not just repeating C patterns in C++?

I'd be particularly interested in sources that included STL and Boost stuff.

I'd (also) recommend:

  • Effective C++, Effective STL by Steve Myers. They are easy to digest, yet very valuable - sometimes even illuminating.
  • Code Complete (The 1993 edition is available cheaply and not that much different). It's lengthy, but it walks across the entire field from what it means to be a programmer to how a for loop should look. (It would be better if it was shorter - the way it is it covers so much ground it's hard to place it). I hold it dear because it illustrate two points very well:
    • code is compromise
    • There are know facts, (but we still manage to get by by gut feel)
  • C++ FAQ Lite / C++ FAQ.
  • I'd throw in Facts and Fallacies by Robert Glass - it doesn't fit your request very well, but go read it.

It's natural that you are unhappy with other people's code. That's typical for programming - heck, even my own code of five years ago was written by a total n00b. That might be more articulated for C++, since it caters for different styles, and often puts freedom ("you can") over guildelines ("that's the way").

Still, mulling over existing code - yours or others - and considering how it can be improved. Also, figuring out why it is the way it is sometimes helps.

(I remember a few TheDailyWTF's where everyone would chime in how stupid and unreasonable this is - yet somewhere, buried among the me too's, was someone with domain experience explaining convincingly under what circumstances this was better than the obvious solution).

You might wnat to check out The Definitive C++ Book Guide and List

For your purposes I would especially recommend:

They are not in particular order, also you might want to read and code something in between them.

(Note: As noted by @John Dibling the Boost book might be a bit out of date, I do not have experience with that one myself)

I'm fairly new to the STL, so I was wondering whether there are any dynamically sortable containers? At the moment my current thinking is to use a vector in conjunction with the various sort algorithms, but I'm not sure whether there's a more appropriate selection given the (presumably) linear complexity of inserting entries into a sorted vector.

To clarify "dynamically", I am looking for a container that I can modify the sorting order at runtime - e.g. sort it in an ascending order, then later re-sort in a descending order.

STL maps and sets are both sorted containers.

I second Doug T's book recommendation - the Josuttis STL book is the best I've ever seen as both a learning and reference book.

Effective STL is also an excellent book for learning the inner details of STL and what you should and shouldn't do.

what is the most advanced c or c++ book you ever read? i am asking this because i already read lots and lots of books on c and c++ on a lot of topics including (object oriented programming-data structures and algorithms-network programming-parallel programming (MPI-PThreads-OpenMP-Cilk-Cuda)-boost library....). So whats next. I still want to advance.. especially in c.

Hey nobody mentioned about Bruce Eckel's Thinking in C++ Volume 1 And Volume 2. When I read it as the first book it went straight way above my head. However as now I have good experience and have read books like Effective/Exceptional C++ so Eckel's book is now an ordinary stuff. However no doubt its a very popular book (4.5 stars on Amazon - 84 customer reviews).

Large Scale C++ Design by John Lakos.

Practical advice on managing the complexity of compiling/linking and executing large C++ programs. Talks a lot about decoupling and how to avoid the many kinds of dependencies that arise in C++.

(This is something most C#/Java developers, and sadly some C++-devs too, rarely understand. IMO, it's a pain they need to. I wish we had modules in C++ already.)

My favourite "difficult" C++ book is this Template Metaprogramming one: C++ Template Metaprogramming: Concepts, Tools, and Techniques from Boost and Beyond.

You really want to test your mental limits? Then try these:

Alexandrescu: Modern C++ Design

Abrahams&Gurtovoy: C++ Template Metaprogramming

These books look deceiptively thin, but they stretch the limits of template programming, your C++ compiler, and your brain.

It seems to me there aren't half as many books about C programming as there are about C++. The language just isn't that complex.

One interesting read might be P. J. Plauger The Standard C Library. It is supposed to contain some masterful code. It's on my to-read list.

I am not sure if you would consider these advanced, but I would surely put them in the category of must have references:

The C++ Programming Language Special Edition (3rd) by Bjarne Stroustrup

The C++ Standard Library: A Tutorial and Reference by Nicolai M. Josuttis

The other books I would recommend have already been listed by others.

I haven't done C++ for about three years and looking to get back and ready. What is the best way? any open source projects that I might want to look at to recall all the details and be ready for interviews? I started reading (again) C++ Primer 5th edition but was wondering whether there's more efficient way since I did program in C++ for few years before.

Just wanted to add: Does anyone know about open source projects related to finance? (e.g. servers, fix, etc)

I'd start in on a real project.

If nothing else, download an open source C++ project that's in the same realm as the jobs you want to target, and start modifying. Practice helps more than anything for being comfortable.

If you're going to focus on reading, or in addition to practice, I'd actually focus on reading books that work more on using C++ well, not necessarily learning C++. Effective C++, More Effective C++, and Effective STL are great for this - you'll learn new things while refreshing your old knowledge. You can always use the primer book as a reference to study things you've forgotten as you read about them elsewhere.

I would like to use different instances of an STL custom allocator class to manage different memory spaces, and then be able to specify an allocator instance to an STL container such that each container only draws from its assigned memory space. But I don't see how I can do that. I see how I can pass an allocator type into the template parameters of an STL container, but I want something akin to passing an allocator instance into the constructor of an STL container. Is there a way to do this in STL?

Unfortunately STL allocators cannot have state (or at least have to be very careful how that state is used) - each instance of a particular allocator type must be equivalent for STL containers to work effectively with them. I don't recall the details right now, but I know that Scott Meyers discusses this problem at length in "Effective STL", Item 10: Be aware of allocator conventions and restrictions.

However, you can have templated allocators that are very similar with the differences between the allocators being encapsulated in the allocator type and use different 'instantiations' of the allocator template (each template 'instantiation' is a different type). Again, my recollection is that Meyers discusses this pretty clearly.

For example see this paragraph from an article by Anthony Aue, "Improving Performance with Custom Pool Allocators for STL":

A potentially more serious caveat is that, since the allocator uses nonstatic data, it's not technically Standard compliant because the Standard requires that allocators of the same type be equivalent. See Effective STL (Item 10) for a thorough explanation of the issue. This amounts to requiring that an allocator for a given type be able to deallocate memory allocated by any other instance of an allocator for that type. For many uses of standard containers, this requirement is unnecessary (some might say Draconian). However, there are two cases where this requirement is absolutely necessary: list::splice and swap(). The case of swap() is especially serious because it is needed in order to implement certain operations on containers in an exception-safe manner (see Exceptional C++, Item 12). Technically, swap could be (and in some cases, is) implemented in the face of allocators that don't compare equally—items could be copied or the allocators could be swapped along with the data—but this is not always the case. For this reason, if you're using swap() or list::splice, you should make sure to use HoldingPolicySingleton; otherwise, you're bound to run into some really nasty behavior.

See also Stephan T. Lavavej's discussion in this newsgroup thread.

I'll update later tonight if someone else doesn't give the details in the meantime.

This is a follow-up to my question from yesterday. I have Scott Meyers' warning about write-only code on my mind. I like the idea in principle of using standard algorithms to access the keys or values of a std::map, but the syntax required is a little baroque IMHO. Let's say I want to dump all the keys of a map to a vector. Given following declarations,

typedef std::map<int, int> MyMap;
MyMap m;
std::vector<int> v;

which code is more maintainable (i.e., potentially less confusing)?

Option #1:

               std::tr1::bind(&MyMap::value_type::first, _1));

Option #2:

for (MyMap::iterator i = m.begin(); i != m.end(); ++i)

Option 1 is more standard library-ish but I have to mentally decompose it to understand what's going on. Option 2 seems easier to read at the expense of a possible small runtime penalty. I'm not hurting for CPU time so I'm leaning toward option 2. Does you guys agree? Is there a third option I should consider?

P.S. Over the course of writing this question I concluded that the best way (for my project) to read the keys of a std::map is to store them off in a side container and iterate over that. The maintainability question still stands though.

Go with option #1, see Scott Meyers, Effective STL Item #43, page 181.

Possible Duplicate:
Where is the c++11 standard

I am looking to buy/download a few things. First I want both a digital copy and paper copy of the official c++11 reference.

Also I would like a book that is a summation of the reference that focuses on things like commonly used c/c++ functions and the STL, something more accessible than the official reference itself. Also would be great for both paper and digital versions. I don't need a beginners book, just a reference. This one is probably going to be opinionated so feel free to say which one you like.

There are plenty of great books on the STL, there is a giant list available on Amazon. Some of the most popular ones for STL are

For C++ 11, there are plenty of locations for references, such as

Does anybody know of an STL implementation that allows for dynamic allocators to be passed in to an instance of a container before use.

The scenario is that we have a general memory allocator that manages a number of pools of memory and for each instance of say stl::vector we want to allocate each instance from a different pool of memory.

The problem with the standard STL implementations is that you can only define the memory pool on a type basis ie all vector's of type int would allocate from the same pool.

I've already swapped out our default stl::allocator for one that has a state ie the pool we want to allocate this instance from but this doesn't work well for say stl::list where it allocates things in the default ctor.

For reasons related to our library we also don't have a valid pool in the ctor for all objects and so we want to call a 'set memory pool' function before users can use the stl container.

Has anybody come across an implementation that supports this kind of thing?

The problem with the standard STL implementations is that you can only define the memory pool on a type basis ie all vector's of type int would allocate from the same pool.

This is not exactly true. You can have different vectors holding int elements each having a different allocator type.

However, regarding the question --

Does anybody know of an STL implementation that allows for dynamic allocators to be passed in to an instance of a container before use.

-- it is simply not supported by the C++ Standard Library (STL), therefore, while it may be that there are implementations where per-object allocators work, it is not portable.

For a detailed analysis of why and how to use custom allocators see Scott Meyers's book Effective STL, specifically Item 11: Understand the legitimate use of custom allocators.

I am preparing for a programming competition in witch we solve programming problems in c++.

Looking at the former year solutions, they seem quite easy (not more than ~30 lines of code). I realised that they are widely using the STL for easy manipulating - vectors, sets, maps, lists and also the algorithms available in STL.

Any site for beginners like me who want to learn the features of STL and its use in solving problems ?

Thank you in advance.

Two books come to mind: Josuttis's The C++ Standard Library (and his page for it), and Meyers's Effective STL

I haven't touch C++ in more then 8 years. I recently had to do fix some C++ code, and although I still can code, I feel like I no more belongs to the camp of C++ programmers. I don't know any libraries, didn't pay attention to the new language features / improvements / best practices.

Qt Creator and Qt seems like a nice toolset for what I need now, since I'm interested mostly in cross platform development.

What would be good resources for someone like me to quickly re-learn C++ and best practices in shortest period of time?

I have been doing mostly java and common lisp in the meantime, with a short strides to C, flex, Scala and Haskell.

Read :

Those are references books on C++ that resume all the modern effective pratices, philosophies and knowledge on C++ (without going into Meta-Programmation stuff).

Then if you want to go farther, read :

About libraries: first learn about the STL and learn to use Boost as a "standard" STL extension.

I'm currently in the process of learning C++, and because I'm still learning, I keep making mistakes.
With a language as permissive as C++, it often takes a long time to figure out exactly what's wrong -- because the compiler lets me get away with a lot. I realize that this flexibility is one of C++'s major strengths, but it makes it difficult to learn the basic language.
Is there some tool I can use to analyze my code and make suggestions based on best practices or just sensible coding? Preferably as an Eclipse plugin or linux application.

I think you'd better have some lectures about good practices and why they are good. That should help you more than a code analysis tool (in the beginning at least).

I suggest you read the series of Effective C++ and **Effective STL books, at least. See alsot The Definitive C++ Book Guide and List

There are countless articles and blogs discussing C++'s most vexing parse, but I can't seem to find any with a more substantial reference than "the C++ literature."

Where did this term come from?

Scott Meyers book Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library of 2001 might be first published use.

I am very interested in c++ and want to master this language. I have read a lot of books about c++. I want to read some library source code to improve my skill, but when I read the boost library source code, I find it is very difficulty.
Can anyone give me some advice about how to read boost source code and before I can understand it what kind of books about c++ should I read?

If you're starting out in C++, the boost source code is probably not the best place. It's where the wizards hang out and they deal in template magic. I think a better starting point are Scott Myers and Herb Sutters books (in that order).

Some versions of Scott's book can be a bit out dated but they are still strong in the fundamentals. Herb's books are worth reading many many times and are an invaluable tool. Once you've gotten through both of those authors, then would be a good time to tackle the boost source code.

I cannot find this question on stackoverflow. But I am wondering how people use STL (No fancy boost)... just an ol' fashion STL. Tricks/tips/mostly used cases acquired over many, many years... and perhaps gotchas...

Let's share it...

One tip per answer...with code example --

Edit is it such a bad question as it resulting in downvotes?

There are no most used STL algorithms, predicates or iterators. It's like asking what is the most used operator in C++ language. What do you use more often, operator+ or operator-? Do you prefer if to while? Or maybe to throw?

Everything is used when it has to be used.

PS: I suggest you to read Effective STL by Scott Meyers before asking such questions.

I want to refresh my STL knowledge before interview. Could anyone recommend good short and freely downloadable STL tutorial? Thank you.

EDIT: Preferably in PDF.



These are two very good sites for STL reference. For interview I would suggest to refer good book The C++ Standard Library: A Tutorial and Reference by Nicolai M. Josuttis .

Its not a book and for free download, but Scott Myers Effective STL in combination with a good STL reference is in my opinion invaluable for an interview preparation.

My question is mostly about STL than the rest of the C++ that can be compared (I guess) to be as much fast as C a long as classes aren't used at every corner.

STL is standard for games and in engines like OGRE3D, but I was wondering that if STL's features are nice to use, the problem is while I don't really know how they work, I should know first what features can cause serious hogs before using them.

I'm very excited to begin that game programming school, and apparently there is no way I am going to not use those advanced features.

I recommend Effective STL by Scott Myers. The biggest performance hog of STL, is the lack of understanding of it. Please learn it well!

Also see Optimizing software in C++ by Agner Fog for C++ specific performance related topics.

This book covers what issues you face when using C++ in games.

The following code represents a container based on std::vector

template <typename Item>
struct TList
    typedef std::vector <Item> Type;

template <typename Item>
class List
            typename TList <Item>::Type items;

int main()
  List <Object> list;

Is it possible to templatize std::vector and create a general container, something like that?

template <typename Item, typename stl_container>
struct TList
    typedef stl_container<Item>;

where stl_container represents std::vector, std::list, std::set...? I would like to choose the type of container at the time of the creation.

List <Object, std::vector> list; //vector of objects, not a real code
List <Object, std::vector> list; //list of objects, not a real code

Thanks for your answers...

Updated question:

I tried the following code but there are errors:

#include <vector>
template <typename Item, typename Container>
struct TList
   typedef typename Container <Item>::type type; //Error C2059: syntax error : '<', Error C2238: unexpected token(s) preceding ';

template <typename T>
struct vector_container
  typedef std::vector<T> type;

int _tmain(int argc, _TCHAR* argv[])
TList <int, vector_container> v;
TList <int, map_container> m;

Is it possible to templatize std::vector and create a general container, something like that?

No. You would have to templatize the function or object using the container -- you couldn't templatize the container itself.

For example. consider a typical std::find:

template<class InputIterator, class T>
InputIterator find ( InputIterator first, InputIterator last, const T& value )
    for ( ;first!=last; first++) if ( *first==value ) break;
    return first;

This works for any container, but doesn't need a tempalte with the container at all.

Also, given that it looks what you're trying to do is make container independent code, you might want to buy or borrow yourself a copy of Scott Meyers' Effective STL and read Item 2: Beware the illusion of container-independent code.

This is a best practices question. I am making an array

type * x = malloc(size*sizeof(type));

AFAIK sizeof gives a return value of size_t. Does that mean that I should use a size_t to declare, or pass around size? Also when indexing the array should I also use a size_t for the index variable? What is the best practice for these these? This is not something that they taught in school, and now that I'm getting into serious c++ I want to know.

Also if anyone has references of where I can find best practices for this kind of stuff it would be helpful? Kind of an etiquette for programmers book.

EDIT: The malloc should be cudaHostAlloc, or cudaMalloc, since I am developing a class that stores an array simultaneously on the device and host, and updates both at the same time. So malloc here is just a place holder for what I'll actually be doing.

In reference to your follow-on question:

The best reference I have used for general high-level programming "current good practices" sort of thing is:

Code Complete by Steve McConnell (ISBN 0-7356-1967-0)

I reference it all the time. When my company formalized its coding standards, I wrote them based off of it. It doesn't go into design or architecture as much, but for actually banging out code, the book is appropriately named.

In general, I use whatever minimizes the number of implicit or explicit casts and warning errors. Generally there is a good reason why things are typed the way they are. size_t is a good choice for array index, since it's unsigned and you don't generally want to access myarray[-1], say.

btw since this is C++ you should get out of the habit of using malloc (free) which is part of CRT (C runtime library). Use new (delete), preferably with smart pointers to minimize manual memory handling.

Once you have mastered the basics, a good practices reference (language-specific) is Effective C++ by Scott Meyers. The logical next step is Effective STL.

Those of us who have seen the beauty of STL try to use it as much as possible, and also encourage others to use it wherever we see them using raw pointers and arrays. Scott Meyers have written a whole book on STL, with title Effective STL. Yet what happened to the developers of ifstream that they preferred char* over std::string. I wonder why the first parameter of ifstream::open() is of type const char*, instead of const std::string &. Please have a look at it's signature:

void open(const char * filename, ios_base::openmode mode = ios_base::in );

Why this? Why not this:

void open(const string & filename, ios_base::openmode mode = ios_base::in );

Is this a serious mistake with the design? Or this design is deliberate? What could be the reason? I don't see any reason why they have preferred char* over std::string. Note we could still pass char* to the latter function that takes std::string. That's not a problem!

By the way, I'm aware that ifstream is a typedef, so no comment on my title.:P. It looks short that is why I used it.

The actual class template is :

template<class _Elem,class _Traits> class basic_ifstream;

My copy of the standard disagrees with you. It says both these are overloads:

void open(const char* s, ios_base::openmode mode = ios_base::in);
void open(const string& s, ios_base::openmode mode = ios_base::in);

However, that copy of the standard is a draft of the next version of the standard, C++0x.

The reason for this is that the iostreams library predates std::basic_string, and because the library designers didn't want someone to have to #include <string> and all it's other associated baggage if they didn't want to use it.

I'm wanting to become conversant in the use of the Standard Template Library. If I come across a general reference or beginner's guide published around 1995-97, can I rely on the information in it? How much has STL changed in the last dozen years?

Not a whole lot, if at all. The current standard was published in 1998.

cplusplus.com has a more up-to-date reference, which you can compare for yourself.

I'd recommend also that you get a copy of Scott Meyers' Effective STL.

I've used STL for quite a while now, but mostly to implement algorithms for the sake of it, other than the occasional vector in other code.

Before I start using it more, I wanted to know what the common mistakes people make when using STL are -- in particular, are there any things I should watch for when using STL templates to keep my code safe from memory leaks?

There are a lot of bottlenecks in using STL effectively, if you want to know more I'd suggest the book "Effective STL" by S.Meyers.

I am considering to put one of the following as a reference on my desk (as I am sick and tired to google every time I have a STL question):

I would go with the first - Josuttis' The C++ Standard Lib: Tutorial and Reference for the depth. I like to keep O'Reilly's STL Pocket Reference around for quick lookups.

All of Scott Meyers' books are excellent, including "Effective STL". It's not a handbook or a tutorial, but worth having.

I am trying to delete an element from a deque using a loop and an iterator. I am following online examples but seeing a bug.

I am using g++ (GCC) 4.8.3 20140911 (Red Hat 4.8.3-9).

Here is the code:

#include <iostream>
#include <deque>

using namespace std;

// Display the contents of a queue
void disp_deque(deque<int>& deque) {
  cout << "deque contains: ";
  for (auto itr = deque.begin(); itr!=deque.end(); ++itr)
    cout << *itr << ' ';
  cout << '\n';

int main(int argc, char** argv) {
  deque<int> mydeque;

  // Put 10 integers in the deque.
  for (int i=1; i<=10; i++) mydeque.push_back(i);

  auto it = mydeque.begin(); 
  while (it!=mydeque.end()) {
    cout << "Checking " << *it << ',';
    // Delete even numbered values.
    if ((*it % 2) == 0) {
      cout << "Deleting " << *it << '\n';
    } else ++it;

It is pretty straight forward - create a list of 10 elements and delete the even ones.

Notice the following (fluff excluded):

if ((*it % 2) == 0) {
} else it++;

It is the recommended way to delete using an iterator so that your iterator does not get invalidated as mentioned in the link above.

However, when I run this, I get the following:

$ ./test
deque contains: 1 2 3 4 5 6 7 8 9 10 
Checking 1,Checking 2,Deleting 2
deque contains: 1 3 4 5 6 7 8 9 10 
Checking 3,Checking 4,Deleting 4
deque contains: 1 3 5 6 7 8 9 10 
Checking 5,Checking 6,Deleting 6
deque contains: 1 3 5 7 8 9 10 
Checking 7,Checking 8,Deleting 8
deque contains: 1 3 5 7 9 10 
Checking 10,Deleting 10
deque contains: 1 3 5 7 9 
Checking 10,Deleting 10
deque contains: 1 3 5 7 
Checking 0,Deleting 0
deque contains: 1 3 5 
Checking 0,Deleting 0
deque contains: 1 3 
Checking 0,Deleting 0
deque contains: 1 
Checking 0,Deleting 0
deque contains: 
Checking 0,Deleting 0
Segmentation fault (core dumped)

Looking through it, it seems pretty good up until it deletes 8. In fact, number 9 is skipped altogether and never checked! What I expect should happen is this:

$ ./test
deque contains: 1 2 3 4 5 6 7 8 9 10 
Checking 1,Checking 2,Deleting 2
deque contains: 1 3 4 5 6 7 8 9 10 
Checking 3,Checking 4,Deleting 4
deque contains: 1 3 5 6 7 8 9 10 
Checking 5,Checking 6,Deleting 6
deque contains: 1 3 5 7 8 9 10 
Checking 7,Checking 8,Deleting 8
deque contains: 1 3 5 7 9 10 
Checking 9,Checking 10,Deleting 10
deque contains: 1 3 5 7 9 

In fact, this is exactly what I get when I change the code to this:

if ((*it % 2) == 0) {
} else it++;

So, why does one method work, but the other not? Can anyone explain it?

Even if I create a temporary iterator to delete, I see the exact same problem output:

  while (it!=mydeque.end()) {
    cout << "Checking " << *it << ',';
    auto tmp_it = it++;
    // Delete even numbered values.
    if ((*tmp_it % 2) == 0) {
      cout << "Deleting " << *tmp_it << '\n';
      cout << "IT before delete: " << *it << '\n';
      cout << "IT after delete: " << *it << '\n';

Here I store a copy of it in tmp_it and then increment it. I added some more debug statements and saw some really weird stuff:

deque contains: 1 3 5 6 7 8 9 10 
Checking 5,Checking 6,Deleting 6
IT before delete: 7
IT after delete: 7
deque contains: 1 3 5 7 8 9 10 
Checking 7,Checking 8,Deleting 8
IT before delete: 9
IT after delete: 10
deque contains: 1 3 5 7 9 10 
Checking 10,Deleting 10
IT before delete: 10
IT after delete: 10

However, the deletion of element 8 makes it point to element 10, skipping 9! On previous deletes, it was pointing to the previous element (e.g. when 6 was deleted, it was pointing to 7 before and after the delete).

I looked up the implementation of deque and see under "Iterator Validity" the following (emphasis mine):

Iterator validity If the erasure operation includes the last element in the sequence, the end iterator and the iterators, pointers and references referring to the erased elements are invalidated. If the erasure includes the first element but not the last, only those referring to the erased elements are invalidated. If it happens anywhere else in the deque, all iterators, pointers and references related to the container are invalidated.

So does that mean that in my code, my iterator is being invalidated even though I did a post increment on it before it is deleted? i.e. an iterator other than the one I deleted is being invalidated?

If so, then that it fine, but it seems like a little known bug. It means that common implementations of iterator deletion within a loop are not valid when using deque.

The code you quoted is for associative containers only (set, map etc.).

Scott Meyers's Effective STL Item 9 (aptly named "Choose carefully among erasing options") shows how it's done for sequence containers (vector, deque, string)

for (SeqContainer<int>::iterator it = c.beqin(); it != c.end();) {
    if (predicate(*it)){
        it = c.erase(it); // keep it valid by assigning
    }                     // erase's return value to it
    else ++it;

Here, the erase() return value is exactly what we need: it's a valid iterator pointing to the element following the erased element once the erase has been accomplished.

I got this question when I was reading erase-remove idiom (item 32) from Scott Meyers "Effective STL” book.

vector<int> v; 
v.erase(remove(v.begin(), v.end(), 99), v.end());

remove basically returns the "new logical end” and elements of the original range that start at the "new logical end" of the range and continue until the real end of the range are the elements to be erased from container.

Sounds good. Now, let me ask my question:

In the above example, remove can return v.end() if 99 is not found in the vector v. It is basically passing past-the-end-iterator to erase method.

  1. What happens when past-the-end-iterator is passed to the erase method? Does standard says it a UB?
  2. If it is undefined behavior, then erase-remove idiom example in Scott Meyer’s book should have looked like:

  vector<int> v; 
    vector<int>::iterator newEndIter = remove(v.begin(), v.end(), 99);
    if(newEndIter != v.end() )
     v.erase(newEndIter, v.end();

Any ideas on this?

I have been learning C++ with some books from school that are from the 80's and I'm not really sure if they are strings in C++ or just really long arrays of type char. Can anyone help?

Check out the standard library.

In the STL, you can find the std::string class, as well as a bunch of other useful classes.

The basic documentation can be found here:


The string documentation can be found here:


The beauty of these stl strings is that they delete themselves; so once you declare them, you can just let them go, and they will handle their own memory. That's true of other stl classes as well (Of course, if you declare a vector of pointers, the vector will get deleted, but the memory the pointers point to has to be handled as well; it's not a total panacea, but it works nicely if you keep that limitation in mind).

Finally, I've found that this book is a really good way to learn how to think in STL:

Effective STL

I saw Scott Meyers' "Effective C++" third edition book having a small section on "Template Programming".

Any other book/links containing information on "effective" usage of templates ?

Scott Meyers deals with the Standard Template Library in Effective STL. That may be relevant for you.

I like Modern C++ Design: Generic Programming and Design Patterns Applied. I found it very well written and clear. Contains a few advanced topics.

alt text

A rarely mentioned but solid book is C++ Common Knowledge by Stephen C. Dewhurst. "Among the first users of C++ at Bell Labs", Dewhurst gives the book a somewhat deceptive title because he actually covers quite a bit of advanced material in particular in regards to templates.

Dewhurst's book is organized similarly to Meyers's with 63 "Items" that you can usefully read on their own. On templates you should look over items 45-59 (about 70 pages of reading).

alt text

class MyContainedClass {

class MyClass {
  MyContainedClass * getElement() {
    // ...
    std::list<MyContainedClass>::iterator it = ... // retrieve somehow
    return &(*it);
  // other methods
  std::list<MyContainedClass> m_contained;

Though msdn says std::list should not perform relocations of elements on deletion or insertion, is it a good and common way to return pointer to a list element?

PS: I know that I can use collection of pointers (and will have to delete elements in destructor), collection of shared pointers (which I don't like), etc.

Scott Meyers in his book Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library says it's just not worth trying to encapsulate your containers since none of them are completely replaceable for another.

1. Description of the problem

I am trying to pick the most appropriate (efficient) container to store unique n-dimensional vectors composed of floating numbers. Solving whole problem, the most important steps (related to the question) involve:

  1. Get a new vector from the external program (during the same run, all vectors have the same dimensionality).
  2. Check (ASAP) if a new point is already in this container:
    • if exists - skip a lot of expensive steps and do the other steps;
    • if doesn't - insert into a container (ordering in the container is not important) and do the other steps.

In advance, I don't know how many vectors I will have but the maximum number is prescribed in advance and equal = 100000. Moreover, I always get only one new vector per iteration. Thus at the beginning, most of these new vectors are unique and will be inserted in a container, but later is hard to predict in advance. A lot will depend on the definition of unique vectors and tolerance values.

Thus my goal is to choose the right container for this (type of) situation(s).

2. Choosing a right container

I did a bit of review and from what I found in S. Meyers - Effective STL Item 1: Choose your containers with care

Is lookup speed a critical consideration? If so, you’ll want to look at hashed containers (see Item 25), sorted vectors (see Item 23), and the standard associative containers — probably in that order.

and what I have seen in amazing David Moore's flowchart Choosing a Container it looks that all three suggested options from S. Meyers, Item 1 are worthy broader investigation.

2.1 Complexity (based on cppreference.com)

Let's start from very brief look into theoretical complexity of lookup and insertion procedures for all three considered options separate:

  1. For Vectors:
    • find_if() - linear O(n)
    • push_back() - constant, but causes reallocation if the new size() is greater than the old capacity()
  2. For Sets:
    • insert() - Logarithmic in the size of the container, O(log(size())).
  3. For unordered Sets:
    • insert() - Average case: O(1), worst case O(size())

3. Benchmarking different containers

In all experiments, I modelled situation with randomly generated 3-dimensional vectors filled with real values from the interval [0,1).


Used Compiler: Apple LLVM version 7.0.2 (clang-700.1.81)

Compiled in release mode with optimization level -O3 and without any optimization levels.

3.1 using unsorted vector

First, why unsorted vector? My scenario considerably differs from the one described in S. Meyers - Effective STL Item 23: Consider replacing associative containers with sorted vectors. Therefore I do not see any advantages in this situation to use sorted vectors.

Second, two vectors x and y assumed to be equal if EuclideanDistance2(x,y) < tollerance^2. Taking into account this, my initial (probably prety poor) implementation with vector's is following:

benchmarking part of implementation using vector container:

// create a vector of double arrays (vda)
std::vector<std::array<double, N>> vda;
const double tol = 1e-6;  // set default tolerance
// record start time
auto start = std::chrono::steady_clock::now();
// Generate and insert one hundred thousands new double arrays
for (size_t i = 0; i < 100000; ++i) {
  // Get a new random double array (da)
  std::array<double, N> da = getRandomArray();
  auto pos = std::find_if(vda.begin(), vda.end(),  // range
    [=, &da](const std::array<double, N> &darr) {  // search criterion
    return EuclideanDistance2(darr.begin(), darr.end(), da.begin()) < tol*tol;

  if (pos == vda.end()) {
    vda.push_back(da);  // Insert array
// record finish time
auto end = std::chrono::steady_clock::now();
std::chrono::duration<double> diff = end - start;
std::cout << "Time to generate and insert unique elements into vector: "
          << diff.count() << " s\n";
std::cout << "vector's size = " << vda.size() << std::endl;

here random n-dimensional real vectors (N-dimensional arrays) generated:

// return an array of N uniformly distributed random numbers from 0 to 1
std::array<double, N> getRandomArray() {
  // Engines and distributions retain state, thus defined as static
  static std::default_random_engine e;                    // engine
  static std::uniform_real_distribution<double> d(0, 1);  // distribution
  std::array<double, N> ret;
  for (size_t i = 0; i < N; ++i) {
    ret[i] = d(e);
  return ret;

and squared Euclidean distance is calculated:

// Return Squared Euclidean Distance
template <typename InputIt1, typename InputIt2>
double EuclideanDistance2(InputIt1 beg1, InputIt1 end1, InputIt2 beg2) {
  double val = 0.0;
  while (beg1 != end1) {
    double dist = (*beg1++) - (*beg2++);
    val += dist*dist;
  return val;

3.1.1 Testing vector's performance

In the messy table below I summarise the average execution time of 10 independent runs and the size of the final container depending on different tolerance (eps) values. Smaller tolerance values lead to higher number of unique elements (more insertions), while higher lead to the less number of unique vectors but longer lookups.

| eps | time(s) with -O3 flag/without optimization flags | size |

| 1e-6 | 13.1496 / 111.83 | 100000 |

| 1e-3 | 14.1295 / 114.254 | 99978 |

| 1e-2 | 10.5931 / 90.674 | 82868 |

| 1e-1 | 0.0551718 / 0.462546 | 749 |

From the results, it seems, that the most time-consuming part using vectors is lookup (find_if()).

Edit: Also, it's obvious, that -O3 optimization makes really good job improving vector's performance.

3.2 Using set

Benchmarking part of implementation using set container:

// create a set of double arrays (sda) with a special sorting criterion
std::set<std::array<double, N>, compare_arrays> sda;
// create a vector of double arrays (vda)
std::vector<std::array<double, N>> vda;
// record start time
auto start = std::chrono::steady_clock::now();
// Generate and insert one hundred thousands new double arrays
for (size_t i = 0; i < 100000; ++i) {
  // Get a new random double array (da)
  std::array<double, N> da = getRandomArray();
  // Inserts into the container, if the container doesn't already contain it.
// record finish time
auto end = std::chrono::steady_clock::now();
std::chrono::duration<double> diff = end - start;
std::cout << "Time to generate and insert unique elements into SET: "
          << diff.count() << " s\n";
std::cout << "set size = " << sda.size() << std::endl;

where the sorting criterion is based on flawed (breaks strict weak ordering) answer. At the moment I wanted to look (approximately) what can I expect from different containers and later decide which one is the best.

// return whether the elements in the arr1 are “lexicographically less than”
// the elements in the arr2
struct compare_arrays {
  bool operator() (const std::array<double, N>& arr1,
                   const std::array<double, N>& arr2) const {
    // Lexicographical comparison compares using element-by-element rule
    return std::lexicographical_compare(arr1.begin(), arr1.end(),  // 1st range
                                        arr2.begin(), arr2.end(),  // 2nd range
                                        compare_doubles);   // sorting criteria
  // return true if x < y and not within tolerance distance
  static bool compare_doubles(double x, double y) {
    return (x < y) && !(fabs(x-y) < tolerance);
  static constexpr double tolerance = 1e-6;  // Comparison tolerance

3.2.1 Testing set's performance

In the imaginable table below, I summarise execution time and the size of container depending on different tolerance (eps) values. The same eps values were used, but for the sets the equivalence definition is different.

| eps | time(s) with -O3 flag/without optimization flags | size |

| 1e-6 | 0.041414 / 1.51723 | 100000 |

| 1e-3 | 0.0457692 / 0.136944 | 99988 |

| 1e-2 | 0.0501 / 0.13808 | 90828 |

| 1e-1 | 0.0149597 / 0.0777621 | 2007 |

Performance difference comparing with vector approach is massive. The main concern now is flawed sorting criterion.

Edit: -O3 optimization also makes a good job improving set's performance.

3.3 Using unsorted set

Finally, I was eager to try unordered set, as my expectations after reading a bit of Josuttis, The C++ Standard Library: A Tutorial and Reference

As long as you only insert, erase, and find elements with a specific value, unordered containers provide the best running-time behavior because all these operations have amortized constant complexity.

were really high but cautious, as

Providing a good hash function is trickier than it sounds.

Benchmarking part of implementation using unordered_set container:

  // create a unordered set of double arrays (usda)
  std::unordered_set<std::array<double, N>, ArrayHash, ArrayEqual> usda;
  // record start time
  auto start = std::chrono::steady_clock::now();
  // Generate and insert one hundred thousands new double arrays
  for (size_t i = 0; i < 100000; ++i) {
    // Get a new random double array (da)
    std::array<double, N> da = getRandomArray();
  // record finish time
  auto end = std::chrono::steady_clock::now();
  std::chrono::duration<double> diff = end - start;
  std::cout << "Time to generate and insert unique elements into UNORD. SET: "
            << diff.count() << " s\n";
  std::cout << "unord. set size() = " << usda.size() << std::endl;

where a naive hash function:

// Hash Function
struct ArrayHash {
  std::size_t operator() (const std::array<double, N>& arr) const {
    std::size_t ret;
    for (const double elem : arr) {
      ret += std::hash<double>()(elem);
    return ret;

and equivalence criterion:

// Equivalence Criterion
struct ArrayEqual {
  bool operator() (const std::array<double, N>& arr1,
                          const std::array<double, N>& arr2) const {
    return EuclideanDistance2(arr1.begin(), arr1.end(), arr2.begin()) < tol*tol;
  static constexpr double tol = 1e-6;  // Comparison tolerance

3.3.1 Testing unsorted set's performance

In the last messy table below, I again summarise the execution time and the size of container depending on different tolerance (eps) values.

| eps | time(s) with -O3 flag/without optimization flags | size |

| 1e-6 | 57.4823 / 0.0590703 | 100000 / 100000 |

| 1e-3 | 57.9588 / 0.0618149 | 99978 / 100000 |

| 1e-2 | 43.2816 / 0.0595529 | 82873 / 100000 |

| 1e-1 | 0.238788 / 0.0578297 | 781 / 99759 |

Shortly, execution times are the best comparing with other two approaches, however even using quite loose tolerance (1e-1) almost all random vectors were identified as unique. So, in my case saving time for lookup but wasting much more time doing other expensive steps of my problem. I guess, this is because my hash function is really naive?

Edit: This is the most unexpected behaviour. Turning on -O3 optimization for the unordered set, decreased performance awfully. Even more suprising, the number of unique elements depends on the optimization flag, which is shouldn't be Probably this only means, that I must provide a better hash function!?

4. Open questions

  1. As I know in advances the maximum size of possible unique vectors would it make sense to use std::vector::reserve(100000)?

According to The C++ Programming Language by Bjarne Stroustrup reserve does not make big impact into the performance:

I used to be careful about using reserve() when I was reading into a vector. I was surprised to find that for essentially all of my uses, calling reserve() did not measurably affect performance. The default growth strategy worked just as well as my estimates, so I stopped trying to improve performance using reserve().

I have repeated the same experiment using vectors and eps = 1e-6 with reserve() = 100000 and in this case got that the total execution time was 111.461 (s) compared to 111.83 (s) without reserve(). So, the difference is negligible.

  1. How to provide better hash function for the situation described in

  2. General comments about the fairness of this comparison. How can I improve it?

  3. Any general comments how to make my code better and more efficient are very welcome - I love to learn from you, guys! ;)

P.S. Finally, is there (in StackOverflow) proper markdown support to create tables? In the final version of this question (benchmarking) I would like to put the final summarizing table.

P.P.S. Please feel free to correct my poor English.

I am learning C++ STL and one thing that not sure is how to safely use STL.

For example one thing, I am constantly catching myself is using container, without doing if (!container.empty()). Seems a trivial thing to do, but is source of bugs.

Are there any rules or guides on how to safely use STL ?

Edit: So far, I found one such guide JSF Air Vehicle - C++ Coding Standards - Joint Strike Fighter, but it seems to be outdated by now (or at least was not updated, though most rules are applicable to this day)

Here are a few coding guidelines that make container.empty() checks mostly superfluous

  • properly initialize your containers, preferably with initializer-lists. This will get you off with a good start and a non-empty container :-)
  • if you need to fill a container with values from a input stream, use a std::back_inserter (sequence containers) or std::inserter (associative containers). This will take care of properly expanding your container.
  • if you need to process a container, prefer to use a Standard Library algorithm that accepts the container iterators. These algorithms behave gracefully for empty input.
  • if you need to write your own algorithm, use the container iterators begin() and end() and make sure an empty container is caught by a statement like it != end(). This will avoid things like pop_back() or erase() on an empty container.
  • hand-written modifying algorithms can run into iterator invalidation. Make sure you understand those rules.

The last items are perhaps the most tricky ones to get right. You really want to write your algorithms as general as possible so that the empty case is encompassed naturally without special casing.

Effective STL by Scott Meyers is the recommended guide for beginning/intermediate users of the Standard Library.

I am new here. I am also new on C++ So here is the class and function i wrote.But i got the compiler error My class:

class fooPlayer
       void fooPlayerfunc(){}//doing something here
       char askYesNo(std::string question);

class fooPlayerFactory
   virtual std::auto_ptr<fooPlayer> MakePlayerX() const;
   virtual std::auto_ptr<fooPlayer> MakePlayerO() const;
   std::auto_ptr<fooPlayer> MakePlayer(char letter) const;
   std::auto_ptr<fooPlayer> my_player;


Implement my class:

auto_ptr<fooPlayer> fooPlayerFactory:: MakePlayer(char letter) const
       return my_player;

auto_ptr<fooPlayer> fooPlayerFactory::MakePlayerX() const
      char go_first = my_player->askYesNo("Do you require the first move?");
      return my_player;

auto_ptr<fooPlayer> fooPlayerFactory::MakePlayerO() const
    return my_player;

My main() function here:

int main()
          fooPlayerFactory factory;

I got the error: error C2558: class 'std::auto_ptr<_Ty>' : no copy constructor available or copy constructor is declared 'explicit'

I do not know how to change it even after reading the document on this link:

The reason for the error is that you are calling the copy constructor of auto_ptr my_player in fooPlayerFactory::MakePlayerO() which is a const method. That means that is cannot modify its members.

However the copy constructor of auto_ptr DOES modify the right hand side so returning my_player trys to change its pointer to 0 (NULL), while assigning the original pointer to the auto_ptr in the return value.

The signature of the copy constuctor is

auto_ptr<T>::auto_ptr<T>(auto_ptr<T> & rhs)


auto_ptr<T>::auto_ptr<T>(const auto_ptr<T> & rhs)

The copy constructor of auto_ptr assigns ownership of the pointer to the left hand side, the right hand side then holds nothing.

I don't think you want to use auto_ptr here, you probably want boost::smart_ptr

It looks like you have mixed up two uses for auto_ptr

The first is as poor man's boost::scoped_ptr. This is to manage a single instance of a pointer in a class, the class manages the life time of the pointer. In this case you don't normally return this pointer outside your class (you can it is legal, but boost::smart_ptr / boost::weak_ptr would be better so clients can participate the life time of the pointer)

The second is its main purpose which is to return a newly created pointer to the caller of a function in an exception safe way.


auto_ptr<T> foo() {
    return new T;

void bar() {
    auto_ptr<T> t = foo();

As I said I think you have mixed these two uses auto_ptr is a subtle beast you should read the auto_ptr docs carefully. It is also covered very well in Effective STL by Scott Meyers.

I am trying to figure out what the best and simplest way is of determining if a singly linked list is empty or not.

Would I need to create a boolean method?


Read Method

void List::Read(istream& r) {

char c[13];
r >> c;
r >> numberOfInts;

Node *node = new Node();

for(int i = 0; i < numberOfInts; i++)
    r >> node->data;
    cout << node->data << endl;
    node->next = new Node;
    //node = node->next;

    head = node;
    if(node->data > head->data)
    else if(node->data < head->data)
        Node* tempNode;
        tempNode = head;
        head->data = node->data;
        node->data = tempNode->data;


Header file

class Node
    Node() {}
    Node(int d, Node* q = 0) : data(d), next(q) {} //constructor with parameters data and next
    int data; //holds data in node
    Node* next;//pointer to next node

class List
    void Read(istream&);
    void Write(ostream&);

    void setReadSort(bool);
    void sortOwn();
    void insertionSort(Node*);
    bool isEmpty();

    bool _sortRead;
    int numberOfInts;

    Node *head;
    Node current;

Yes. The reason is: sometimes we use the iterator to insert element, it would be very uncomfortable (or impossible) to handle the number of the elements over the iterators. This is the reason why many STL implementation has linear time for size_t size(void) function. bool empty(void) is an effective way to check if the list is empty and it has constant time.

Just to note: when you use STL prefer to use bool empty(void) against size_t size(void). More info in: Meyers: Effective STL.

The function is simple:

bool empty( void ) const
  return ( this->begin() == this->end() );

In your case:

bool empty( void ) const
  return ( this->head == 0 );

I have created a container for generic, weak-type data which is accessible through the subscript operator.

The std::map container allows both data access and element insertion through the operator, whereas std::vector I think doesn't.

What is the best (C++ style) way to proceed? Should I allow allocation through the subscript operator or have a separate insert method?


I should say, I'm not asking if I should use vector or map, I just wanted to know what people thought about accessing and inserting being combined in this way.

In the case of Vectors: Subscript notation does not insert -- it overwrites.

This rest of this post distils the information from item 1-5 of Effective STL.

If you know the range of your data before hand -- and the size is fixed -- and you won't insert at locations which has data above it -- then you can use insert into vectors without unpleasant side-effects.

However in the general case vector insertions have implications such as shifting members upward and doubling memory when exhausted (which causes a flood of copies from the old vector's objects to locations in the new vector ) when you make ad hoc insertions. Vectors are designed for when you know the locality characteristics of your data..

Vectors come with an insert member function... and this function is very clever with most implementations in that it can infer optimizations from the iterators your supply. Can't you just use this ?

If you want to do ad-hoc insertions of data, you should use a list. Perhaps you can use a list to collect the data and then once its finalized populate a vector using the range based insert or range based constructor ?

In brief, my question is about member variables as pointers in unmanaged C++.

In java or c#, we have "advanced pointer". In fact, we can't aware the "pointer" in them. We usually initialize the member of a class like this:

member = new Member();


member = null;

But in c++, it becomes more confusing. I have seen many styles: using new, or leave the member variable in stack.

In my point of view, using boost::shared_ptr seems friendly, but in boost itself source code there are news everywhere. It's the matter of efficiency,isn't it?

Is there a guildline like "try your best to avoid new" or something?


I realize it's not proper to say "leave them in stack", here's a more proper way to say: when i need an object to be my member variable, should i prefer a object than a object*?

I trying to convert some loops in my code to use the for_each functionality of the STL. Currently, I calculate and accumulate two separate values over the same set of data, requiring me to loop over the data twice. In the interest of speed, I want to loop once and accumulate both values. Using for_each was suggested as it apparently can be worked into a multithreaded or multiprocessor implementation fairly easily (I haven't learned how to do that yet.)

Creating a function that only loops over the data once and calculates both values is easy, but I need to return both. To use with for_each, I need to return both calculated values at each iteration so STL can sum them. From my understanding, this isn't possible as for_each expects a single value returned.

The goal with using for_each, besides cleaner code (arguably?) is to eventually move to a multithreaded or multiprocessor implementation so that the loop over the data can be done in parallel so things run faster.

It was suggested to me that I look at using a functor instead of a function. However, that raises two issues.

  1. How will using a functor instead allow the return accumulation of two values?
  2. I have two methods of applying this algorithm. The current code has a virtual base class and then two classes that inherit and implement the actual working code. I can't figure out how to have a "virtual functor" so that each method class can implement its own version.


Here is an example of using a functor to perform two accumulations in parallel.

struct MyFunctor
    // Initialise accumulators to zero
    MyFunctor() : acc_A(0), acc_B(0) {}

    // for_each calls operator() for each container element
    void operator() (const T &x)
        acc_A += x.foo();
        acc_B += x.bar();

    int acc_A;
    int acc_B;

// Invoke for_each, and capture the result
MyFunctor func = std::for_each(container.begin(), container.end(), MyFunctor());

[Note that you could also consider using std::accumulate(), with an appropriate overload for operator+.]

As for virtual functors, you cannot do these directly, as STL functions take functors by value, not by reference (so you'd get a slicing problem). You'd need to implement a sort of "proxy" functor that in turn contains a reference to your virtual functor.* Along the lines of:

struct AbstractFunctor
    virtual void operator() (const T &x) = 0;

struct MyFunctor : AbstractFunctor
    virtual void operator() (const T &x) { ... }

struct Proxy
    Proxy(AbstractFunctor &f) : f(f) {}
    void operator() (const T &x) { f(x); }
    AbstractFunctor &f;

MyFunctor func;
std::for_each(container.begin(), container.end(), Proxy(func));

* Scott Meyers gives a good example of this technique in Item 38 of his excellent Effective STL.

Say I have a binary tree with the following definition for a node.

struct node
 int key1 ;
 int key2 ;

The binary search tree is created on the basis of key1. Now is it possible to rearrange the binary search tree on basis of key2 in O(1) space. Although I can do this in variable space using an array of pointers to nodes.

The actual problem where I require this is "counting number of occurrences of unique words in a file and displaying the result in decreasing order of frequency." Here, a BST node is

 char *word;
 int freq ;
The BST is first created on basis of alphabetic order of words and finally I want it on basis of freq.

Am I wrong at choice of data structure i.e a BST?

Map, BST are good if you need to have sorted output for your dictionnary.

And it is good if you need to mix up add, remove and lookup operations. I don't think this is your need here. You load the dictionnary, sort it, then do only look up in it, that's right ? In this case a sorted array is probably a better container. (See Item 23 from Effective STL from Scott Meyer).
(Update: simply consider that a map could generate more memory cache misses than a sorted array, as an array get its data contiguous in memory, and as each node in a map contain 2 pointers to other nodes in the map. When your objects are simple and take not much space in memory, a sorted vector is probable a better option. I warmly recommand you to read that item from Meyer's book)

About the kind of sort you are talking about, you will need that algorithm from the stl: stable_sort. The idea is to sort the dictionnary, then sort with stable_sort() on the frequence key.

It will give something like that (not tested actually, but you got the idea):

struct Node
char * word;
int key;

bool operator < (const Node& l, const Node& r)
    return std::string(l.word) < std::string(r.word));

bool freq_comp(const Node& l, const Node& r)
    return l.key < r.key;

std::vector<node> my_vector;
... // loading elements
sort(vector.begin(), vector.end());
stable_sort(vector.begin(), vector.end(), freq_comp);

Which is better (space/time) to find certain strings:

  1. To use a vector of strings (alphabetically ordered) and a binary search.

  2. To use a BST of strings (also ordered alphabetically).

Or are both similar?

Both have advantages, and it is going to depend on what your usage scenario is.

A sorted vector will be more efficient if your usage scenario can be broken into phases: load everything, then sort it once, then look things up without changing anything.

A tree structure will work better for you if your scenario involves inserting, searching, and removing things at different times, and you can't break it into phases. (In this case, a vector can add overhead, since inserting in the middle is expensive.)

There's a really good discussion of this in Effective STL, and there's a sorted vector implementation in Loki.

Possible Duplicate: What is the difference between const int*, const int * const, and int const *?

What is the difference between the following?

char const *p;
const char  *p;
char *const p;

And is there a good site where I can relearn C and C++? It seems that I forgot it and job interviews are doing me an hard time...

  1. Buy a copy of Kernighan & Ritchie (K&R) and work through it.
  2. Do the exercises in K&R and understand the solutions provided in The C Answer Book.
  3. Buy a copy of Accelerated C++ and work through it, because it treats C++ as its own language and not just C with "bits bolted on".
  4. Buy a copy of Effective C++, don't violate the items and read each one to understand why you shouldn't violate them.

As an added bonus, read Effective STL to use the STL properly.

Could you let me know about books that explains the ideas of smart pointer very clearly (beginner, intermediate and advanced level)?

Thank you.

Scott Meyers has an a few items on it. You might not need a whole book.

Scott Meyers books :

Effective C++

More Effective C++

Effective STL

Do you just base your STL container selections on the following attributes?

  1. Searching/Updating
  2. Insertion and
  3. Deletion

If not, what else do you base your selections upon? Is there any reference out there that lists how each container performs across all these different attributes?

Scott Meyers' Effective STL covers not only this, but the weird pitfalls that you'll run into with some of the odder containers like set.

I am a fairly capable Ruby scripter/programmer, but have been feeling pressure to branch out into C++. I haven't been able to find any sites along the lines of "C++ for Ruby Programmers". This site exists for Python (which is quite similar, I know). Does anyone know of a guide that can help me translate my Ruby 'thoughts' into C++?

If you want to learn C++, start here. Once you have learned the fundamentals, you should also look into these: Effective C++, More Effective C++, Effective STL, and Exceptional C++

I had this problem happen to me in the past http://www.parashift.com/c++-faq-lite/ctors.html#faq-10.19

My question is, when writing

Foo x(Bar());

Why is it "declaring a non-member function that returns a Bar object" ? i can understand it if i wrote

Foo x(Bar);

But what does it think the () means in Bar()?

Unfortunately it doesn't seem to be online, but Scott Meyers' book, Effective STL, has a good, detailed explanation of what's going on in your example in Item 6: Be alert for C++'s most vexing parse.

On the plus side, the book is worth the price for anyone serious about C++.

I was trying to run the below code. What I am finding is that there is difference in the output. I understand that there is an issue with ordering mechanism used in the Comparator functionality. What I am basically looking for is: 1) How does Set internally stores data. 2) How can I resolve this issue or the best way to copy the data to a different Set. 3) How exactly the ordering is creating this issue.

#include <iostream>
#include <set>
using namespace std;
struct Comparator {
  bool operator()( const int& a, const int& b ) {
    if( a <= b ) 
      return true;
      return false;
int main()
  set< int, Comparator > customSet;
  for( unsigned k = 0, index = 2; k < 10; ++k ) {
    customSet.insert( index );

  set< int, Comparator >::iterator iter = customSet.begin();
  for(; iter != customSet.end(); ++iter ) {

  set< int, Comparator > tempCustomSet ;//= customSet;
  tempCustomSet.insert( customSet.begin(), customSet.end() );

  iter = tempCustomSet.begin();
  for(; iter != tempCustomSet.end(); ++iter ) {

  return 0;

See this reference for more details on std::set. The implementation should not concern you (they can differ from platform to platform), since the interface and complexity guarantees is all that matters to the Standard. Typical implementations are using red-black-trees.

You need to make your Comparator use operator< and not operator<=. The reason is that std::set will consider elements equivalent if !Comparator(a, b) && !Comparator(b, a) evaluates to true (i.e. neither is strictly less than the other).

But with <=, you have a <= a equal to true, so that !(a<=a) && !(a<=a) gives false for equal elements. Whereas with < you have a < a equal to false so !(a<a) && !(a<a) gives true.

The right to thing to do is:

struct Comparator 
    bool operator()(int const& lhs, int const& rhs) const 
        return lhs < rhs; 

This will guarantee that equal elements are considered equivalent. Note that this is discussed at length in Effective STL, "Item 19. Understand the difference between equality and equivalence."

Question 1>

I would like to know why in case I we have to use not2(ptr_fun(ciCharCompare)), while in case II, we just need to use ciCharLess. Why not use ptr_fun(ciCharLess) instead?

Question 2>

Is there a general rule that I can follow when to use which form?

Thank you

case I:

int ciCharCompare(char c1, char c2)
// case-insensitively compare chars c1 and c2
// return -1 if c1 < c2
// return 0  if c1 == c2
// return 1  if c1 > c2

string s1("Test 1");
string s2("test 2222222222222222");

pair<string::const_iterator, string::const_iterator>
    p = mismatch(s1.begin(), s1.end(),


template <class InputIterator1, class InputIterator2, class BinaryPredicate>
pair<InputIterator1, InputIterator2>
mismatch (InputIterator1 first1, InputIterator1 last1,
          InputIterator2 first2, BinaryPredicate pred );

Binary predicate taking two elements as argument

Case II:    
bool ciCharLess(char c1, char c2)
    // return true if c1 precedes c2 in a case insensitive comparison

lexicographical_compare(s1.begin(), s1.end(), s2.begin(), s2.end(),


Comparison function object that, taking two values of the same type than those contained in the range, returns true if the first argument is to be considered less than the second argument.

Why not use ptr_fun(ciCharLess) instead?

You could use ptr_fun(ciCharLess) if you wanted. All ptr_fun does is convert your function pointer into a functor, which contains some typedefs such as result_type. Most algorithms don't need it, but some (particularly binders such as not2) do need it.

Generally speaking, because you're never going to be wrong by using ptr_fun on a function pointer type (note: applying it to a type which is already a functor is wrong), I just use it everywhere. The worst thing that can happen then is someone raising their eyebrows a bit as to why the wrapper is there if it need not be. If you don't use it and it needs it the compiler is going to complain quite loudly at you.

For more information on the specific bits that ptr_fun is for, see Scott Meyers' Effective STL Item 41: Understand the reasons for ptr_fun, mem_fun, and mem_fun_ref.

(Long story short, these binder adapters are required to make up for some syntactic inconsistencies in the language; e.g. functors and function pointers are called like identifier(args), member functions called via a pointer are object->identifier(args), and member functions called via a reference are object.identifier(args).)

Suppose I've an empty list L. Currently if I run L.front(), it will merrily execute returning a garbage value. Is there some option I can turn on such that executing this would throw an exception or result in an assertion failure?


Use empty() to check if the list is empty. size() is not good here because it could have linear runtime. See more details in Effective STL. empty() has constant runtime and it is a standard way.

The average length is 4 characters for the strings. I was thinking a binary search might be the fastest starting at position 4. Also I think an inlined templatized function might perform well. This is done in a very tight loop so performance is critical.

The data looks like:

"1234    "
"ABC     "
"A1235   "
char* found = std::find(arr, arr+9, ' ');

Note that 'no match' is signaled wuth the end iterator:

bool match = (arr+9) != found;

Note, that

  • binary search doesn't apply unless you characters are in some known ordering.
  • std::find is inlined, templatized and will perform to the max if you turn on optimization (e.g. -O3 -march=native for g++)

Edit since you have shown more code, I now realize you actually want to detect (sub)string length. You could use

Of course, that assumes you'd want to convert the char[] to std::string for the purpose. In practice, that might be a perfectly valid idea, because of SSO (Small String Optimization) found in nearly all implementations of the C++ standard library. (see Items 13-16 in Herb Sutter's More Exceptional C++, or Scott Meyers' discussion of commercial std::string implementations in Effective STL).

What is the purpose of the sequential container adaptors (i.e; stack, queue) in C++?


The best answer to your question would be to read the following book:

Effective STL

However if you want a quick and dirty answer: Not only do stacks and queues model real world objects such as program stacks and process queues, they also are optimal for random insert and delete operations.

What’s the best language and IDE to develope socket server? I want a language I can learn quickly that will work on an enterprise level. Please set me up with some good resources:)

'I only know Flash and scripting languages'
• C languages and VB++

I’m tring to get my Flash animations to connect to an old backend system. The IT director of my company left, and I don’t want the project to get canned. I’m willing to stay up nights learning, as long as I can get a prototype made.

WHAT I'M DOING 'Connecting to an archaic back-end system'

alt text

No time contraints or limits

Is any of the languages already used in your enterprise?
C and VB are used

How complex should your socket server be?
Not complex, but have a good library and foundation to expand later

Can you use something already existing?
Yes, but it can't cost anything

What is your purpose
Learning and proof of concept is my purpose. Out of the box solution would be ideal, but sometimes implementing a new framework takes as much time, and could go against what's already in place. I'm likely to go with a language that I can continue use in game development.

What’s the best language and IDE to develope socket server?

Any language that supports sockets programming (almost anything). The question is a bit simplistic.

I want a language I can learn quickly that will work on an enterprise level.

You can learn quickly most languages, but to become proficient in them may take time. More than that, the language doesn't matter as much as the library you use.

Here are a few examples of what I mean:

Python takes little time to become proficient with, but I'm not sure how "enterprise level" it is (it's used by NASA, Google and a few other major players so it may be enough).

It is also very high-level, so I wouldn't be surprised if you can write the code for a simple socket server within ten lines of code (it only takes one line of code for creating a web server in python).

Java and C#/C++.cli/VB+ should support the creation of a socket server with relatively few lines of code, as (the same as python) they have already-made libraries supporting most of the functionality.

They are more verbose than Python though so you'll write much more code.

I don't know much about PHP to say how good it would be for this.

C is too low level which means you'll probly write more code than the others mentioned. It's very powerful, but writing the project in C will take you at least a week of writing code and a week (probably many more) in debugging it - especially if you're new with the language.

C++ is ... well across the spectrum (it is both high and low level) but it is difficult to use correctly (it has many quirks and the mistakes you make are not obvious until you understand why it's designed as it is). C++ would probably take more than C to learn and use correctly.

Please set me up with some good resources:)+

I would but your question is too broad. Here are some questions to narrow it down:

  • what are your time constraints?

  • are there any limits?

  • is any of the languages already used in your enterprise?

  • how complex should your socket server be?

  • can you use something already existing?

  • what is your purpose (do you need socket-server functionality urgently? do you need to learn sockets programming? do you need a socket-server-based solution to a problem you have?)


Considering your answers, I'd recommend going with C++ and boost (boost::asio specifically). Here's my reasoning:

I'm likely to go with a language that I can continue use in game development.

C++ is the language of choice for game development. It has many pitfalls, but the advantages seem to outweigh that.

If you use good C++ practices you will avoid most of the pitfalls and reasonably manage the ones you can't avoid. ( If you want a list of good practices or common C++ pitfalls ask a new question :) ).

it can't cost anything

Neither C++ nor boost cost anything.

For IDEs, you can download Microsoft's Visual Studio 2010 Express (free) for Windows, and use Eclipse+CDT or Code::Blocks for other platforms (I think they're available for Windows also).

If possible, also use a distributed source control system (like Git or Mercurial). They save you a lot of headaches and make managing the code much easier.

Learning and proof of concept is my purpose.

You will learn a lot :D.

Here are some resources to get you started:

For C++ look at Thinking in C++ (free) and (if you can get your hands on them) Effective C++, More Effective C++ and maybe Effective STL.

For boost, the boost documentation (also free) should be enough, once you get started with C++.

Specifically, have a look at the boost::asio examples. They offer the complete source code for various servers (HTTP servers, echo servers and so on).

boost::asio is an already implemented framework, but learning C++ and the boost libraries on top of it may require a steep learning curve on your side.

I am trying to add a scalar value to all entries of the vector without a loop. The most obvious way is to use a loop.

for ( auto it = a.begin(); it != a.end(); ++it )
   *it += scalar;

I want to use algorithm and functional to do this and one other way I figured out was to do something like this:

std::transform( a.begin(), a.end(), a.begin(), std::bind2nd( std::plus< int > (), scalar ) );

While reading through the documentation, I learnt that bind2nd is deprecated in C++11.

  1. What is the best way to do this without using deprecated features of C++11?
  2. Apart from a few less lines of code, do I get any performance advantage by using std::transform instead of using a loop?

First std::bind1st, and bind2nd, are replaced with std::bind. See below. I am using the new std::bind syntax with the placeholders. I'm also storing the results in another container using a std::back_inserter.

using namespace std::bind::placeholders::_1; 
std::vector<int> result;
std::transform(ints.begin(), ints.end(), std::bind(std::plus<>, _1, 5), std::back_inserter(result));

Regarding your second question, it is considered preferred c++ style to prefer algorithms over hand written loops. I'd recommend reading Scott Meyers Effective STL Item 43, "Prefer Algorithm calls to hand written loops". Their is also a discussion in this article on DrDobbs.

I have a Matrix class and I want to pass an array to the constructor in order to set the values of the matrix dynamically. I found that if I allocate an array like this:

double **array;
array = new double*[3];
array[0] = new double[2];
array[1] = new double[2];
array[2] = new double[2];
array[0][0] = 1;
array[0][1] = 1;
array[1][0] = 1;
array[1][1] = 1;
array[2][0] = 1;
array[2][1] = 1;

I can get the number of rows and cols using a method like this:

int getNRows(double **data){
  int size = 0;
  return size;

int getNCols(double **data){
  int size = 0;
  return size;

Is this ok or should I stick to the vector declaration?

What happens when you store the value 0 in your array? You need to store and pass the sizes to functions that operate on your data structure, or use an STL container like std::vector.

Please pick up a copy of Effective STL.

Also, if you want to be more clear about why you need a multi-dimensional array, we may be able to propose a better solution.

I need a long list of objects ordered by one of they're parameters. What is the fastest way to do this in C++? I need to be able to add and remove elements to this list and still be sorted by that specific parameter.

Class Foo {
  int rank;

I want all my Foo objects to be listed in ascending order and when a new one is added or deleted it should take the right spot in the order. There can also be more than one object with the same rank so key-value is not possible.

Any idea how I can do this in C++? I was looking at make_heap() but I'm not sure how to use it (or if it can be used) with objects.

First you should probably define operator< for Foo (something like this)...

inline bool operator< (const Foo& lhs, const Foo& rhs) {
  return lhs.rank < rhs.rank;

which will need to be declared as a friend of Foo's:

class Foo {
  explicit Foo(int rank_init) : rank(rank_init) {}
  friend bool operator< (const Foo&, const Foo&);
  int rank;

Now you can create a std::multiset<Foo> which will keep the Foos sorted ascending by rank, e.g.

std::multiset<Foo> foo_multiset;
foo_multiset.insert(Foo(5));  // 5
foo_multiset.insert(Foo(3));  // 3, 5
foo_multiset.insert(Foo(1));  // 1, 3, 5
foo_multiset.insert(Foo(3));  // 1, 3, 3, 5
size_t erased_count(foo_multiset.erase(Foo(3)));  // 1, 5 (erased_count == 2)

There are no guarantees however that this will be the "fastest" option in your particular case. You'll need to profile for that. Depending on the number of elements, the frequency of insert/erase operations, and the STL implementation, you could find that a sorted std::vector<Foo> better suits your needs.

Scott Meyers' Effective STL describes how this could be the case in Item 23.

I've studied C++ as a college course. And I have been working on it for last three years. So I kinda have a fairly good idea what is it about. But I believe to know a language is quite different from using it to full potential. My current job doesn't allow me to explore much.

I have seen you guys suggest studying a open source project and perhaps contributing to one too. So my question is, can you suggest one(of both?) to start with that is simple and doesn't overwhelm a starter.

I was in the same situation 12 years ago when I got my first programming job out of college. I didn't do any open source but I managed to gain a lot of practical and advanced C++ knowledge by reading books (the dead tree kind).

In particular, there was an excellent series by Scott Meyers which I feel helped the most in turning me from newbie to professional:

Effective C++: 55 Specific Ways to Improve Your Programs and Designs

More Effective C++: 35 New Ways to Improve Your Programs and Designs

Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library

The topics in these books range from beginner to advanced. It took me about 2 years working in C++ to understand every chapter in these books, so don't be disheartened if it goes over your head at some point... just try reading it again later :)