Creating your own std::vector like class from scratch

Pages: 12
MiiNiPaa (7820)
memcpy(temp, start_, size() * sizeof(value_type));potential to wreck anything which is not POD. For example, moving strings using small string optimisation that way practically guarantees crash.
MiiNiPaa (7820)
Also you did not check if high_resolution_clock is steady before using it.
Also high_resolution_clock measures wall time, not the time actually used by your application to do something — if system scheduler will decide to suspend your program and give processing time to another process, your measurement will be off.

Read JLBorges posts here: http://www.cplusplus.com/forum/beginner/146620/#msg771119
Last edited on
Gamer2015 (686)
What happens if you do the test in the other order, i.e. myvec before std::vector?

Interestingly it spreads out even more
  std::vector: 54147
        myvec: 17319


potential to wreck anything which is not POD. For example, moving strings using small string optimisation that way practically guarantees crash.

Could you show me such a case?

I can't generate 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
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
151
152
153
154
 
#include <iostream>
#include <chrono>
#include <vector>
#include <string>
#include <cstring>
#include <iomanip>

template <typename T, class alloc_t=std::allocator<T>>
class myvec {
public:
    typedef std::size_t size_type;
    typedef alloc_t allocator_type;

    typedef T value_type;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef value_type* pointer;
    typedef const pointer const_pointer;

    // constructors
    myvec()
        : allocator_()
        , start_()
        , size_()
        , capacity_()
    {}

    myvec(const myvec& vec)
        : allocator_(vec.allocator())
        , start_(allocator().allocate(vec.size()))
        , size_(vec.size())
        , capacity_(vec.size())
    {
        memcpy(start_, vec.start(), size());
    }

    myvec(myvec&& vec)
        : allocator_(std::move(vec.allocator_))
        , start_(std::move(vec.start_))
        , size_(std::move(vec.size_))
        , capacity_(std::move(vec.capacity_))
    {
        vec.start_ = 0;
        vec.size_ = 0;
        vec.capacity_ = 0;
    }

    ~myvec() {
        if(start_) {
            for(int i = 0; i < size(); ++i)
                start_[i].~value_type();

            allocator().deallocate(start_, capacity());
        }
    }

    // data
    size_type capacity() const { return capacity_; }
    size_type size() const { return size_; }
    const_pointer data() const { return start_; }
    allocator_type& allocator() { return allocator_; }

    // modify
    void push_back(const_reference value) {
        if(capacity() == size()) // if the vector is full allocate new memory
        {
            // get new-needed space (geometric growth factor 2)
            if(capacity() != 0)
                capacity_ *= 2;
            else
                capacity_ = 1;

            // allocate space
            pointer temp = allocator().allocate(capacity());

            // then move the elements over and create the new element
            memcpy(temp, start_, size() * sizeof(value_type));

            allocator().deallocate(start_, size());
            start_ = temp;
        }
        new (start_ + size()) value_type(value);

        ++size_;
    }

    // access
    reference operator[](size_type position) { return start_[position]; }
    const_reference operator[](size_type position) const { return start_[position]; }

private:
    allocator_type allocator_;
    pointer start_;
    size_type size_;
    size_type capacity_;
};

// push a few elements in both vectors and compare size, capacity and values
template <class container, typename T>
void Test1(T val) {
    container vec;
    std::cout << "push_back: " << std::endl;
    vec.push_back(val);
    std::cout << "c/s: " << vec.capacity() << ' ' << vec.size() << std::endl;

    std::cout << "e: ";
    for(int i = 0; i < vec.size(); ++i)
        std::cout << vec[i] << ' ';
    std::cout << std::endl;

    std::cout << "push_back: " << std::endl;
    vec.push_back(val);
    std::cout << "c/s: " << vec.capacity() << ' ' << vec.size() << std::endl;

    std::cout << "e: ";
    for(int i = 0; i < vec.size(); ++i)
        std::cout << vec[i] << ' ';
    std::cout << std::endl;

    std::cout << "push_back: " << std::endl;
    vec.push_back(val);
    std::cout << "c/s: " << vec.capacity() << ' ' << vec.size() << std::endl;

    std::cout << "e: ";
    for(int i = 0; i < vec.size(); ++i)
        std::cout << vec[i] << ' ';
    std::cout << std::endl;

    std::cout << "push_back: " << std::endl;
    vec.push_back(val);
    std::cout << "c/s: " << vec.capacity() << ' ' << vec.size() << std::endl;

    std::cout << "e: ";
    for(int i = 0; i < vec.size(); ++i)
        std::cout << vec[i] << ' ';
    std::cout << std::endl;

    std::cout << "push_back: " << std::endl;
    vec.push_back(val);
    std::cout << "c/s: " << vec.capacity() << ' ' << vec.size() << std::endl;

    std::cout << "e: ";
    for(int i = 0; i < vec.size(); ++i)
        std::cout << vec[i] << ' ';
    std::cout << std::endl;
}

int main(void)
{
    Test1<std::vector<std::string>>(std::string("Hello"));
    Test1<myvec<std::string>>(std::string("Hello"));

    return 0;
}
push_back: 
c/s: 1 1
e: Hello 
push_back: 
c/s: 2 2
e: Hello Hello 
push_back: 
c/s: 4 3
e: Hello Hello Hello 
push_back: 
c/s: 4 4
e: Hello Hello Hello Hello 
push_back: 
c/s: 8 5
e: Hello Hello Hello Hello Hello 
push_back: 
c/s: 1 1
e: Hello 
push_back: 
c/s: 2 2
e: Hello Hello 
push_back: 
c/s: 4 3
e: Hello Hello Hello 
push_back: 
c/s: 4 4
e: Hello Hello Hello Hello 
push_back: 
c/s: 8 5
e: Hello Hello Hello Hello Hello


That being said the performance difference is getting smaller here:

  std::vector: 144932
        myvec: 135083
  std::vector: 127032
        myvec: 124030
  std::vector: 130041
        myvec: 122995

Last edited on
Gamer2015 (686)
Also you did not check if high_resolution_clock is steady before using it.
Also high_resolution_clock measures wall time, not the time actually used by your application to do something — if system scheduler will decide to suspend your program and give processing time to another process, your measurement will be off.
Well, that made some difference...
So it's actually exactly the same speed right now for std::string
  std::vector: 1967670
        myvec: 1967669


but I loose totally on int 
  std::vector: 0
        myvec: 4203


thanks guys
Last edited on
MiiNiPaa (7820)
Example which breaks after memcpy:
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
 
#include <bits/stdc++.h>

struct SmallString_O
{
    SmallString_O() : end(buff) {}
    ~SmallString_O()
    {
        if(not (end >= (char*)this && end < (char*)this + sizeof(*this)))
            delete[] end;
    }
    char* end;
    char buff[10];

};

int main()
{
    char data[sizeof(SmallString_O)];
    new (data) SmallString_O;

    char data2[sizeof(SmallString_O)];
    std::memcpy(data2, data, sizeof(SmallString_O));
    
    ((SmallString_O*)data)->~SmallString_O();
    std::cout << "working fine" << std::endl;
    ((SmallString_O*)data2)->~SmallString_O();
    std::cout << "working fine" << std::endl;
}
Also any self-referential (directly or otherwise) structure will have a problem: when you move it that way, you do not send a signal to containing object to update its references.

You can only copy with memcpy C++ objects which are TiviallyCopyable: http://en.cppreference.com/w/cpp/types/is_trivially_copyable
Gamer2015 (686)
Also any self-referential (directly or otherwise) structure will have a problem: when you move it that way, you do not send a signal to containing object to update its references.

That makes sense, thanks!
MiiNiPaa (7820)
std::vector grows 1.5 times.
libstdc++ grows 2 times, VS implementation grows 1.5 AFAIR. Actually 2 times growth might be worse approach than 1.5 or even 1.9 growth, as memory manager might not be able to reuse abandoned memory to create new buffer for fast growing vector.
Gyiove (97)
so ... what should we use to move items in vector?
I'm already having something on my mind using std::move and then some sort of swap function.

Also while moving items with memcpy, you don't need to signal the ~
If you're going to remove item then signal the item's ~ first and then feel free to use that function.

memcpy is pretty fast function yet std::vector's moving systems are faster somehow.
That's why im searhing another way.
MiiNiPaa (7820)
Also while moving items with memcpy, you don't need to signal the ~
After you move items, they are going to be destroyed by vector destructor anyway. My example was not destroying original objects, but destination objects, simulating later call to destructor of vector.

vector uses move semantics if move operation does not throw exception. Otherwise it defaults to copy to give strong exception guarantee. It uses move_if_noexcept internally.
http://en.cppreference.com/w/cpp/utility/move_if_noexcept
Gyiove (97)
oh thanks, i shall look it out.
Thanks for the help guys, at least im going somewhere now.
Registered users can post here. Sign in or register to post.
Pages: 12

C++

Forum