C++

Forum

 
std::unordered_set speed comparison with vector

Pages: 12
TheIdeasMan (6817)
For some reason this container is creating more buckets than elements that are in it :+( 


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
 
#include <iostream>
#include <iomanip>
#include <vector>
#include <random>
#include <algorithm>
#include <iterator>
#include <chrono>
#include <ctime>
#include <unordered_set>
#include <set>

//#include "helper.hpp"

template<typename ContainerType>
void FindAlgoTimer(ContainerType Container, std::size_t ValueToFind) {

    std::clock_t c_start = std::clock();
    auto result1 = std::find(std::begin(Container), std::end(Container), ValueToFind);
    std::clock_t c_end = std::clock();

    if (result1 != std::end(Container)) {; /* null statement */} //quiets unused variable warning


    std::cout << std::fixed << std::setprecision(6) << "CPU time used: "
              << 1000.0 * (c_end-c_start) / CLOCKS_PER_SEC << " ms\n";

}


int main()
{

    const std::size_t Size = 1000000;

    std::vector<std::size_t> RandVect(Size,0);

    for(std::size_t item = 0;item < RandVect.size(); ++item) {
        RandVect[item] = item;
    }

    std::random_device rd;
    std::mt19937 g(rd());

    std::shuffle(RandVect.begin(), RandVect.end(), g);
//    std::size_t ValueToFind = 300000;

        std::cout << "Random number " << g() % Size << "\n";

    // Create vector of values to test find with
    std::vector<std::size_t> TestValues(10);
    for (std::size_t a = 0; a < TestValues.size() ; ++a) {
        TestValues[a] = g() % Size;
    }

    std::cout << "Test values are \n";
    for (const auto& element : TestValues) {
        std::cout << element << "\n" ;
    }
//    std::cout << "Random number " << g() % Size << "\n";
    std::cout << "\n\n\nstd::vector\n";
    for (const auto& ValueToFind : TestValues ) {
        FindAlgoTimer<std::vector<std::size_t>>(RandVect, ValueToFind);
    }




     // use contents of RandVect to make unordered set
//     const std::size_t BucketCount = 1000;
//    std::unordered_set<std::size_t> RandSet(std::begin(RandVect),
//                                            std::end(RandVect)/*,
//                                            BucketCount*/);

    std::unordered_set<std::size_t> RandSet;
    RandSet.reserve(Size);
    RandSet.insert( std::begin(RandVect), std::end(RandVect) );


//    RandSet.rehash(BucketCount);
    std::cout << "\n\n\nstd::unordered_set\n";

    std::cout << "max size  " << RandSet.max_size() << "\n";
    std::cout << "size  " << RandSet.size() << "\n";
    std::cout << "bucket_count " << RandSet.bucket_count() << "\n";
    std::cout << "Load factor " << RandSet.load_factor() << "\n";
    std::cout << "Max Load factor " << RandSet.max_load_factor() << "\n";



//    FindAlgoTimer<std::unordered_set<std::size_t>>(RandSet, ValueToFind);

    for (const auto& ValueToFind : TestValues ) {
        FindAlgoTimer<std::unordered_set<std::size_t>>(RandSet, ValueToFind);
    }


// Make std:;set from RandVect

    std::set<std::size_t> MySet(std::begin(RandVect),
                                std::end(RandVect));

    // Test timing

    std::cout << "Test timing std::set \n";
    for (const auto& ValueToFind : TestValues ) {
        FindAlgoTimer<std::set<std::size_t>>(MySet, ValueToFind);
    }

    return 0;
}
Last edited on
TheIdeasMan (6817)
For some reason the code is not running on cpp.sh, here is the output from my IDE:

The other minor problem I have, is that literals of the form 1'000'000 aren't working - I do have c++14 with clang 3.8, gcc5.3.1

Random number 362043
Test values are 
981603
21447
81390
7212
901014
925691
975057
599908
691098
915834



std::vector
CPU time used: 0.000000 ms
CPU time used: 0.000000 ms
CPU time used: 0.001000 ms
CPU time used: 0.001000 ms
CPU time used: 0.000000 ms
CPU time used: 0.000000 ms
CPU time used: 0.001000 ms
CPU time used: 0.000000 ms
CPU time used: 0.001000 ms
CPU time used: 0.000000 ms



std::unordered_set
max size  1152921504606846975
size  1000000
bucket_count 1056323
Load factor 0.946680
Max Load factor 1.000000
CPU time used: 3.275000 ms
CPU time used: 0.720000 ms
CPU time used: 2.561000 ms
CPU time used: 0.065000 ms
CPU time used: 2.459000 ms
CPU time used: 2.323000 ms
CPU time used: 0.711000 ms
CPU time used: 2.831000 ms
CPU time used: 1.811000 ms
CPU time used: 0.983000 ms
Test timing std::set 
CPU time used: 26.807000 ms
CPU time used: 0.539000 ms
CPU time used: 2.583000 ms
CPU time used: 0.183000 ms
CPU time used: 26.665000 ms
CPU time used: 24.537000 ms
CPU time used: 28.095000 ms
CPU time used: 16.055000 ms
CPU time used: 19.860000 ms
CPU time used: 23.903000 ms

Peter87 (11235)
It seems like the bucket count is always a prime number. It probably has something to do with prime numbers reducing the risk of hash collisions.

The next prime after 1000000 is 1000003 so why doesn't it use that one instead of 1056323? I don't know.
Last edited on
ne555 (10692)
TheIdeasMan (6817)
Hi,

Thanks ne555 and Peter87 :+)

I think I must have a big misunderstanding on how the hash functions / buckets work :+( It seems the load_factor is not supposed to exceed 1.0, so that would mean that there will always be more buckets than elements, here I have about 5.6% more buckets than elements. Maybe that is to allow for a bit of expansion in the size of the container? I had the impression that there would be multiple elements per bucket, as in 1 million elements in 1000 buckets. And I thought the purpose of that was to greatly reduce the amount of searching because there are relatively few elements in each bucket. The hash function provides a value to determine which bucket an element is in. Is that right? How does having more buckets than elements make the container efficient?

Maybe the hash function works out an exact subscript for an array?

Also wondering why the unordered_set is about 2'500 times slower for a find than a vector? I mean the worst case scenario for vector is supposed to be O(n), isn't unordered_set supposed to be better than that? I know that trying to predict what is the average complexity is usually quite difficult.

cppreference wrote:
Unordered set is an associative container that contains a set of unique objects of type Key. Search, insertion, and removal have average constant-time complexity.

Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its value. This allows fast access to individual elements, since once a hash is computed, it refers to the exact bucket the element is placed into.

std::unordered_set meets the requirements of Container, AllocatorAwareContainer, UnorderedAssociativeContainer.



Btw, I have fixed the digit separator problem, I had a Community Edition QtCreator which wasn't doing it, the current version does :+)

Thanks in advance :+)
Last edited on
doug4 (1538)
Hey, @TIM,

I think you are confusing things a bit. You have an array of X objects of type size_t. There's no guarantee that hashing each of the elements in the array won't cause collisions if there are only X slots. You know that because of how you created the array. However, with arbitrary values, the only way to guarantee that you don't have collisions in a hash table of size_t elements is to have 2^sizeof(size_t) buckets.

On the flip side, if you only have 2 elements, it's ludicrous to have all of those buckets. So, the hash map (I'm guessing here, but I suspect I'm on the right path) starts with the number of elements you gave it. There were "too many" collisions, so it resized and rehashed the elements. So it's probably a function of the number of elements, the number of possible values, and the specific values stored in the map.
Peter87 (11235)
TheIdeasMan wrote:
Also wondering why the unordered_set is about 2'500 times slower for a find than a vector? I mean the worst case scenario for vector is supposed to be O(n), isn't unordered_set supposed to be better than that? I know that trying to predict what is the average complexity is usually quite difficult.

You are using std::find which will do a linear search. To take advantage of the hash table you need to use the find member function.

http://www.cplusplus.com/reference/unordered_set/unordered_set/find/
TheIdeasMan (6817)
@doug4

Ah, ok, so I gave it a go with my existing 1 million numbers in the range 1 to 1 trillion, so a comparison can be made to the previous results.

So the results seem to be still about 3'500 times slower than the vector, as compared to about 2'500 times before :+| The vector seems to always have 0.001ms or 0.000ms to find a value. And the std::set is much worse. Any clues as to why that is ? Did I do the timing correctly, or maybe the way the random numbers are being generated - would they cause any issues?

Test values are 
2378152212
2567041987
3441403981
2569341569
170878496
1954053340
1348074434
931938584
1617858511
1988811527



std::vector
CPU time used: 0.000000 ms
CPU time used: 0.001000 ms
CPU time used: 0.000000 ms
CPU time used: 0.000000 ms
CPU time used: 0.000000 ms
CPU time used: 0.001000 ms
CPU time used: 0.001000 ms
CPU time used: 0.000000 ms
CPU time used: 0.001000 ms
CPU time used: 0.000000 ms



std::unordered_set
max size  1152921504606846975
size  999884
bucket_count 1056323
Load factor 0.946570
Max Load factor 1.000000
CPU time used: 3.638000 ms
CPU time used: 4.009000 ms
CPU time used: 3.529000 ms
CPU time used: 3.467000 ms
CPU time used: 3.491000 ms
CPU time used: 3.416000 ms
CPU time used: 3.263000 ms
CPU time used: 3.357000 ms
CPU time used: 3.371000 ms
CPU time used: 3.451000 ms
Test timing std::set 
CPU time used: 28.653000 ms
CPU time used: 27.280000 ms
CPU time used: 31.278000 ms
CPU time used: 27.163000 ms
CPU time used: 29.629000 ms
CPU time used: 26.345000 ms
CPU time used: 28.941000 ms
CPU time used: 26.109000 ms
CPU time used: 28.429000 ms
CPU time used: 25.903000 ms

doug4 (1538)
Did you change the find function that you are using like @Peter87 mentioned? That's the biggie.
TheIdeasMan (6817)
Ah, I didn't see Peter87's post - and his advice worked like a charm :+) I now have comparable performance, about 0.001ms to 0.003ms for all 3 containers. But I guess this is getting down towards the limits of the clock, I probably should find more numbers and compare totals.

Thanks to everyone :+)

1
2
 
++SillyMistakes;
++ThingsLearnt;
htirwin (1208)
Did a quick test (compiled with -O3), and results were pretty much as expected. 

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
 
#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <string>
#include <unordered_set>

int main()
{ 
    std::string s;

    const int NUM_SEARCHES = 10;

    for( int numStrings = 100; numStrings < 1000000000; numStrings *= 10 )
    {
        const int MAX_VALUE = numStrings*3;

        std::vector< std::string > stringVec( numStrings );
        std::unordered_set< std::string > stringSet;

        for( int i = 0; i < numStrings; ++i ) 
        {
            stringVec[ i ] = std::to_string( std::rand() % numStrings * 2 );
            stringSet.insert( stringVec[ i ] );
        }

        std::clock_t c_start = std::clock();
        for( int i = 0; i < NUM_SEARCHES; ++i ) 
        {
            auto it = std::find( 
                stringVec.begin(), 
                stringVec.end(), 
                std::to_string( rand() % MAX_VALUE ) );
            
            if( it != std::end( stringVec ) )
            {
                s = *it;    
            }
        }
        int vecTime = std::clock() - c_start;

        c_start = std::clock();
        for( int i = 0; i < NUM_SEARCHES; ++i ) 
        {
            auto it = stringSet.find( std::to_string( rand() % MAX_VALUE )  );
            if( it != stringSet.end() )
            {
                s = *it;
            }
        }
        std::cout << "unordered_set was  " 
                  << vecTime / double( std::clock() - c_start ) 
                  << " times faster than vector with n=" 
                  << numStrings << "\n"; ;
    }
}


unordered_set was  3 times faster than vector with n=100
unordered_set was  21.6 times faster than vector with n=1000
unordered_set was  224 times faster than vector with n=10000
unordered_set was  1086.73 times faster than vector with n=100000
unordered_set was  6518.18 times faster than vector with n=1000000
unordered_set was  86467.7 times faster than vector with n=10000000
unordered_set was  655039 times faster than vector with n=100000000
Last edited on
JLBorges (13770)
Measure performance for the typical use case with the target implementation.
In many scenarios, overall, the vector (sorted, binary search) would be faster.

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
 
#include <iostream>
#include <ctime>
#include <random>
#include <unordered_set>
#include <vector>
#include <algorithm>

std::vector<std::size_t> make_test_data( std::size_t n )
{
    std::mt19937 rng( std::time(nullptr) ) ;
    std::vector<std::size_t> result(n) ;
    for( auto& v : result ) v = rng() ;
    return result ;
}

void insert( const std::vector<std::size_t>& srce, std::vector<std::size_t>& dest )
{
    dest = srce ;
    std::sort( std::begin(dest), std::end(dest) ) ;
}

void insert( const std::vector<std::size_t>& srce, std::unordered_set<std::size_t>& dest )
{
    dest = { std::begin(srce), std::end(srce) } ;
}

std::size_t find( const std::vector<std::size_t>& what, const std::vector<std::size_t>& vec )
{
    std::size_t n = 0 ;
    for( std::size_t v : what )
    {
        const auto iter = std::lower_bound( std::begin(vec), std::end(vec), v ) ;
        if( iter != std::end(vec) && *iter == v ) ++n ;
    }
    return n ;
}

std::size_t find( const std::vector<std::size_t>& what, const std::unordered_set<std::size_t>& set )
{
    std::size_t n = 0 ;
    for( std::size_t v : what ) if( set.find(v) != set.end() ) ++n ;
    return n ;
}

struct timer
{
    const std::clock_t start = std::clock() ;
    ~timer()
    {
        const auto end = std::clock() ;
        const auto ms = (end-start) * 1000.0 / CLOCKS_PER_SEC ;
        std::cout << ms << " msecs.\n" << std::flush ;
    }
};

int main()
{
    constexpr std::size_t n_values = 10'000'000 ;
    constexpr std::size_t n_searches = 1'000'000 ;
    
    std::cout << n_values << " values, " << n_searches << " searches\n\n" ;
    
    const auto data_set = make_test_data(n_values) ;
    const auto searched_values = make_test_data(n_searches) ;

    std::vector<std::size_t> vec ;
    std::unordered_set<std::size_t> set ;
    
    volatile std::size_t x = 0 ; 

    {
        std::cout << "vector: insert & sort - " ;
        timer t ;
        insert( data_set, vec ) ;
    }

    {
        std::cout << "         vector: find -  " ;
        timer t ;
        x += find( searched_values, vec ) ;
    }

    {
        std::cout << "\n          set: insert - " ;
        timer t ;
        insert( data_set, set ) ;
    }

    {
        std::cout << "            set: find -  " ;
        timer t ;
        x += find( searched_values, set ) ;
    }
    
    return x - x ;
}


coliru, LLVM , GNU, -O3
------- clang++/libc++ ----------

10000000 values, 1000000 searches

vector: insert & sort - 1510 msecs.
         vector: find -  720 msecs.

          set: insert - 5930 msecs.
            set: find -  310 msecs.

------- g++/libstdc++ -----------

10000000 values, 1000000 searches

vector: insert & sort - 1200 msecs.
         vector: find -  770 msecs.

          set: insert - 3510 msecs.
            set: find -  210 msecs.

http://coliru.stacked-crooked.com/a/9b1266753b0c68e1

rextester, microsoft, -Ox
10000000 values, 1000000 searches

vector: insert & sort -  1574 msecs.
         vector: find -   851 msecs.

          set: insert - 13011 msecs.
            set: find -   244 msecs.

http://rextester.com/WJY78145
TheIdeasMan (6817)
@htirwin , @JLBorges

Thank you very much for your replies :+) Those were the results I was expecting, and I did get similar results myself.

@JLBorges

I like what you did with putting the end of the timing in the timer's destructor - quite clever and elegant :+) It is the first time I have seen a decent reason to put code in a destructor - Cheers.

Also, interesting it seems that computing the hash function for the unordered_set takes longer than sorting a vector - that surprised me a bit :+).

I have been trying to write one generic function that will do timing for any algorithm using any container. After a lot of lolly-gagging about, I have come to the conclusion that maybe the easiest way might be to std::bind a std::function with the call incorporating the algorithm, the container and it's iterators. Am working on that today - hopefully it works out OK.

One thing I had been trying (I don't need it now, but interested to find out why ) was to use the type trait std::is_same. It worked fine in a cpp file:

1
2
3
4
 
std::vector<std::size_t> RandomVect(Size,0);

    std::cout << std::boolalpha;
    std::cout << std::is_same<decltype(RandomVect) , std::vector<std::size_t>>::value << '\n';


but I couldn't get it to work when the underlying type was a template parameter, or using the template parameter itself. It compiles, but is always false. Also, the template was instantiated in the cpp file, this is part of the header :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
template<
        typename ContainerData,
        typename T = int,
        std::size_t N = 1, // for use with std::array<T, N> 
        typename A = std::allocator<T> // I have this so that I can still have distinct types, 
                                          // even though their declarations  might look the same 
         >

void AlgoTimer( ContainerData Container,
                    ContainerData TestValues
              ) {

    std::clock_t c_start = std::clock();

    // if Container is a sequence container use std::find
    // right now this condition is always false
    if(
            std::is_same< decltype(Container) ,  std::array<T, N> >::value 
           or std::is_same<decltype(Container),  std::vector<T,A> >::value
           or std::is_same<decltype(Container),  std::deque<T, A> >::value
            or std::is_same<decltype(Container),  std::forward_list<T,A> >::value
       ) {}
    // else use member find function


I am a bit hazy when it comes to querying template parameters for their associated tag information.

Last edited on
JLBorges (13770)
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
 
#include <iostream>
#include <type_traits>
#include <iterator>

namespace detail
{
    template < typename T > struct is_sequence
    {
        template < typename U >
        static char test( U&&, decltype( std::begin( std::declval<U>() ) )* = 0 ) ;

        using two_chars = char[2] ; static two_chars& test(...) ;

        static constexpr bool value = sizeof( test( std::declval<T>() ) ) == 1 ;
    };

    template < typename T > struct is_associative
    {
        template < typename U >
        static char test( U&&, typename U::key_type* = 0 ) ;

        using two_chars = char[2] ; static two_chars& test(...) ;

        static constexpr bool value = sizeof( test( std::declval<T>() ) ) == 1 ;
    };
}

template < typename T > struct is_sequence :
    std::conditional< detail::is_sequence<T>::value || std::is_array<T>::value,
                      std::true_type, std::false_type >::type {};

template < typename T > struct is_associative_sequence :
    std::conditional< detail::is_sequence<T>::value && detail::is_associative<T>::value,
                      std::true_type, std::false_type >::type {};

#include <vector>
#include <array>
#include <vector>
#include <map>
#include <unordered_set>

int main()
{
    using c_array = int[50] ;
    using array = std::array<int,50> ;
    using vector = std::vector<int> ;
    using map = std::map<int,int> ;
    using set = std::unordered_set<int> ;

    std::cout << std::boolalpha

              << "      c array: " << is_sequence<c_array>::value << ' ' // true
              << is_associative_sequence<c_array>::value << '\n' // false

              << "    std array: " << is_sequence<array>::value << ' ' // true
              << is_associative_sequence<array>::value << '\n' // false

              << "       vector: " << is_sequence<vector>::value << ' ' // true
              << is_associative_sequence<vector>::value << '\n' // false

              << "          map: " << is_sequence<map>::value << ' ' // true
              << is_associative_sequence<map>::value << '\n' // true

              << "unordered_set: " << is_sequence<set>::value << ' ' // true
              << is_associative_sequence<set>::value << '\n' ; // true
}

http://coliru.stacked-crooked.com/a/661ec9616694dc05
http://rextester.com/AQA11642


> Also, interesting it seems that computing the hash function for the unordered_set takes longer than sorting a vector

It is not computing the hash that takes a lot of time. Things like dynamic memory allocation, rehashing when load factor becomes more than the maximum load factor, a data representation that is less compact than a vector and the general poorer memory locality have an adverse impact on time.
Last edited on
TheIdeasMan (6817)
@JLBorges

Thank you very much - as per usual, that is totally awesome :+D. I never would have figured that out myself: at the moment it is about 3 orders of combinations above my current understanding :+) . Crikey, I will have to ruminate on that quite a bit - some reading up to do. I might have more questions later.

Regards.
TheIdeasMan (6817)
Ok, some lots of initial questions, see if I have understood this correctly:

7
8
9
10
11
12
13
14
15
 
    template < typename T > struct is_sequence
    {
        template < typename U >
        static char test( U&&, decltype( std::begin( std::declval<U>() ) )* = 0 ) ;

        using two_chars = char[2] ; static two_chars& test(...) ;

        static constexpr bool value = sizeof( test( std::declval<T>() ) ) == 1 ;
    };


Obviously the whole thing (rather, the value) has to evaluate to 0 or 1 true or false, and this happens with line 14, specifically this part : sizeof( test( std::declval<T>() ) ) == 1.

Interesting to note that both declarations of the test function on line 10 and 12, are just declarations, no definition anywhere. But they do seem to be evaluated? And somehow the functions return a char?

Line 14 is constexpr, so must be evaluated at compile time, and it calls the test function with 1 argument which seems to match parameter 1 of the test function declaration on line 10. The other parameter has a default value, so it's optional?
So what of the declaration of test on line 12? As in it's argument being a parameter pack and it's return type of two_chars& ? I guess it's something to do with the use of sizeof on line 14. Maybe the call on line 14, somehow matches the function on line 12 which then matches the one on line 10? I am guessing the test function on line 12 wouldn't be evaluated otherwise?

As for the detail of line 10:

U&& is a rvlaue reference, that's pretty obvious.

std::declval<U>() converts the type U into a rvalue. And this is then used as an argument to U's begin iterator. Not sure what the effect of this rvalue is on the call to the begin iterator? Or why one might need an rvalue there?

With the decltype call, it's argument is perhaps the begin iterator, or maybe T ? Not sure what is being returned, cppreference has this:

cppreference wrote:
Explanation
1) If the argument is an unparenthesized id-expression or an unparenthesized class member access expression, then decltype yields the type of the entity named by this expression. If there is no such entity, or if the argument names a set of overloaded functions, the program is ill-formed.
2) If the argument is any other expression of type T, and
a) if the value category of expression is xvalue, then decltype yields T&&;
b) if the value category of expression is lvalue, then decltype yields T&;
c) if the value category of expression is prvalue, then decltype yields T.


At the moment I am guessing part 2 applies, part 1 doesn't seem to fit :+) It doesn't seem to be an xvalue , maybe it's a prvalue (do not have identity and can be moved from are called prvalue expressions; ) in which case part c applies and it yields a T I am guessing the declvalue part must be a prvalue. But then there is * at the end of decltype, so the expression becomes a pointer? Then it has a default value of 0, making the argument optional?

On line 20, I understand that key_type is a member in common with associative containers, so you have taken advantage of that. But the same could not be said for the sequence containers, so there is some gymnastics required on line 10?

The rest of it all makes sense.

Sorry for zillions of questions, but I feel that in the C++ world I am perhaps qualified for first year of high school, and have somehow found myself in a final year class :+D

Just going back to std::is_same (If I may): Is there a reason why it didn't work in conjunction with the template parameter? Or was I missing something ?

Thanks again :+)




htirwin (1208)
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 <type_traits>
#include <iterator>

namespace detail
{
    template < typename T > struct is_sequence
    {
        template < typename U >
        static char test( U&&, decltype( std::begin( std::declval<U>() ) )* = 0 ) ;
        using two_chars = char[2] ; static two_chars& test(...) ;
        static constexpr bool value = sizeof( test( std::declval<T>() ) ) == 1 ;
    };
}

template < typename T > struct is_sequence :
    std::conditional< detail::is_sequence<T>::value || std::is_array<T>::value,
                      std::true_type, std::false_type >::type {};

#include <vector>

int main()
{
    std::cout << std::boolalpha << is_sequence<std::vector<bool>>::value << '\n';
}

This has a bug?
Last edited on
JLBorges (13770)
> Interesting to note that both declarations of the test function on line 10 and 12,
> are just declarations, no definition anywhere. But they do seem to be evaluated?

These are strawman functions; we want the compiler to answer the question: "if there are the overloads for the function test, which of the two would be selected via overload resolution?". However, the selected function is never actually called because the expression involving the call is used only in an unevaluated context.
In jargon, these functions are never odr-used.

The operands of the four operators typeid, sizeof, noexcept, and decltype (since C++11) are expressions that are not evaluated (unless they are polymorphic glvalues and are the operands of typeid), since these operators only query the compile-time properties of their operands.
Thus, std::size_t n = sizeof(std::cout << 42); does not perform console output.
http://en.cppreference.com/w/cpp/language/expressions#Unevaluated_expressions


There is a surprising amount of power in sizeof : You can apply sizeof to any expression, no matter how complex, and sizeof returns its size without actually evaluating that expression at runtime. This means that sizeof is aware of overloading, template instantiation, conversion rules—everything that can take part in a C++ expression. In fact, sizeof conceals a complete facility for deducing the type of an expression; eventually, sizeof throws away the expression and returns only the size of its result. - Alexandrescu in 'Modern C++ Design'


Needless to say, std::declval<>() is also a strawman; it can only be used in unevaluated contexts.
http://en.cppreference.com/w/cpp/utility/declval


> U&& is a rvlaue reference,

U&&, where U is a template type parameter is what Scott Meyers calls a 'universal reference'.
https://isocpp.org/blog/2012/11/universal-references-in-c11-scott-meyers


> So what of the declaration of test on line 12? As in it's argument being a parameter pack

using two_chars = char[2] ; static two_chars& test(...) ; is not a template; it is a c-style variadic function.

In the C programming language, at least one named parameter must appear before the ellipsis parameter, so printz(...); is not valid. In C++, this form is allowed even though the arguments passed to such function are not accessible, and is commonly used as the fallback overload in SFINAE, exploiting the lowest priority of the ellipsis conversion in overload resolution. (emphasis added)
http://en.cppreference.com/w/cpp/language/variadic_arguments


The overload is resolved between the two candidate functions
1
2
 
template < typename U > 
static char test( U&&, decltype( std::begin( std::declval<U>() ) )* = 0 ) ; // overload 1

and
using two_chars = char[2] ; static two_chars& test(...) ; // overload 2

If std::begin(x), where the type of the expression x is T, is a valid construct, the overload resolves to overload 1.
sizeof( test( std::declval<T>() ) ) is sizeof(char) ie. 1

If not, overload 1 is not viable, SFINAE http://en.cppreference.com/w/cpp/language/sfinae kicks in (that is the raison d'être for overload 1 being a function template) and the overload resolves to overload 2.
sizeof( test( std::declval<T>() ) ) is sizeof( char[2] ) ie. 2



> going back to std::is_same ... Is there a reason why it didn't work in conjunction with the template parameter?

The template arguments other than that for the type parameter ContainerData can't be deduced.
TheIdeasMan (6817)
Ok, thanks for providing such a detailed answer - things are becoming clearer. The concept of the strawman functions is quite a revelation.

I had been aware of SFINAE, but had not realised that it was being used in this context. I just learnt yesterday how it is used with ->decltype , but I will have to digest the link you kindly provided :+)

However I have another question, relating to this comment:

If std::begin(x), where the type of the expression x is T, is a valid construct, the overload resolves to overload 1.


Most all the containers have begin iterators (except the Container Adaptors), so won't that nearly always be a valid construct?

One of the ideas I had was that each of the container categories nearly have their own types of iterator. That is for Sequence Category (array vector deque) has RandomAccessIterator, while forward_list and list have ForwardIterator. For the Associative containers, they all have BidirectionalIterator. But the relation of Category to Iterator type isn't 1:1 so that could be a bit awkward.

The motivation for determining the type of the container was to use the correct algorithm: std::find for sequence containers; otherwise the member find function. If we were to make this as generic as possible (any STL algorithm), would it be a good idea to somehow make use of the desired algorithm in the overload? So if std::find is invalid, use member find? Or if some other algorithm is invalid, use the appropriate function?

I can't help thinking all of this would be a lot easier if there were a type trait for each container: is_vector, is_list etc. I guess that's why my initial idea was to use is_same. I had also spent some time with RTTI.

Sorry I was heading off on a tangent there, if I can pass a std::function to the Timer function, then hopefully that will negate all that. The caller should know what container, iterators and algorithm to use.

> going back to std::is_same ... Is there a reason why it didn't work in conjunction with the template parameter?

The template arguments other than that for the type parameter ContainerData can't be deduced.


So does that I mean I should have had ContainerData instead of Container? Or I can't have std::vector as the second parameter? Or is_same just can't be used at all with template parameters, and that is why you have presented your code?

It is not computing the hash that takes a lot of time. Things like dynamic memory allocation, rehashing when load factor becomes more than the maximum load factor, a data representation that is less compact than a vector and the general poorer memory locality have an adverse impact on time.


Ah, I will try reserving the required amount to see what difference that will make.

Sorry for all the questions and comments, but I am learning a lot today :+)

It's late at my end (I have a mad sleeping pattern at the moment) , so I might not see or reply to anything for quite awhile. So don't feel under pressure to pump out a reply :+)
htirwin (1208)
Anyways, here is a fix for the vector<bool> related bug. Any way to tell programatically that vector<bool> is not a sequence?
1
2
 
template<>
struct is_sequence< std::vector<bool> > { static const bool value=false; };
Last edited on
Pages: 12