how to write my own vector.emplace_back

[closed account oivD8vqX]

As an exercise I'm writing my own version of vector. I can't figure out how to implement emplace_back. I went and looked at my header for a hint, and this is what I saw:

      /**
       *  @brief  Inserts an object in %vector before specified iterator.
       *  @param  __position  A const_iterator into the %vector.
       *  @param  __args  Arguments.
       *  @return  An iterator that points to the inserted data.
       *
       *  This function will insert an object of type T constructed
       *  with T(std::forward<Args>(args)...) before the specified location.
       *  Note that this kind of operation could be expensive for a %vector
       *  and if it is frequently used the user should consider using
       *  std::list.
       */
      template<typename... _Args>
	iterator
	emplace(const_iterator __position, _Args&&... __args)
	{ return _M_emplace_aux(__position, std::forward<_Args>(__args)...); }

I can't figure out how to read this. How would I find out were _M_emplace_aux is defined?

Actually what I want to do is just understand how you would write emplace_back, any example would help, but advice on how to read these headers would be appreciated.

[seeplus]

_M_emplace_aux is probably defined earlier in the same header - or in an included header.

Do you know/understand Variadic Templates (eg typename... _Args) - as emplace_back depends upon them?

[closed account oivD8vqX]

The short answer is no, I don't know understand Variadic Templates, off the top of my head, but I have used them before, and I guessing it's a recursive list. Information on Variadic Templates I know where to look up, and I would rather learn that reading the documentation, I need to get comfortable reading the documentation.

I'm assuming by your answer that after I read that it will be obvious, so thank you.

[mbozzi]

I can't figure out how to read this. How would I find out were _M_emplace_aux is defined?

There's nothing like a decent IDE for navigating through code. Set up your editor so that it can bring you to _M_emplace_aux when you click on it.

I'd suggest carefully studying std::vector's implementation. Start with the vector class itself, examine its data members and base classes. This info -- its representation, not a list of member functions -- is often the best way to figure out what a class does & how data moves through it.

The base class is present for exception-safety reasons; it manages memory, following a well-aged idiom.

This can be a tough exercise depending on your experience level, but the answers to the inevitable questions
"why is this done"
are very enlightening. There's quite little left to opinion or chance, while the standard library implementers address issues that aren't typically discussed in class or beginner's books.

Alternatively, students have written relatively poor imitations of the real thing as an exercise for years -- and some examples should be easy to find on the web.

Most often these prototypes
a.) require much from the contained type (e.g. a default constructor)
b.) are not exception-safe
c.) do not support allocators
d.) are oversized
etc.

If vector::allocator_type is std::allocator, then emplace_back is roughly equivalent to this (untested) code

template <typename... Args>
  void emplace_back(Args&&... args) 
  { 
    if (size == capacity) 
      increase_capacity(); 

    new (buffer + size) value_type(std::forward<Args>(args)...);
    size++;
  }

[closed account oivD8vqX]

I've spent the morning watching young children or I would have replied earlier.

Thank you very much mbozzi; it worked; below is the actual code I used in my implementation.

As you can see I didn't need to make any changes other than the names I'm using. I still haven't even read up on Variardic Templates yet, I just plugged in your code to see if it would work, and it worked.

        template <typename... Args> 
        void emplace_back(Args&&... args) { 
            allocate();
            *m_end = T(std::forward<Args>(args)...); 
            m_end++; 
        }

Just for completeness, this is my allocate() which is a private function.

        void allocate () {
            if(m_end == m_end_of_storage){
                size_t old_size = size();
                T* temp = new T[(old_size + 1) * 2]();

                m_end_of_storage = temp + (old_size + 1) * 2;

                for(size_t i = 0; i != size(); ++i)
                    *(temp + i) = std::move(*(m_start + i));

                delete[] m_start;

                m_start = m_end = temp;
                m_end += old_size;
            }
        }

I'm testing my version; but any comments/criticisms/pointers would be appreciated.

[mbozzi]

Nice. Compared to std::vector, the resize operation allocate:
a. loses user data (and leaks memory) if move-assignment throws an exception
b. requires T is default-constructible
c. uses a potentially-overloaded new as opposed to ::new

Also the growth factor of 2 is a poor choice, because it prevents the reuse of previously-used blocks of memory. This is because the new capacity is always exactly one greater than the sum of all prior capacities
2^n - 1 = 2^0 + 2^1 + ... 2^(n-2) + 2^(n-1)

A vector of capacity c and growth factor k is resized to capacity ck and then capacity ck^2. Ideally ck^2 would fit in the space previously allocated, ck + c, which happens when
ck^2 <= ck + c
Solve the inequality's upper bound to get k <= φ = (1 + sqrt(5))/2, the golden ratio.

Recall the Fibonacci sequence 1 1 2 3 5 8 13 21, where each term is given by the sum of the prior two. The ratio of adjacent terms converges to φ.

Since we have to deal with finite integers a rational approximation of k = 3/2 is typically used.

[closed account oivD8vqX]

What does the :: in front of new mean? I assume it prevents someone from overloading new.

I went to this site to read the documentation: https://en.cppreference.com/w/cpp/language/new

It tells me the :: is optional, but I can't seem to find where I read about it. I'm just getting use to reading this information.

I've been trying to read the implementations header, but it is really a bit much for me. I going to take your advice and start and using an IDE to help with reading the headers. Up to now I have only been using vim's search syntax to navigate around, but since the implementations vector is made up multiple headers it's not been easy.

I also don't understand what you mean when you say,

requires T is default-constructible

I really am a beginner and I appreciate you taking the time to look at my code. Thanks.