C++

Forum

 
Code review for: Empty Base Optimization pair (similar to boost::compressed_pair)

Catfish666 (666)
I have tried to implement a much simplified version of boost::compressed_pair.

What follows is a partially specialized EBO_pair<T1, T2> class template, written in C++11.
The first type T1 is constrained to not be empty.
The second type T2 may or may not be empty.

I would greatly appreciate a code review, thank you.

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
 
#pragma once

#include <memory>
#include <type_traits>
#include <utility>

namespace dsa
{

template <typename, typename, typename = void, typename = void>
class EBO_pair;

template <
    typename Member,
    typename Base
    >
class EBO_pair <
    Member,
    Base,
    typename std::enable_if<!std::is_empty<Member>::value>::type,
    typename std::enable_if<std::is_empty<Base>::value>::type
    >:
    public Base
{
private:

    Member m;

public:

    using first_reference           = Member &;
    using first_const_reference     = const Member &;
    using second_reference          = Base &;
    using second_const_reference    = const Base &;

    explicit EBO_pair(const Member &m = Member(), const Base &b = Base()):
        Base(b),
        m(m)
    {
    }

    EBO_pair(const EBO_pair &)                  = default;
    EBO_pair(EBO_pair &&)                       = default;
    EBO_pair & operator = (const EBO_pair &)    = default;
    EBO_pair & operator = (EBO_pair &&)         = default;

    ///
    /// @note Unqualified call to `swap()` for ADL (Argument Dependent Lookup).
    ///
    void swap(EBO_pair &other)
    {
        if (this != std::addressof(other))
            swap(m, other.m);
    }

    first_reference first()
    {
        return m;
    }

    first_const_reference first() const
    {
        return m;
    }

    second_reference second()
    {
        return *this;
    }

    second_const_reference second() const
    {
        return *this;
    }
};

template <
    typename First,
    typename Second
    >
class EBO_pair <
    First,
    Second,
    typename std::enable_if<!std::is_empty<First>::value>::type,
    typename std::enable_if<!std::is_empty<Second>::value>::type
    >
{
private:

    First   f;
    Second  s;

public:

    using first_reference           = First &;
    using first_const_reference     = const First &;
    using second_reference          = Second &;
    using second_const_reference    = const Second &;

    explicit EBO_pair(const First &f = First(), const Second &s = Second()):
        f(f),
        s(s)
    {
    }

    EBO_pair(const EBO_pair &)                  = default;
    EBO_pair(EBO_pair &&)                       = default;
    EBO_pair & operator = (const EBO_pair &)    = default;
    EBO_pair & operator = (EBO_pair &&)         = default;

    ///
    /// @note Unqualified call to `swap()` for ADL (Argument Dependent Lookup).
    ///
    void swap(EBO_pair &other)
    {
        if (this != std::addressof(other))
        {
            swap(f, other.f);
            swap(s, other.s);
        }
    }

    first_reference first()
    {
        return f;
    }

    first_const_reference first() const
    {
        return f;
    }

    second_reference second()
    {
        return s;
    }

    second_const_reference second() const
    {
        return s;
    }
};

template <typename EboPair>
void swap(EboPair &a, EboPair &b)
{
    a.swap(b);
}

} // namespace dsa


Edit: added non-member swap() function template.
Last edited on
JLBorges (13770)
This optimisation is already there for std::tuple<>

Note: The optimisation is not there in std::pair<> because members can be accessed using member variables first, second (std::tuple<> elements are accessed using std::get<N>())

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
#include <iostream>
#include <tuple>

int main()
{
    struct empty {};

    std::cout << '\n' ;
    
    std::cout << "sizeof( std::pair<empty,int> ): " << sizeof( std::pair<empty,int> ) << '\n' ;
    std::cout << "sizeof( std::pair<int,empty> ): " << sizeof( std::pair<int,empty> ) << '\n' ;

    std::cout << '\n' ;

    std::cout << "sizeof( std::tuple<empty,int> ): " << sizeof( std::tuple<empty,int> ) << '\n' ;
    std::cout << "sizeof( std::tuple<int,empty> ): " << sizeof( std::tuple<int,empty> ) << '\n' ;
    
    std::cout << '\n' ;
}

echo clang++ && clang++ -std=c++11 -stdlib=libc++ -O2 -Wall -Wextra -pedantic-errors main.cpp -lsupc++ && ./a.out
echo g++ && g++-4.8 -std=c++11 -O2 -Wall -Wextra -pedantic-errors main.cpp && ./a.out
clang++

sizeof( std::pair<empty,int> ): 8
sizeof( std::pair<int,empty> ): 8

sizeof( std::tuple<empty,int> ): 4
sizeof( std::tuple<int,empty> ): 4

g++

sizeof( std::pair<empty,int> ): 8
sizeof( std::pair<int,empty> ): 8

sizeof( std::tuple<empty,int> ): 4
sizeof( std::tuple<int,empty> ): 4

http://coliru.stacked-crooked.com/a/1351eb1d4fa34521
Catfish666 (666)
Thanks JLBorges.

This would mean that code such as below would work correctly with the second element being a stateless allocator?

std::get<1>(/* ... */).allocate(/* ... */);
JLBorges (13770)
Yes.
Catfish666 (666)
@ JLBorges: for your information, building your original code with Visual Studio 2013 Express does not apply the optimization:

sizeof( std::pair<empty,int> ): 8
sizeof( std::pair<int,empty> ): 8

sizeof( std::tuple<empty,int> ): 8
sizeof( std::tuple<int,empty> ): 8

Press any key to continue . . .

JLBorges (13770)
> Visual Studio 2013 Express does not apply the optimization

Yes, there is always a quality of implementation issue. (The optimisation is permitted, but not mandated).
Catfish666 (666)
I thank you for your contribution to the thread, JLBorges.

However I now feel that I should reiterate my original request: that members verify my EBO_pair code for bugs, bad practices, etc.

The reasons are:

1) If I write about EBO in my article then I should demonstrate it somehow in the code.
std::tuple would have been great, however if EBO is not mandated for it, readers could rightly ask "why use std::tuple for two elements instead of std::pair when there are no guaranteed benefits?"

2) I do not want to use boost::compressed_pair. I would like my code to be self-sufficient, pure C++11. In any case, I rather not bundle third party libraries with it.
LB (13399)
Could you explain in your code how you expect EBO to be enforced? From what I can tell at a glance, it just looks like you're hoping that the compiler will use EBO.
Catfish666 (666)
EBO has been around for many years now.
I think it is safe to assume that it will be applied by a C++11 compliant compiler, if one derives from an empty base class.
LB (13399)
After seeing the above post, this post confuses me:
http://www.cplusplus.com/forum/general/128717/#msg695620
JLBorges (13770)
Something like this, perhaps:

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
 
#include <utility>
#include <tuple>
#include <type_traits>

namespace dsa
{
    namespace detail
    {
        struct empty {};
        using tuple_type = std::tuple<int,empty> ;

        constexpr bool use_tuple = sizeof(tuple_type) == sizeof(int) ;

        struct integer : empty { int m ; } ;

        constexpr bool use_home_grown_ebo = !use_tuple &&
                                            ( sizeof(integer) == sizeof(int) ) ;
    }

    template < typename FIRST, typename SECOND, typename = void >
    struct pair : std::pair<FIRST,SECOND>
    {
        using base = std::pair<FIRST,SECOND> ;

        using first_type = typename base::first_type ;
        using second_type = typename base::second_type ;

        using base::base ;
        using base::operator= ;
        using base::swap ;

        first_type& first() { return base::first ; }
        const first_type& first() const { return base::first ; }
        second_type& second() { return base::second ; }
        const second_type& second() const { return base::second ; }
    };

    template < typename FIRST, typename SECOND >
    struct pair< FIRST, SECOND,
                 std::enable_if< detail::use_tuple >::type > : std::tuple<FIRST,SECOND>
    {
        using base = std::tuple<FIRST,SECOND> ;

        using first_type = typename std::pair<FIRST,SECOND>::first_type ;
        using second_type = typename std::pair<FIRST,SECOND>::second_type ;

        using base::base ;
        using base::operator= ;
        using base::swap ;

        first_type& first() { return std::get<0>(*this) ; }
        const first_type& first() const { return std::get<0>(*this) ; }
        second_type& second() { return std::get<1>(*this) ; }
        const second_type& second() const { return std::get<1>(*this) ; }
    };

    template < typename FIRST, typename SECOND >
    struct pair< FIRST, SECOND,
                 typename std::enable_if< detail::use_home_grown_ebo &&
                                          std::is_empty<SECOND>::value >::type >
                  : SECOND
    {
        FIRST m ;

        // typedefs

        // constructors, templated constructors

        // operator=, templated operator=s

        // operator pair<A,B>, templated operator pair<A,B>

        // first(), second()

        // swap

        // whatever else
    };
}
Topic archived. No new replies allowed.