4
\$\begingroup\$

I am learning c++ and read why we can't use realloc() in std::vector, but i think we can use realloc() for pods, so here is my attempt to write std::vector like class template specialized for PODs

#include <malloc.h>
#include <stdexcept>
#include <type_traits>

namespace gupta {
namespace detail {
namespace podvector {
template <typename T> inline auto malloc(size_t elm_count) {
  return ::malloc(elm_count * sizeof(T));
}

template <typename T> inline auto realloc(void *old_block, size_t elm_count) {
  return ::realloc(old_block, elm_count * sizeof(T));
}
} // namespace podvector
} // namespace detail

template <typename PodType,
          typename = std::enable_if_t<std::is_pod<PodType>::value>>
class podvector {
public:
  using value_type = PodType;
  using size_type = size_t;
  using pointer = value_type *;
  using const_value_pointer = const value_type *;

  ~podvector() {
    if (m_memory)
      free(m_memory);
  }

  podvector(size_type initial_size = 0) {
    alloc(initial_size);
    m_size = initial_size;
  }

  podvector(size_type initial_size, const value_type &value)
      : podvector(initial_size) {
    for (auto &v : *this)
      v = value;
  }

  podvector(const podvector &other) : podvector(other.m_size) {
    for (size_type i = 0; i < m_size; i++)
      m_memory[i] = other.m_memory[i];
  }

  podvector(const podvector &&other)
      : m_memory{std::move(other.m_memory)},
        m_capacity{std::move(other.m_capacity)}, m_size{
                                                     std::move(other.m_size)} {
    // other.m_memory = nullptr;
    other.alloc(0);
  }

  podvector &operator=(const podvector &rhs) {
    if (this != &rhs) {
      resize(rhs.m_size);
      for (size_type i = 0; i < rhs.m_size; i++)
        m_memory[i] = rhs[i];
    }
    return *this;
  }

  podvector &operator=(podvector &&rhs) {
    if (this != &rhs) {
      this->~podvector();
      m_memory = std::move(rhs.m_memory);
      m_capacity = std::move(rhs.m_capacity);
      m_size = std::move(rhs.m_size);
      // rhs.m_memory = nullptr;
      rhs.alloc(0);
    }
    return *this;
  }

  void resize(size_type new_size) {
    if (new_size > m_size)
      change_capacity(new_size);
    m_size = new_size;
  }

  void reserve(size_type new_capacity) {
    if (m_capacity < new_capacity)
      change_capacity(new_capacity);
  }

  void push_back(const value_type &new_elm) {
    if (m_size + 1 > m_capacity)
      change_capacity(std::min(m_capacity * 2, 1));
    m_memory[m_size++] = new_elm;
  }

  void pop_back() { m_size--; }

  auto size() const { return m_size; }
  auto capacity() const { return m_capacity; }
  pointer begin() { return m_memory; }
  const_value_pointer begin() const { return m_memory; }
  pointer end() { return m_memory + m_size; }
  const_value_pointer end() const { return m_memory + m_size; }
  value_type &operator[](size_type pos) { return m_memory[pos]; }
  const value_type &operator[](size_type pos) const { return m_memory[pos]; }

private:
  pointer m_memory;
  size_type m_size, m_capacity;
  void alloc(size_type capacity) {
    m_capacity = capacity;
    m_size = 0;
    m_memory =
        static_cast<pointer>(detail::podvector::malloc<value_type>(capacity));
    if (!m_memory)
      throw std::bad_alloc{};
  }
  void change_capacity(size_type new_capacity) {
    m_capacity = new_capacity;
    void *new_memory =
        detail::podvector::realloc<value_type>(m_memory, new_capacity);
    if (!new_memory)
      throw std::bad_alloc{};
    m_memory = static_cast<pointer>(new_memory);
  }
};

} // namespace gupta
\$\endgroup\$
7
\$\begingroup\$
  1. malloc and realloc live in cstdlib. malloc.h is not a standard header, neither in C++ nor in C, and should not be relied on in any case.
  2. Also, you're missing #include <utility> for std::move.
  3. Legacy C functionality, as everything else from the standard library, lives in the std namespace, if you include the corresponding <cheader> files. While you can also include the C standard headers via <header.h>, this is highly discouraged. With the first option, names may also exist in the global namespace, but this is not guaranteed and should not be relied on.
  4. Your malloc and realloc functions need not be inline. In fact, inline does nothing here; remove it.
  5. You don't need to check for null pointers when freeing memory. Passing a null pointer to free is always well defined and does nothing.
  6. You don't need to move out all the data members from other in your move constructor. All of those members are trivial to copy, and have no special move behavior.
  7. The move assignment operator invokes undefined behavior. You cannot just call the destructor of an object and then write to its members. Calling the destructor completely ends the lifetime of the object; afterwards, there's nothing there to write to. Furthermore, this is a kind of anti-pattern; in almost all cases, the move assignment operator should be implemented via the copy-and-swap idiom.
  8. push_back is broken. You call change_capacity with the result of std::min(m_capacity * 2, 1), which is either 0 or 1, in any case. Most likely, you'd want to use std::max instead.
  9. if (m_size + 1 > m_capacity) looks strange to my eyes. I would just write if (m_size >= m_capacity).
  10. pop_back should definitely return a value. It's not very useful otherwise.
  11. Since you're going for what seems to be a std-like container interface, you should add a little more functionality. For one, you're missing some of the usual type definitions, such as iterator and const_iterator. Furthermore, some sort of emplace mechanism would be appropriate, as well as some way to clear the container and some functionality to shrink it, as well as some other things.
  12. You should make sure that memory is properly initialized. As a user, I would expect that it's safe to access every element in bounds; however, you are not initializing memory at all, leaving that job to the user. I'd expect memory to be default- or zero-initialized; making use of std::calloc should do the trick (alternatively, you can also just std::memset the area).
  13. I would make your malloc and realloc functions a little bit more useful. As of right now, the onus of checking whether allocation succeeded is put on the user of those functions, but in my opinion it would be much cleaner and safer to lift those functions to a "C++-safe" level, i.e. make them check the return value of the underlying allocation call directly and convert that into an exception directly.
  14. std::is_pod is being deprecated, in accordance with the standard library moving away from the term POD as a whole. Also, the requirement that T must be a POD type is too strict; your vector will still work correctly if T is trivial.
\$\endgroup\$
  • \$\begingroup\$ Re #10: std::vector::pop_back doesn't return a value, either. What would be nice, however, would be a back() member function that returns a reference to the last element in the podvector. \$\endgroup\$ – hoffmale Jul 29 '18 at 12:56
  • \$\begingroup\$ @hoffmale You're right. Still, why not fix the mistakes of the standard library while you're at it :P \$\endgroup\$ – Ben Steffan Jul 29 '18 at 13:05
  • \$\begingroup\$ Actually, I'm siding with the standard library: Removing the last element is a different operation than retrieving it (so it violates SRP), and if it isn't used by the caller pop_back just performs an unnecessary copy. \$\endgroup\$ – hoffmale Jul 29 '18 at 13:55
  • \$\begingroup\$ @hoffmale Well, in that case, the name pop_back is just badly chosen. A pop operation should always return the popped value. If that's your stance, you should advocate for renaming the function to remove_back, or something along those lines. \$\endgroup\$ – Ben Steffan Jul 29 '18 at 15:17
  • \$\begingroup\$ If any pop-like member function were to return a value, no container could provide the strong exception guarantee mandated by the standard. This might not matter if the language is garbage collected and/or uses references only (basically forcing everybody to something similar to std::vector<std::unique_ptr<T>>, where the assignment is noexcept), but this option is not available in C++. What would you do if T contains some resource (e.g. it's owning a pointer or file handle), but the assignment of the result from pop(or the like) throws an exception for some reason? \$\endgroup\$ – hoffmale Jul 29 '18 at 16:09
2
\$\begingroup\$

Memory Allocation Layer

Before looking at everything lets look at the memory allocation layer.

#include <malloc.h>

namespace gupta {
namespace detail {
namespace podvector {
template <typename T> inline auto malloc(size_t elm_count) {
  return ::malloc(elm_count * sizeof(T));
}

template <typename T> inline auto realloc(void *old_block, size_t elm_count) {
  return ::realloc(old_block, elm_count * sizeof(T));
}
} // namespace podvector
} // namespace detail

....
private:
  void alloc(size_type capacity) {
    m_capacity = capacity;
    m_size = 0;
    m_memory =
        static_cast<pointer>(detail::podvector::malloc<value_type>(capacity));
    if (!m_memory)
      throw std::bad_alloc{};
  }
  void change_capacity(size_type new_capacity) {
    m_capacity = new_capacity;
    void *new_memory =
        detail::podvector::realloc<value_type>(m_memory, new_capacity);
    if (!new_memory)
      throw std::bad_alloc{};
    m_memory = static_cast<pointer>(new_memory);
  }

Lets just say that <malloc.h> is not a valid header. You should probably be using <cstdlib> (this is C++ so prefer the C++ headers) which puts all the function in the standard namespace. So your use of ::malloc() and ::realloc() are wrong as they are not necessarily in the global namespace (you just happen to get lucky).

You do the memory allocation in your gupta::detail::podvector namespace but leave the checking for null to your vector class. Using Separation of Concerns we should really be doing all the memory handling (including checking for failed allocation) in your memory functions not inside your vector.

Also why are you static_cast the result in the vector. Would it not be easier to cast the type in the allocation routines so that you return the correct type.

Though your use of static_cast is correct this is the kind of thing I would want other developers to have a critical look at to make sure I got it correct. Thus I would have used reinterpret_cast<>() to make people stop and think to make sure cast is correct.

There is a bug in your current code. A std::vector always makes sure all members are in a specific state after initialization. You don't do this. Your main constructor simply calls alloc() then sets the size. Since alloc simply calls std::malloc() the underlying memory is not in any specific state. Thus I would use std::calloc() to make sure the memory returned is in a standard state.

template <typename T>
T* new_malloc(size_t elm_count) {
    auto tmp = std::calloc(elm_count, sizeof(T));
    if (tmp == nullptr) {
        throw std::bad_alloc("PLOP");
    }
    return reinterpret_cast<T*>(tmp);
}

template <typename T>
T* new_realloc(void *old_block, size_t elm_count) {
    auto tmp = std::realloc(old_block, elm_count * sizeof(T));
    if (tmp == nullptr) {
        throw std::bad_alloc("PLIP");
    }
    return reinterpret_cast<T*>(tmp);
}

...
private:
  void alloc(size_type capacity) {
      m_capacity = capacity;
      m_size     = 0;
      m_memory   = detail::podvector::new_malloc<value_type>(capacity));
  }
  void change_capacity(size_type new_capacity) {
      m_capacity = new_capacity;
      m_memory   = detail::podvector::new_realloc<value_type>(m_memory, new_capacity);
  }

Specialization for POD

If you want to specialize for POD. You don't need to customize the whole vector. You just need to specialize the allocation method used by the vector.

You do need to keep it in mind for a couple of functions (but I don't think you need to do anything special).

private:
  // POD Data
  typename std::enable_if_t<std::is_pod<PodType>::value>>::value_type
  alloc(size_type capacity) {
      m_capacity = capacity;
      m_size     = 0;
      m_memory   = detail::podvector::new_malloc<value_type>(capacity));
  }
  typename std::enable_if_t<std::is_pod<PodType>::value>>::value_type
  change_capacity(size_type new_capacity) {
      m_capacity = new_capacity;
      m_memory   = detail::podvector::new_realloc<value_type>(m_memory, new_capacity);
  }


  // Any other Data
  typename std::enable_if_t<!std::is_pod<PodType>::value>>::value_type
  alloc(size_type capacity) {
      m_capacity = capacity;
      m_size     = 0;
      m_memory   = ::operator new(sizeof(T) * m_capacity);
  }
  typename std::enable_if_t<!std::is_pod<PodType>::value>>::value_type
  change_capacity(size_type new_capacity) {
      podvector<T>  tmpBuffer(newCapacity);

      for(loop = 0; loop < m_size; ++loop) {
          tmpBuffer.push_back(std::move(m_memory[loop]));
      }
      tmpBuffer.swap(*this);
  }
\$\endgroup\$
  • \$\begingroup\$ I'm more in favor of usingif constexpr for the specializations, makes the code easier to read \$\endgroup\$ – JVApen Aug 2 '18 at 18:00
  • \$\begingroup\$ @JVApen Do you have a link to an example or description? \$\endgroup\$ – Martin York Aug 2 '18 at 18:25
  • \$\begingroup\$ stackoverflow.com/a/51659883/2466431 should indicate the idea \$\endgroup\$ – JVApen Aug 2 '18 at 18:27
  • \$\begingroup\$ @JVApen I have seen that once before. But I have never used it. I will need to experiment. I have some code reviews coming up where this may help. \$\endgroup\$ – Martin York Aug 2 '18 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.