C9 Lectures: Stephan T. Lavavej - Standard Template Library (STL), 3 of n

Let's see if I can post a 5 KB comment.

 

Here's the solution that I presented, slightly modified (I renamed a template parameter), and with test cases:

C:\Temp>type meow.cpp
#include <algorithm>
#include <deque>
#include <forward_list>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <vector>

namespace meow {
    namespace detail {
        struct vectorlike_tag { };
        struct listlike_tag { };
        struct associative_tag { };

        template <typename C> struct container_traits;

        template <typename T, typename A>
            struct container_traits<std::vector<T, A>> {
            typedef vectorlike_tag category;
        };

        template <typename T, typename A>
            struct container_traits<std::deque<T, A>> {
            typedef vectorlike_tag category;
        };

        template <typename T, typename A>
            struct container_traits<std::list<T, A>> {
            typedef listlike_tag category;
        };

        template <typename T, typename A>
            struct container_traits<std::forward_list<T, A>> {
            typedef listlike_tag category;
        };

        template <typename T, typename C, typename A>
            struct container_traits<std::set<T, C, A>> {
            typedef associative_tag category;
        };

        template <typename T, typename C, typename A>
            struct container_traits<std::multiset<T, C, A>> {
            typedef associative_tag category;
        };

        template <typename T, typename C, typename A>
            struct container_traits<std::unordered_set<T, C, A>> {
            typedef associative_tag category;
        };

        template <typename T, typename C, typename A>
            struct container_traits<std::unordered_multiset<T, C, A>> {
            typedef associative_tag category;
        };

        template <typename K, typename V, typename C, typename A>
            struct container_traits<std::map<K, V, C, A>> {
            typedef associative_tag category;
        };

        template <typename K, typename V, typename C, typename A>
            struct container_traits<std::multimap<K, V, C, A>> {
            typedef associative_tag category;
        };

        template <typename K, typename V, typename C, typename A>
            struct container_traits<std::unordered_map<K, V, C, A>> {
            typedef associative_tag category;
        };

        template <typename K, typename V, typename C, typename A>
            struct container_traits<std::unordered_multimap<K, V, C, A>> {
            typedef associative_tag category;
        };

        template <typename Container, typename X>
            void erase_helper(Container& c, const X& x, vectorlike_tag) {

            c.erase(std::remove(c.begin(), c.end(), x), c.end());
        }

        template <typename Container, typename Predicate>
            void erase_if_helper(Container& c, Predicate p, vectorlike_tag) {

            c.erase(std::remove_if(c.begin(), c.end(), p), c.end());
        }

        template <typename Container, typename X>
            void erase_helper(Container& c, const X& x, listlike_tag) {

            c.remove(x);
        }

        template <typename Container, typename Predicate>
            void erase_if_helper(Container& c, Predicate p, listlike_tag) {

            c.remove_if(p);
        }

        template <typename Container, typename X>
            void erase_helper(Container& c, const X& x, associative_tag) {

            c.erase(x);
        }

        template <typename Container, typename Predicate>
            void erase_if_helper(Container& c, Predicate p, associative_tag) {

            for (auto i = c.begin(); i != c.end(); ) {
                if (p(*i)) {
                    c.erase(i++);
                } else {
                    ++i;
                }
            }
        }
    }

    template <typename Container, typename X> void erase(Container& c, const X& x) {
        detail::erase_helper(c, x, typename detail::container_traits<Container>::category());
    }

    template <typename Container, typename Predicate> void erase_if(Container& c, Predicate p) {
        detail::erase_if_helper(c, p, typename detail::container_traits<Container>::category());
    }
}

#include <iostream>
#include <numeric>
#include <ostream>
using namespace std;
using namespace meow;

template <typename Container> void print(const Container& c) {
    for (auto i = c.begin(); i != c.end(); ++i) {
        cout << *i << " ";
    }

    cout << endl;
}

int main() {
    vector<int> v(7);

    iota(v.begin(), v.end(), 1);
    print(v);
    for_each(v.begin(), v.end(), [](int& n) { n *= 11; });
    print(v);

    cout << "--" << endl;

    list<int> l(v.begin(), v.end());
    set<int> s(v.begin(), v.end());

    erase(v, 44);
    print(v);
    erase_if(v, [](int n) { return n % 2 == 0; });
    print(v);

    cout << "--" << endl;

    erase(l, 33);
    print(l);
    erase_if(l, [](int n) { return n % 2 != 0; });
    print(l);

    cout << "--" << endl;

    erase(s, 22);
    print(s);
    erase_if(s, [](int n) { return n > 40 && n < 70; });
    print(s);
}

C:\Temp>cl /EHsc /nologo /W4 meow.cpp
meow.cpp

C:\Temp>meow
1 2 3 4 5 6 7
11 22 33 44 55 66 77
--
11 22 33 55 66 77
11 33 55 77
--
11 22 44 55 66 77
22 44 66
--
11 33 44 55 66 77
11 33 77

[Tominator2005]
> One interest of mine is Graphs. This will definatly make programming in C++ sooo much easier.

Check out the Boost Graph Library: http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/table_of_contents.html

There's a whole book about it too.

[PhrostByte]
> STL, I'm curious if you know why unique_ptr has array new/delete support but shared_ptr doesn't?

I'm not exactly sure. (I'm on the Standardization Committee's mailing lists, but I haven't attended their meetings.) There was some discussion of defining shared_ptr<T[]>, but it appeared to have been rejected as too controversial with insufficient implementation experience. The strongest argument against it was that specializations should behave like the primary template (vector<bool> being an obvious offender), but shared_ptr<T[]> would actually be significantly different (it would have to prohibit derived-to-base conversions, for example). Given that, it should be differently named instead of being a specialization. boost::shared_array exists, but was not incorporated into TR1/C++0x.

The biggest mystery to me is actually why unique_ptr<T[]> was retained, given the controversy with shared_ptr. There could be a rationale there, or it could be an oversight. (If there's a rationale, I'd guess that it's because unique_ptr is zero overhead, so providing an array form could be useful to someone who needs a dynamically allocated array with a runtime length (std::array has a compiletime length), needs exception safety (owning raw pointers lead to leaktrocity), and doesn't need the flexibility and doesn't want to pay the minor costs of std::vector (which is at least as large as three pointers). On the other hand, shared_ptr has overhead (minor, but nonzero). It is difficult for me to imagine a scenario in which shared_ptr<vector<T>> is unacceptable, but shared_array would be acceptable.)

> And a slight correction: having the same initialism is fun, but shared_ptr etc. were not added to SGI's Standard Template Library, but to the C++ Standard Library.

Like most people, I use "STL" to refer to "the parts of the C++ Standard Library that were derived from or strongly influenced by Stepanov's original work". This usage doesn't lead to confusion. In that interpretation, shared_ptr is very clearly part of the STL, while iostreams are not (and for std::string, flip a coin).

[Sys64738]
> And comparing the ref-counted deterministic resource management
> offered by shared_ptr vs. garbage-collector systems, are the
> performance of ref-counted systems better than those offered by GC?

There's a major difference between universal refcounting and shared_ptr's refcounting. The vast majority of resources in a C++ program won't be managed by refcounting. For example, vector maintains no reference count. Its destructor simply deallocates its memory (and any owned by its elements, recursively). Thanks to C++'s deterministic destruction, the compiler knows when to destroy vectors on the stack. A local vector's lifetime is known at compiletime, so tracking it is O(0). shared_ptr uses reference counting to track the lifetimes of dynamically allocated objects, but it's certainly not the case that everything in a C++ program is held by shared_ptr.

The other major difference between C++'s resource management system and GC is that C++'s system is resource-agnostic, while GC isn't. C++ destructors don't care what they're destroying, and can be used to manage memory, files, sockets, locks, textures, fonts, HWNDs, whatever equally. They don't care whether they're being invoked for local objects or dynamically allocated objects (vector elements, shared_ptr-owned objects, etc.) either. In contrast, non-deterministic GC handles memory much better than non-memory resources. *Usually*, nobody will notice if you hang onto memory for longer than absolutely necessary. Hanging onto non-memory resources for longer than necessary is a big deal, though. Keeping a file open, holding onto a texture (in video memory!), etc. could have observable and undesirable effects. (And "finalizers" are an incomprehensible nightmare.)

> And, as a side question: does it exist a tracing garbage collector for C++?

As I'm strongly opposed to universal GC, I'm about the furthest thing from an expert here, but the http://en.wikipedia.org/wiki/Boehm_garbage_collector is well known.

> and don't pay too much attention to memory allocation, cleanup, cycles, etc.

One of the goals of my videos is to demonstrate that C++ (uniquely!) can be used to write code that doesn't concern itself with the details of resource management, without falling into the tar pit that is universal GC. In fact, in Part 3 I drew big NO signs around new/delete and new[]/delete[].

> I would have used simple C++ overload... but the template metaprogramming technique presented by STL is very cool!

As I mentioned, I was concerned that the template metaprogramming here consumed more effort than it saved, but I figured I'd demonstrate it anyways. (The N=2 of vector/deque and list/forward_list is really the worst case for simplifying code. When N=lots, as with (unordered_)?(multi)?(map|set), the savings are clearer.)

> May some other lesson be dedicated to the template metaprogramming subject?

Template metaprogramming is relatively advanced, but I might use it in future installments.

(In an "Inside the STL" series, template metaprogramming would feature prominently, as it powers most of our ingenious tricks.)

PhrostByte: Yes, my reaction is very much "if you want .NET, you know where to find it".

There aren't any container traits. Perhaps you're thinking of std::iterator_traits. In this case, iterator traits are not applicable, because both std::list and std::set have bidirectional iterators, but they have different erasure patterns.

(Nice Dopefish avatar!)

About Part 3's homework problem: my Nurikabe solver currently solves Wikipedia's "moderately difficult" 10x9 example in 128 ms (on my Q9450). See if you can do better!

That's equivalent, but it's basically the same amount of code.  (When there are two equivalent ways of saying something, I'll usually choose the shorter one.)  I actually used to use static member functions of explicitly/partially specialized classes before I began maintaining the STL, where Dinkumware's convention is to use overload resolution.  If you like using specializations, go for it!

 

Note that because the helpers will be inlined, the compiler will easily be able to optimize out nameless empty arguments.  It's okay to assume a basic level of competency on the optimizer's part.

I just finished filming Parts 4 and 5! They'll be making their way to you soon.

 

geeyef: When you dllexport T, the compiler has to generate its copy constructor and copy assignment operator immediately, because whoever's linking against your DLL might want to copy construct or copy assign T.  This is different from how C++ ordinarily works, where the copy constructor and copy assignment operator will only be generated when you attempt to use them for the first time.

 

vector<unique_ptr<int>> isn't copy constructible or copy assignable, because that would require copying its elements, which are non-copyable (but movable).  Therefore, compilation fails.  The compiler errors are saying this, but as usual they're hard to understand if you're not an expert (and the compiler doesn't talk about the ultimate reason involving dllexport).

 

When you add a unique_ptr<int> data member, its copy ctor/copy assign are private and unimplemented.  The compiler sees that they're private, and does not attempt to generate T's copy ctor/copy assign.  vector<stuff> has a public copy ctor/copy assign, so when it's the only data member, the compiler behaves differently (it's only when it tries to instantiate the copy ctor/copy assign that compilation explodes).

 

With vector<unique_ptr<int>> as the only data member, you can add this to make it compile:

 

private:
    T(const T&);
    T& operator=(const T&);
};

That will prevent the compiler from attempting to generate a copy ctor/copy assign which will explode.

 

C4251 is essentially ignorable here.  You should be aware that using the STL in your DLL's interface (as opposed to just its implementation) forces you to play by the STL's rules - in particular, mixing major versions is forbidden.  You can't compile such a DLL with VC10 and have somebody compiling with VC9 or VC11 link against it, because the STL intentionally breaks binary compatibility between major versions.