Hidden Features and Dark Corners of STL?

Question

C++ developers, all know the basics of C++: Declarations, conditionals, loops, operators, etc.

Some of us even mastered the stuff like templates, object model, complex I/O, etc.

But what are the most hidden features or tricks or dark corners of C++/STL that even C++ fans, addicts, and experts barely know?

I am talking about a seasoned C++ programmer (be she/he a developer, student, fan, all three, etc), who thinks (s)he knows something 99% of us never heard or dreamed about. Something that not only makes his/her work easier, but also cool and hackish. After all, C++ is one of the most used programming languages in the world, thus it should have intricacies that only a few privileged know about and want to share with us.

Boost is welcome too!

One per post with an example please

P.S Examples are important for other developers to copy and paste!

Answer 1

swap()

Allows your code to avoid needless copies by swapping the internal representation of 2 containers.

 std::vector<unsigned char> src;
 std::vector<unsigned char> dest;

 //... fill in src

 // Destination takes on source's buffer
 dest.swap(src);

Answer 2

Using std::fill and std::partial_sum, you can generate a range of numbers.

size_t count = 10;
// **This is assuming the vector was already constructed somewhere earlier**
std::vector<int> values(count);
std::fill(values.begin(), values.end(), 1);
// if the first number is not 1:
// values[0] = start;
std::partial_sum(values.begin(), values.end(), values.begin());

Edit: obviously if you are constructing the vector specifically for the range, you can use the following and leave out the call to std::fill:

std::vector<int> values(count, 1);

Answer 3

Though not techncially part of the STL.
The streams library is part of the standard C++ libs.

For streams:

Locales.

Very few people actually bother to learn how to correctly set and/or manipulate the locale of a stream.

The second coolest thing is the iterator templates.
Most specifically for me is the stream iterators, which basically turn the streams into very basic containers that can then be used in conjunction with the standard algorithms.

Examples:

• Did you know that locals will change the '.' in a decimal number to any other character automatically.
• Did you know that locals will add a ',' every third digit to make it easy to read.
• Did you know that locals can be used to manipulate the text on the way through (ie conversion from UTF-16 to UTF-8 (when writting to a file).

etc.

Examples:

• Adding comma for every three digits
• Using space as the seporator
• Set the decimal seporator
• Simple output filter
• Set the current locale
• Count number of characters sent to output
• Indent every line
• UTF-16 (stream) -> UTF-16 (Internal) Converter (untested)

Answer 4

Once you start using the STL algorithms and need unary functions, knowing how to use bind is incredibly helpful. It lets you easily convert binary functions into the unary functions.

Edit Suppose you want to multiply all the numbers is a container by 5. Rather than looping or defining your one off functor, use bind1st:

transform(container.begin(), container.end(), container.begin(),
          bind1st(multiplies<double>(),5.0));

Answer 5

Locales/facets and valarray/slice/gslice/ are probably the most obvious, at least to me.

In the other direction, I think mem_fun/mem_fun_ref/bind1st/bind2nd, etc., usually produce code that looks obscure and is often nearly impossible to read, but it seems that nearly everybody who starts using algorithms overuses these severely for at least a while. There are really two culprits: for_each (which is severely overused itself), and lack of lambdas (in the current language). The FOR_EACH from boost can help quite a bit, and the lambda support in C++ 0x will help a lot more.

Edit to add examples:

Locales: to get output in readable format with iostreams:

#include <iostream>
#include <locale>

int main() { 
    std::locale loc("");
    std::cout.imbue(loc);

    std::cout << 1234.56;
    return 0;
}

Produces:
1,234.56
for me, but for a typical German user (for example) would produce:
1.234,56
As he'd expect.

valarray: for example, to compute the variance of elements in an array:

// Warning: only minimally tested
template <class T>
T const variance(T *values, size_t size) {
        std::valarray<T> const v(values, size);
        T average = v.sum() / static_cast<T>(v.size());
        std::valarray<T> diffs = v-average;   
        diffs *= diffs;

        // unsigned arithmetic is fine here -- all numbers are positive.
        return diffs.sum()/diffs.size();

}

Doing the same with std::vector and the standard algorithms (e.g. std::inner_product, std::accumulate) produces code that's substantially longer and harder to read or understand.

Edit: more about for_each (in response to comment). The position of for_each among algorithms is similar to the position of goto among control structures. If you advocate it, each can be seen as flexible, versatile, and usable in almost every possible circumstance.

That flexibility becomes the Achilles heal of each: using it tells the reader virtually nothing about what you're really trying to accomplish. Its usage imparts essentially no information to the reader -- the actual intent of each can be ascertained only by careful examination of the surrounding code to figure out what it does.

Answer 6

Programming is not about proving how clever you are. It's rarely even about how well your compiled code performs. Usually, the most important thing is how well it can be understood by the next guy who has to extend or debug it.

In general you shouldn't use unknown corners of libraries. If they are unknown, then they are little used, and readers of your code will struggle to understand them.

Answer 7

Google "most vexing parse". C++ doesn't get much darker than that ;-)

Answer 8

Streambufs and streambuf iterators. Most people don't know about streambufs, only about streams. The latter is in fact a high-level wrapper around the former that provide formatting and locale-specific functions. While formatting is often what you want, for low-level I/O where speed is essential you want to bypass the stream and use the stream buffer. (In C terms, this is like the difference between printf/scanf and fputc/fgetc.)

An example of use from Dr. Dobb's Journal (the source of the above link). Note that this can be considerably faster than using istream::operator<<. It is for byte-level control, not for text-processing.

#include <istream>
#include <fstream>

using namespace std;

void read_buffer(streambuf * buffer)
{
    istreambuf_iterator<char> i(buffer);
    istreambuf_iterator<char> end;
    while (i != end)
    {
        char c = *i;
        // Do something with c
    }

}

int main()
{
    // Use a stream
    ifstream   in("filename.txt");
    streambuf* buf = in.rdbuf();
    read_buffer(buf);

    // Directly use a buffer
    filebuf    buf("filename.txt");
    read_buffer(&buf);
}

Answer 9

I'd vote for boost::bind() as a very powerful idiom that many people don't tend to come across. Conceptually it's a means to convert a function into an object that can be copied around and called at a later point, so you can use it for deferred callbacks. For instance you can use it with boost::thread to wrap the thread function:

void MyStaticThreadFunc(Data* someData) {
...
}

Data* myData=new Data;
t=new boost::thread(boost::bind(&MyStaticThreadFunc,myData));

Another very powerful use becomes evident when combined with its overloads for operator== so that you can combine with find_if (or copy_if, remove_if, etc) to call any member function of a class in a container:

struct Record {
   string  GetEmployeeName();
   int     GetWage();
};

std::vector<Record>  records;
std::vector<Record>::iterator it;
it=std::find_if(records.begin(), records.end(), boost::bind(&Record::GetEmployeeName, _1) == "John Smith");

Answer 10

I usually don't like to just list books, but there's one that really targets the "dark corners" of the STL, and that's Scott Meyer's "Effective STL".. Lots of gotchas and unexpected features covered, for example:

• Copying containers
• Iteration invalidation
• Erasing containers (you wouldn't think this was tricky but...)
• Swaps
• Subtleties of memory management (many, many subtleties, sigh)

Check out the table of contents.

Answer 11

I really like the inner_product function. Normally, it calculates the dot product of a vector and a transposed vector, given as iterator ranges (what else?) but it can be properly parametrized to perform about any accumulation on two ranges.

Although, to be honest, I am not sure using it is a good idea for code clarity. Still, it has a true ring of function-oriented programming.

Consider this one-line¹⁾ implementation of the Hamming distance:

unsigned int hamming_distance(std::string const& a, std::string const& b) {
    return std::inner_product(
        a.begin(), a.end(), b.begin(), 0, std::plus<unsigned int>(),
        compose<unsigned int>(
            std::bind1st(std::minus<unsigned int>(), 1),
            std::equal_to<unsigned int>()));
}

Admittedly, I had to create a (trivially implemented) compose function to handle function composition – and unfortunately I had to make it use two parameters (which isn’t quite proper) because C++ doesn’t understand currying.

For comparison, here’s the almost exact equivalent in Python (taken from the abovementioned article), and it’s easy to see that the C++ method is absolutely superior in every aspect:

def hamming_distance(s1, s2):
    return sum([ch1 != ch2 for ch1, ch2 in zip(s1, s2)])

---

¹⁾ Well, it’s really a “one-expression” implementation.

Answer 12

The stupid 'swap' trick to actually free memory when you clear a vector.
I really want to find the guy that thought that was a better alternative to a free() function.

std::vector<int> vi;
vi.reserve(1000000); // don't ever do this
std::copy(
    std::istream_iterator<int>(cout),
    std::istream_iterator(),
    std::back_inserter(vi) );

vi.size(); // let's say 10
vi.capacity(); // 1000000

std::vector<int>(vi).swap(vi); // almighty swap trick
// vi.free() or vi.reserve(0) both would have been clearer

vi.size(); // still 10
vi.capacity(); // 10 Q.E.D.

Answer 13

I would say that in general, the use of meta-programming technics is quite foreign to most of the C++ developers I know...

But a library that changed my life is incontestably Boost.MultiIndex (and its adapter, Boost.BiMap). Before that trying to maintain multiple indexes on a structure was really hackish and error-prone.

EDIT: example (shamelessly taken from Bimap Reference)

struct id   {}; // Tag for the identification number
struct name {}; // Tag for the name of the person

typedef bimap <
       set_of < tagged< int        , id   > >,
  multiset_of < tagged< std::string, name > >
> People;

People people;

// ...

int user_id;
std::cin >> user_id;

People::map_by<id>::const_iterator id_iter = people.by<id>().find(user_id);
if( id_iter != people.by<id>().end() )
{
  std::cout << "name: " << id_iter->get<name>() << std::endl
            << "id:   " << id_iter->get<id>()   << std::endl;
}
else
{
  std::cout << "Unknown id, users are:" << std::endl;

  for( People::map_by<name>::const_iterator
        name_iter = people.by<name>().begin(),
        iend      = people.by<name>().end();
       name_iter != iend; ++name_iter )
  {
    std::cout << "name: " << name_iter->get<name>() << std::endl
              << "id:   " << name_iter->get<id>()   << std::endl;
  }
}

As you can see, I can easily traverse the Bimap either ordered by id or by name.

Also note the various ways of indexing:

• set_of: ordered, unique
• multiset_of: ordered, non-unique
• unordered_set_of: non-ordered, unique (hash...)
• unordered_multiset_of: non-ordered, non-unique (hash...)
• list_of: sequence (ordered by your insertions / removal)
• vector_of: same as list_of, but provide random access
• unconstrained_set_of: no constraint at all, makes your bimap mimics a classic map

Of course, this uses MPL behind the covers, but it's so much more practical (notably the 'tagged' option), and then you also get some really nice possibilities due to the interaction with other Boost libraries (such as Boost.Range), for example, taken from another page of the reference:

typedef bimap< std::string, unconstrained_set_of<int> > bm_type;
typedef bm_type::left_map map_type;

bm_type bm;
map_type & m = bm.left;

// ... filling the map

typedef map_type::const_iterator const_iterator;
typedef std::pair<const_iterator,const_iterator> const_range;

const_range r = m.range( "one" <= _key, _key <= "two" );
for( const_iterator i = r.first; i != r.second; ++i )
{
  std::cout << i->first << "-->" << i->second << std::endl;
}

The range is very nicely defined, using a 'lambda' like syntax, which makes for effortless 'equal_range'.

Answer 14

A C++ one, placement

CObject *p = (CObject*)malloc(sizeof *p);
...
p = new(p) CObject;
p->DoSomthing();
...

Answer 15

You wouldn't believe how many C++ programmers don't know this simple trick, even though it's rather obvious when you know how iterators and how initializing a container with an iterator range work.

int main(int argc, char* argv[])
{
    std::vector<std::string> params(argv, argv+argc);
    // Now all the command-line parameters are in the 'params' vector

}

In fact, I have seen quite some C++ programs out there which don't take advantage of initializing (or assigning) containers with iterator ranges even though they could. It seems that many C++ programmers simply haven't understood the usefulness of this simple thing.

Answer 16

This one is coming from James Kanze

Hardly a dark corner, but I find a lot of programmers aren't aware of std::accumulate (perhaps because it's in the math section of the standard, rather than the algorithms). Define a custom accumulator type, and it can be used for a lot of things. For example, if I want to append an MD5 checksum to a string, I'll use something like:

   s += std::accumulate(s.begin(), s.end(), MD5Hasher());

(where s is a string, and MD5Hasher is an accumulator which generates the MD5 checksum, and has an implicit conversion to string which returns the hash generated so far).

Practically, accumulate is usable just about any time you want to generate a single value which depends on a sequence of values.

Answer 17

Those who know what allocator::rebind does, please put your hands up.

I write my own allocator, and I override the allocator::pointer so that it points to my object instead of a normal pointer. And I use this when I construct an STL container.

I use shared memory to maintain a look-up table that can be accessed from multiple applications. Since different processes will map the shared memory to a different base address, pointer code in STL containers don't work. I wrote my own pointer class that actually stores the offset and when dereferenced will automatically apply the base address.

While, this is within the standard, this is so obscure that it only worked with MSVC7.0-7.1 and icpc7-9. g++ never supported it and even the latest version of MSVC don't support it. Most STL libraries simply need to assume that you are working with a regular pointer.

This is what a custom allocator looks like (M::ptr contains the base address):

template<class T, class M>
class var_allocator
{
public:
   typedef T value_type;
   typedef size_t size_type;
   typedef ptrdiff_t difference_type;
   typedef relative_ptr<T,M> pointer;
   typedef const_relative_ptr<T,M> const_pointer;
   typedef T& reference;
   typedef const T& const_reference;

   var_allocator() {}
   var_allocator(const var_allocator<T,M> &) {}
   template<class U>
   var_allocator(const var_allocator<U,M> &) {}
   pointer address(reference ref) const { return &ref; }
   const_pointer address(const_reference ref) const { return &ref; } 
   void* raw_allocate( size_type size , size_type n , void* )
   {
      return mm_malloc(M::Ptr, size * n);
   }
   void raw_deallocate( void* ptr )
   {
      mm_free(M::Ptr, ptr);
   }
   pointer allocate( size_type n , const void* )
   {
      return (pointer)raw_allocate( sizeof(T), n, NULL);
   }
   pointer allocate( size_type n )
   {
      return (pointer)raw_allocate( sizeof(T), n, NULL);
   }
   void* _Charalloc(size_type size)
   {
     return raw_allocate(size, 1, NULL);
   }
   void deallocate( pointer ptr, size_type )
   {
      raw_deallocate(ptr);
   }
   void deallocate( pointer ptr )
   {
      raw_deallocate(ptr);
   }
   void deallocate( void* ptr, size_type )
   {
      raw_deallocate(ptr);
   }
   void deallocate( void* ptr )
   {
      raw_deallocate(ptr);
   }
   void construct(const relative_ptr<T,M> &ptr, const T& val)
   {
      new ((void *)ptr) T (val);
   }
   template <class U> void construct(U* ptr, const U& val) 
   { 
      new (ptr) U (val); 
   }
   template <class U> void construct(U *ptr, int)
   {
      new (ptr) U;
   }
   template <class U> void construct(relative_ptr<U,M> &ptr, const U& val)
   {
      new ((void *)ptr) U (val);
   }
   template <class U> void construct(relative_ptr<U,M> &ptr, int)
   {
      new ((void *)ptr) U;
   }
#ifdef _WIN32
#pragma warning(disable: 4100)
#endif
   template <class U> void destroy(U *ptr)
   {
      (*ptr).~U();
   }
#ifdef _WIN32
#pragma warning(default: 4100)
#endif
   template <class U> void destroy(relative_ptr<U,M> &ptr)
   {
      ptr->~U();
   }
   size_type max_size() const
   {
      return mm_core_size(M::Ptr) / sizeof(T);
   }
   template <class U>
   struct rebind 
   {
      typedef var_allocator<U,M> other;
   }; 
};

template<class M>
class var_allocator<void,M>
{
  typedef relative_ptr<void,M> pointer;
};

Answer 18

Allocators

This article has some information about allocators. I don't understand them too well myself, so ,for me, they are a dark corner. This could allow you to use std::vector but force it to create shared_ptrs or use a preallocated/specific (and possible shared/file-mapped/etc) block of memory.

Edit: found another SO post relevant to my answer.

Answer 19

A feature that is often forgotten (and therefore implemented by hand in various ways) are the little iterator functions distance and advance.

They both operate on all standard containers and container adapters and use the most efficient implementation for each container, depending on the supported iterator type (random access, bidirectional, forward, ...).

• distance calculates the distance of two iterators
• advance can be used to advance the iterator by x elements. This is extremely useful for example, if you want to access the nth element of a list<>. (Although this may indicate that you should use an other container...)

Example:

  typedef list<int> MyList;
  MyList myList;
  myList.push_back(5);
  myList.push_back(1);
  myList.push_back(7);
  myList.push_back(9);
  myList.push_back(3);

  // print the 3rd element from the end
  MyList::const_iterator iter = myList.end();
  advance(iter, -3);
  if(myList.end() != iter)
      cout << *iter << endl; // prints "7"

Answer 20

std::vector can be used to create a dynamically sized buffer on the stack.

Like in this example (which shows how to convert a std::string into a std::wstring)

#include <vector>
#include <locale>
#include <string>
using namespace std;

string narrowStr("narrow");
wstring wideStr;
locale loc("german");

vector<wchar_t> wBuffer( narrowStr.length() );  // = wchar_t[narrowStr.length()]

use_facet<ctype<wchar_t> >(loc)._Widen_s( 
    narrowStr.c_str(),                       
    narrowStr.c_str() + narrowStr.length(),
    &wBuffer[0],
    wBuffer.size()
);
wideStr = wstring( &wBuffer[0], wBuffer.size() );

Answer 21

size() on a list is O(N) on some platforms. Use empty() if you can, it should be O(1).

Answer 22

One thing that surprised me in the last year was discovering the block allocation size for the deque class. It's obviously implementation-specific, but I believe the default Visual Studio size is 128 bytes, with a minimum of one object. You should track down the value your deque implementation uses.

The reason this can matter: If you create a deque with a lot of objects, it may internally make a ton of calls to new/delete, enough so that performance suffers. It is easy enough to create a modified deque class with a different block size, although the tradeoff is that it will waste more space.

Answer 23

Differences between std::sort (which many people use anytime they need sorting done) and std::stable_sort. Ostensibly, the primary difference is that stable_sort guarantees that elements that compare equal remain in their original order. In reality, there's another important difference: stable_sort also gives guarantees on worst-case performance that sort does not -- stable_sort is never worse than O(N lg N) complexity. sort gives no explicit guarantee on worst case performance, though it would certainly be surprising it it were worse than O(N^2).

This lack of a guarantee was chosen to allow std::sort to be implemented as a Quicksort, which has extremely good average performance, but can have O(N^2) complexity in a few pathological cases. Most recent implementations of std::sort, however, are implemented with the Introsort algorithm. Introsort starts out as basically a Quicksort, but keeps track of its recursion depth. When/if the recursion depth exceeds a chosen constant (indicating that it may be encountering a pathological case), it switches to using another sort algorithm instead.

Tracking the recursion depth adds minuscule overhead, giving an equally minuscule speed loss, but ensures that complexity remains roughly O(N lg N) even in the worst case.

Answer 24

Keyword mutable.

Sometimes you need to change a member variable inside a const member function. Usually, this happens when you want to do lazy initialization of a value on first access. Consider example:

struct File {
   explicit File(const std::string& name) : name_(name), size_(-1ul) {...}

   // The member is declared to be const because logically taking size of an object
   // doesn't modify it's state. We could calculate the size in constructor as well, 
   // but that would be waste of time in cases when application doesn't want to get
   // size of constructed File object.
   unsigned long size() const {
      if (size_ == -1ul) {
          size_ = /* use some API call to calculate size of the file */;
      }
      return size_;
   }
private:
   std::string name_;
   ...
   mutable unsigned long size_; // Using mutable keyword here !!!
};

This is very simplified example that came first to my mind, but it allows to grasp the idea. Sometimes contract requires a method to be const, but internal implementation due to some reasons needs to modify state of the object, in this case mutable is your friend.

Answer 25

when a temporary is assigned to a const reference inside a {} block, it's lifetime is extended to the lifetime of a reference.That made ScopeGuard possible. ScopeGuard FTW

Answer 26

Sometimes when programming algorithms on sequences (with iterators), you can write a more efficient algorithm if the iterators are random access (std::vector, std::dequeue) as apposed to sequential (std::list, std::map). Instead of going with the most general form, you can use a technique called tag dispatching to decide at compile time which version can be used.

struct random_access_iterator_tag {}; // Defined in the standard.
struct bidirectional_iterator_tag {};

template< class Iterator, class Distance >
Iterator advance( Iterator it, Distance d, random_access_iterator_tag )
{
    return it + d; // Would be illegal for bidirectional iterators.
}

template< class Iterator, class Distance >
Iterator advance( Iterator it, Distance d, bidirectional_iterator_tag )
{
    // This would all be unnecessary with random access iterators.
    while( d > 0 ) {
        it++; d--;
    }
    while( d < 0 ) {
        it--; d++;
    }
    return it;
}

template< class Iterator, class Distance >
Iterator advance( Iterator it, Distance d )
{
    // Use iterator traits to find out what category an iterator is. 
    typename iterator_traits<Iterator>::iterator_category category;
    advance( it, d, category ); // No instance of category is created.
}

It's also worth noting that if you write your own iterator class, you should have it inherit from std::iterator so iterator_traits is done for you and you can call functions like this with no trouble. Otherwise, specializing iterator_traits is not a bad idea.

Answer 27

I like the little-known operator "-->", also know as "goes to."

Here's an example:

#include <stdio.h>
int main()
{
     int x = 10;
     while( x-->0 ) // x goes to 0
     {
       printf("%d ", x);
     }

}

Answer 28

You can often use a std::vector instead of new'ing or malloc'ing an array dynamically. If you need pass a pointer to the array around, use the address to the first element in the vector (&v[0]). This makes code easier to write, easier to read and safer. What's not to like? Consider:

const int len = computeLength( inputData );
char *convertedData = new char[ len ];
if ( !checkDataForValidity( convertedData ) ) {
    delete [] convertedData;
    return false;
}
processData( convertedData );
delete [] convertedData;
return true;

vs.

const int len = computeLength( inputData );
vector<char> buf( len );
if ( !checkDataForValidity( &convertedData[0] ) )
    return false;
processData( &convertedData[0] );
return true;

The second variant using std::vector needs less code, releases the acquired memory automatically (even if exceptions are thrown), and it auto-initializes the array to zero automatically.

Answer 29

When you want to clone a container of object that are polymorphic, and that exposes a Clone() methode, here is how a procede :

std::transform(e.begin(), e.end(), std::back_inserter(exp_), std::mem_fun(&PolymorficObj::Clone));

where e is the source container of polymorphic items and exp_ is the dest of cloned object.

Answer 30

Using std::auto_ptr for pimpl design pattern: Just assume a simple class which uses pimpl mechanism to hide its implementation. The pointer to impl is implemented by std::auto_ptr which will ensure to delete implementation after it is no longer to be needed.

The header file looks like this:

#include <memory>

class SomeClass
{
 struct Impl;
 std::auto_ptr<Impl> pimpl;
public:
 SomeClass();
 void someFunction();
};

The source file:

#include "SomeClass.h"
#include <iostream>

struct SomeClass::Impl
{
 ~Impl()
 {
    std::cout << "destructed";
 }
};

SomeClass::SomeClass()
: pimpl(new Impl())
{}

void SomeClass::someFunction()
{}

However, if we would like to use this class, g++ won't compile it. At least, we get the error message:

memory:259: note: neither the destructor nor the class-specific operator delete will be called, even if they are declared when the class is defined.

The main problem is that the compiler is unable the generate the ~SomeClass destruction. Because we do not provide it, the compiler-generated default destruction will be used. In this case the deletion of pimpl provided by the auto_ptr destructor. Because only the forward declaration of Impl is present in the header file, the compiler won't be able to generate the destruction. The solution is to add an empty destructor of SomeClass. In this case, the compiler does not have to generate it. Just let the body of destruction empty, the pimpl's destructor will be called, and that point (compiling SomeClass.cpp) the Impl is known.

And how is it connection with STL? If we use e.g. boost's shared_ptr instead of auto_ptr, this error will not occur, because the shared_ptr has its own structure for deletion.