Ranges selection algorithm template for C++.

Posted on by
Reply

Rationale

Consider we have some data sequence (vector-like), for example: [2, 1, 3, 4, 5, 0, 0, 1]. Second, we have some predicate, which can be applied to sequence element, for example: bool f(int a) { return a < 3; }. So we wish get all ranges (indexes pairs) which elements satisfy defined predicate.
For given example we have following pairs: {0, 3}; {5,8}.

Note: Pairs describes range in STL manner: [a, b).

Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<typename It1, typename It2, typename Pred1>
void getRangesIf (It1 first, It1 last, It2 dst_first, Pred1 f)
{
    for (auto it = first, jt = first; it != last;) {
        it = std::find_if (it, last, f);
        jt = std::find_if_not (it, last, f);

        if (it != jt) {
            const auto fst_ind = std::distance (first, it);
            const auto snd_ind = std::distance (first, jt);

            *dst_first++ = std::make_pair (fst_ind, snd_ind);
        }

        std::swap (it, jt);
    }
}

Notes

Algorithm written for C++11 environment and can be ported to C++03, but who cares ? :)

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <sstream>
#include <algorithm>
#include <iterator>
#include <vector>

typedef std::pair<size_t , size_t> RangePair;
typedef std::vector<rangepair> RangeVec;

template<typename It1, typename It2, typename Pred1>
void getRangesIf (It1 first, It1 last, It2 dst_first, Pred1 f)
{
    for (auto it = first, jt = first; it != last;) {
        it = std::find_if (it, last, f);
        jt = std::find_if_not (it, last, f);

        if (it != jt) {
            const auto fst_ind = std::distance (first, it);
            const auto snd_ind = std::distance (first, jt);

            *dst_first++ = std::make_pair (fst_ind, snd_ind);
        }

        std::swap (it, jt);
    }
}

const size_t kVecSz = 1024;

int main()
{
    std::vector<int> some_vec (kVecSz);
    std::generate (std::begin (some_vec), std::end (some_vec), rand);

    RangeVec ranges;
    getRangesIf (std::begin (some_vec), std::end (some_vec),
    std::back_inserter<decltype (ranges) > (ranges), [] (int elem) { return elem < (RAND_MAX / 2); });

    std::cout << "Less than (RAND_MAX/2) ranges: \n";

    std::for_each(std::begin(ranges), std::end(ranges), [](RangePair p) {
        std::cout << "[" << p.first << ", " << p.second << "]\n";
    });

    std::cin.get();
}

Possible output

 

C++11: Smart pointers with lambda deleters

Posted on by
Reply

     Current C++11 ISO Standard supports new three types of smart-pointers: shared_ptr, weak_ptr, unique_ptr. First two used in pair for reference counter memory manager (primitive garbage collector). Latter provided to replace old ugly auto_ptr. auto_ptr has very specific copy-constructor which steals ownership by passing non-const reference to another object. See code example below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <memory>

typedef std::auto_ptr<int> IntAutoPtr;

int main() {
    IntAutoPtr p1(new int); // allocating new object
    *p1 = 1; // set some value
    IntAutoPtr p2(p1); // _steal_ (not copy!) pointer from p1
    std::cout << "p1 addr " << p1.get() << std::endl; // nullptr!
    std::cout << "p2 addr " << p2.get() << std::endl; // normal memory addr

    std::cin.get();
}

     We consider destruction of smart pointers, more precisely, memory freeing. Only weak_pointer doesn’t have ability to destroy referenced object, because this smart pointer provided for addressing cyclic dependencies issues with shared_ptr. Default C++ memory management based on using operators new and delete, so default versions of smart pointers also destroys memory block by calling delete.

     Unfortunately, we have some ad-hoc cases for memory management. First of all, imagine we have dynamic array instead single object. Thus we should use operator new with brackets: new[size_t sz] which have correspond delete with brackets: delete[]. Standard says that unique_ptr must provide partial specialization for type T[] which uses delete with brackets in its destructor, but there is no such requirement for shared_ptr.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <memory>

typedef std::unique_ptr<int> IntUniqPtr; // Default unique_ptr.
typedef std::unique_ptr<int[]> IntArrUniqPtr; // Specialization with operator[] and deleter with delete[] invocation.

int main() {
    IntUniqPtr p1(new int);
    *p1 = 1;

    //! p1[0] = 1;
    //! Compile-time error. Default unique_ptr template doesn't define operator[].

    IntArrUniqPtr p2(new int[3]);
    p2[0] = 1;

    IntArrUniqPtr p3(nullptr);

    p3 = std::move(p2);
    // p3 destroys current acquired memory block
    // than p3 steals p2 memory and p2 deleter. This code is consistent.

    //! IntUniqPtr p4(p1);
    //! Compile-time error. unique_ptr forbids copy-constructors and copy-assignments.

    IntUniqPtr p5(std::move(p1));

    std::cout << "p1 - " << p1.get() << std::endl; // nullptr
    std::cout << "p2 - " << p2.get() << std::endl; // nullptr
    std::cout << "p5 - " << p5.get() << std::endl; // normal memory block

    std::cin.get();
}

In more general case we can obtain memory by another unusual way (e.g. library/driver call) which can be destroyed properly by the same unusual way. We need ability to setup custom deleter in smart pointer. To accomplish this behavior unique_ptr provides second template parameter which refers to deleter type, defaulted to default_delete. Another way used in shared_ptr, where deleter defined in runtime, smart pointer type affected by it. See example below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <memory>

// Custom deleter type
struct verbose_deleter {
    void operator()(void * ptr) {
        std::cout << "Verbose deleter activated " << std::endl;
        delete ptr;
    }
};

typedef std::unique_ptr<int, verbose_deleter> CustomIntUniqPtr; // Deleter type in template definition
typedef std::shared_ptr<int> IntSharedPtr; // No information about deleter

int main() {
    {
        CustomIntUniqPtr p1(new int, verbose_deleter());
        // Pointer and deleter object

        IntSharedPtr p2(new int, verbose_deleter());
        // Deleter info obtained here, STL uses type-erasure concept for internal implementation.
    }

    std::cin.get();
}

Finally, we can use lambda-expression as deleter! That convenient way available in C++11. Lambda-expressions can be boxed into function objects. Visual Studio 10 (2010) contains decltype type specifier, but latter can’t be use with lambda. Visual Studio 11 (2012) allows this code:

1
2
3
4
5
6
7
8
9
10
11
12
#include <memory>
#include <functional>
#include <iostream>

auto deleter = [](void * p){ std::cout << "a"; };

int main() {
    {
        std::unique_ptr<int, decltype(deleter)> x(new int, deleter);
    }
    std::cin.get();
}

No more boilerplate code with function objects or/and bind invocations! Moreover, lambda-based deleters can use type inference with auto keyword. I used this technique in last example.