STL set operations

There are some useful algorithms that run on two sets of values

• set_union
• set_intersection
• set_difference
• set_symmetric_difference

These operations are very useful, but their names are a bit confusing.
Here's a graphical interpretation of how they work, and it is how I remember them:

Exploring ways to express an algorithm

Suppose you want to rewrite the following loop

  
struct Shape {
    int rgb_color() const;
};

map<int, Shape*> id_to_shape;
vector<int> bright_colors;


for( map<int, Shape*>::iterator it=id_to_shape.begin(); it != id_to_shape.end(); ++it )
{
    int color = it->second->rgb_color();
    if (color_is_bright (color))
        v.push_back(bright_colors);
}
  

Here follows a tour in ways that this loop could be expressed.

Moving from legacy data structures to STL containers

When one is introduced to the STL containers there is a temptation to switch from the non-homogeneous legacy C-based data structures to the more smooth and standard containers. The existing code cannot magically turn all Trees to std::maps, DynamicArrays to std::vectors, LinkedLists to std::lists, so old code will probably still use old data structures.

So, a question arises:

• I have C and C++ functions that take Tree*, DynamicArray*, etc as arguments. Isn't it going to be awkward to introduce functions that now take vector, map, deque as well ?
• Do I have to make a version of the function for each data type ?

How to design API headers

Library headers (API) should be minimal and not change very often. If this directive is followed, then the API is more direct, and any internal changes do not reflect to recompiling the whole user project.

The following article describes what steps to take to achieve this goal on an C++ API header.

How does std::unordered_set compare to std::set ?

What are the differences between std::set and std::unordered_set ?

Here is a graphical and quantitative explanation of 

• how unordered_set works, 
• how fast it can access data, 
• how much memory it occypies, and 
• how it compares to std::set.

Forward declarations vs includes in headers

What should be included and what can be forward declared in this header ?

class Polygon : public Shape {

public:
    void setBasicCurve (const Bezier& curve);
    void magnify (Vector direction);
    void setPoints (const vector<Point*>& points);

private:
    Plane*             m_surface;
    std::list<Point*>  m_points;
    Color              m_color;
    Bezier&            m_basic_curve;

    static Type        m_shape_type;

};

Here are some practical tips to keep your header files lean.

Using a std::unordered_set

It's easy to use an unordered_set, or unordered_map with a basic key type, like int, float, string.
You simply set it up like

     std::unordered_set<string> simple_hash_table;  

But how does one create hash functors and compare functors for a more complex key?

How to pass ownership of C objects to STL containers

Mixing C code with C++ code

I have a number of C entities (say Nodes), which I want to store to a std::vector temporarily.

The C interface I have to manipulate these nodes consists of:

• Node *newNode();             constructs such nodes
• void  freeNode(Node *);      frees such nodes

Can I use the RAII technique, so that they are properly freed when the vector goes out of scope?

How is std::deque implemented ?

Deque is sometimes thought of as an dynamic array that is comprised of linked arrays.

typical deque layout

Such a structure could lead to extremely fast insert and remove operations.

Exactly what performance should one expect from a std::deque implementation though?

Generic C-Trees and C++ std::maps

How many lines of code do I need, to set up a typical tree structure? What are the pros and cons between a C-style generic tree and an std::map or an std::set ?