C++

Forum

 
Creating your own std::vector like class from scratch

Pages: 123
MiiNiPaa (8886)
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 (8886)
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 (810)
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 (810)
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 (8886)
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 (810)
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 (8886)
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 (186)
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 (8886)
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 (186)
oh thanks, i shall look it out.
Thanks for the help guys, at least im going somewhere now.
Gyiove (186)
what does 
 
 
_Destroy

function do exactly in std:vector ?
MiiNiPaa (8886)
what does
_Destroy
function do exactly in std:vector ?
There is no _Destroy function in std::vector defined by standard. However implementations are free to define additional members if they need them. So answer woud be different depending on which exactly standard library you use. (This is like asking "what does leftmost light on control panel in my car means").

Judging by name, I think, it correctly destroys current buffer.

EDIT: in libstdc++ it only destroys all elements in sequence.

EDIT2: I should clarify: it detects, if type contained in sequence has a nontrivial destructor, and then either calls destructor on all elements or does nothing if destructor is trivial.
Last edited on
Gyiove (186)
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
 
	void resize(size_type _Newsize)
		{	// determine new length, padding as needed
		if (_Newsize < size())
			_Pop_back_n(size() - _Newsize);
		else if (size() < _Newsize)
			{	// pad as needed
			_Alty _Alval(this->_Getal());
			_Reserve(_Newsize - size());
			_TRY_BEGIN
			_Uninitialized_default_fill_n(this->_Mylast, _Newsize - size(),
				_Alval);
			_CATCH_ALL
			_Tidy();
			_RERAISE;
			_CATCH_END
			this->_Mylast += _Newsize - size();
			}
		}

	void _Tidy()
		{	// free all storage
		if (this->_Myfirst != pointer())
			{	// something to free, destroy and deallocate it
			this->_Orphan_all();
			_Destroy(this->_Myfirst, this->_Mylast);
			this->_Getal().deallocate(this->_Myfirst,
				this->_Myend - this->_Myfirst);
			this->_Myfirst = pointer();
			this->_Mylast = pointer();
			this->_Myend = pointer();
			}
		}

	void _Destroy(pointer _First, pointer _Last)
		{	// destroy [_First, _Last) using allocator
		_Alty _Alval(this->_Getal());
		_Destroy_range(_First, _Last, _Alval);
		}
Last edited on
MiiNiPaa (8886)
It seems that the semantic of this implementation is same as libstdc++ one.
Gyiove (186)
there is
 
 
_Destroy(this->_Myfirst, this->_Mylast);

and
1
2
 
this->_Getal().deallocate(this->_Myfirst,
				this->_Myend - this->_Myfirst);

I'm confused. Both are removing?
MiiNiPaa (8886)
_Destroy destroys objects.
deallocate deallocates memory.
This is two different operations.
Gyiove (186)
oh right ... umn so _Destroy calls class's ~ functions right?
Logic tells me that this is what that does.

#2 question:
I'm using visual studio 2013 right now.
It means that i don't have c++14.

Should i update myself to 2014 or there isn't much in c++14?
Are there any functions/algorithms what make things faster?
MiiNiPaa (8886)
Should i update myself to 2014 or there isn't much in c++14?
VS does not have very good C++14 support yet: http://blogs.msdn.com/b/vcblog/archive/2014/11/17/c-11-14-17-features-in-vs-2015-preview.aspx

In C++14 there are some thing which make life easier: improved lambda, some bugfixes in standard library, constexpr functions are actually useful, auto/decltype are working better, and some more.

Are there any functions/algorithms what make things faster?
In C++14 or at all? C++14 was intended to be a bugfix release to solve problems found in C++11. So there is not much new stuff.
Also just because there is new stuff in standard library it does not means that it will make everything faster.

so _Destroy calls class's ~ functions right?
Yes. It calls destructors of contained objects. Or doesn't. Depending on type. If you have vector of ints it will not do anything as int is a TriviallyDestructible type which destructor does nothing.
A way to save some cycles: detect if destructor should be called and do not call it if it is not needed.
Gyiove (186)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
		void _reallocate(size_type newsize)
		{
			pointer _Ptr = this->_Getal().allocate(newsize);

			_TRY_BEGIN
				_Umove(this->data, this->_last, _Ptr);
			_CATCH_ALL
				this->_Getal().deallocate(_Ptr, newsize);
			_RERAISE;
			_CATCH_END

				if (this->data != pointer())
				{
					_Destroy(this->data, this->_last); // is this really necessary?
					this->_Getal().deallocate(this->data, this->_end - this->data);
				}

			if (newsize > size()) this->_last = _Ptr + size();
			else this->_last = _Ptr + newsize;
			this->_end = _Ptr + newsize;
			this->data = _Ptr;
		}

while reallocating and new size is larger than old size, should i remove all old objects
from old array?

I was thinking if i have a class:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
class myclass {
myclass() : value(0) {
}

myclass(int size) {
value = new char[size];
}

~myclass() {
if(size) delete value;
}

char *value;
};


I dont really need to delete it while moving it from old array to new array.
I'm moving class's pointers/variables and thats all what needed.
So ... umn, in what case is destroying all objects while moving them necessary?
Last edited on
Pages: 123