LinkedVector : a vector of elements with links to other elements

Question

I wanted to have a vector with usual values and with some sort of indexing : an element can have links to other elements (via indices). Something like the following, where V::size_type is the type of the vector's indices.

vector<pair<T, vector<V::size_type>>>

Obviously, this does not work because V is dependant on itself. So I came up with the code below. I would like to know about the following points.

• Is private inheritance correct in this case ?
• Is this how you implement a "custom" vector based on the standard one ?
• Are there other solutions ?

Anything else you can tell me is welcome (code correctness, best practices...).

The code includes a file LinkedVector.hxx containing the definitions of the methods. Here is a compiling compact code for testing purposes.

#ifndef LINKEDVECTOR_HPP
#define LINKEDVECTOR_HPP
#include <vector>
#include <algorithm>
/* LinkedVector
 * Vector of elements with links to other elements
 * Basically does what this would do if it was compilable :
 * vector<pair<T, vector<V::size_type>>>
 * where T is the usual type (in a vector<T>)
 * and V is the type of the whole vector (so that V::size_type is the type of its indices)
 * The class has an inherited vector<T> and a member vector<vector<vector<T>::size_type>>
 */
template<class T, class Allocator = std::allocator<T>>
class LinkedVector : private std::vector<T, Allocator> {
 using VectorType = std::vector<T, Allocator>;
 using IndexVectorType = std::vector<typename VectorType::size_type>;
public:
 using typename VectorType::value_type;
 using typename VectorType::allocator_type;
 using typename VectorType::size_type;
 using typename VectorType::difference_type;
 using typename VectorType::reference;
 using typename VectorType::const_reference;
 using typename VectorType::pointer;
 using typename VectorType::const_pointer;
 using typename VectorType::iterator;
 using typename VectorType::const_iterator;
 using typename VectorType::reverse_iterator;
 using typename VectorType::const_reverse_iterator;
 using VectorType::VectorType;
 using VectorType::at;
 using VectorType::operator[];
 using VectorType::front;
 using VectorType::back;
 using VectorType::begin;
 using VectorType::cbegin;
 using VectorType::end;
 using VectorType::cend;
 using VectorType::rbegin;
 using VectorType::crbegin;
 using VectorType::rend;
 using VectorType::crend;
 using VectorType::empty;
 using VectorType::size;
 using VectorType::max_size;
 using VectorType::capacity;
 LinkedVector(size_type count, const T& value, const Allocator& alloc = Allocator());
 explicit LinkedVector(size_type count, const Allocator& alloc = Allocator());
 template<class InputIt>
 LinkedVector(InputIt first, InputIt last, const Allocator& alloc = Allocator());
 LinkedVector(const LinkedVector& other);
 LinkedVector(const LinkedVector& other, const Allocator& alloc);
 LinkedVector(LinkedVector&& other);
 LinkedVector(LinkedVector&& other, const Allocator& alloc);
 LinkedVector(std::initializer_list<T> list, const Allocator& alloc = Allocator());
 LinkedVector& operator=(const LinkedVector& other);
 LinkedVector& operator=(LinkedVector&& other);
 LinkedVector& operator=(std::initializer_list<T> list);
 iterator insert(const_iterator pos, const T& value);
 iterator insert(const_iterator pos, T&& value);
 iterator insert(const_iterator pos, size_type count, const T& value);
 template<class InputIt>
 iterator insert(const_iterator pos, InputIt first, InputIt last);
 iterator insert(const_iterator pos, std::initializer_list<T> list);
 template<class... Args>
 iterator emplace(const_iterator pos, Args&&... args);
 iterator erase(const_iterator pos);
 iterator erase(const_iterator first, const_iterator last);
 void reserve(size_type newCap);
 void shrink_to_fit();
 void clear();
 void push_back(const T& value);
 void push_back(T&& value);
 template<class... Args>
 void emplace_back(Args&&... args);
 void pop_back();
 void resize(size_type count);
 void resize(size_type count, const value_type& value);
 void swap(LinkedVector& other);
 void addLink(size_type from, size_type to);
 void removeLink(size_type from, size_type to);
 void clearLink(size_type from);
 void clearAllLinks();
 bool isLinked(size_type from, size_type to) const;
private:
 std::vector<IndexVectorType> m_links;
};
#include "LinkedVector.hxx"
#endif // LINKEDVECTOR_HPP

• user52292: Why not using vector<pair<T, vector<size_t>>>?
• Nelfeal: @firda Because there is no guarantee on the type of std::vector<T>::size_type.
• user52292: I think that one static_assert would be good enough, because it is typedef of allocator<pair<T,size_type>>::size_type which would again be circular, so, I would either use size_t or allocator<T>::size_type and place the static_assert there. Just my opinion, nothing more ;)
• Nelfeal: @firda I have to admit, this sounds like a good idea.

Answer 1

Overall the interface looks good and I have no problem with private inheritance here, it allows you to use using to export (publish) some features that are already there. Second option would be to use private member and forward everything (typedefs, methods simply calling the method on the inner variable), no win here, I would prefer private inheritance.

The m_links allows you to have those links in second vector instead of using that pair<T,vector<size_t>>> without problems with size_type, but I personally don't see big problem in using size_t or allocator<T>::size_type directly - it is your vector, you have the right to define size_type as you choose and any vector have to accept integral types as indexes - again, I can see no big problem, but to make sure, static_assert would be good:

static_assert(std::is_same<vector<pair<T,vector<size_type>>>::size_type, size_type>::value,
 "bad size_type");
static_assert(std::is_same<vector<T>::size_type, allocator<T>::size_type>::value, ...);
static_assert(std::is_same<allocator<T>::size_type, allocator<
 pair<T,vector<allocator<T>::size_type>>>::size_type, ...);
// or less strict
static_assert(std::is_convertible<size_type, size_t>::value, ...);
static_assert(std::is_convertible<size_type, allocator<T>::size_type>::value, ...);
// ...and such, depending on the actual usage in the class

I would personally use allocator<T>::size_type and private inheritance and few static_asserts, but you can as well think about private member, your custom typedef size_t size_type and doing everything by hand to make it work in any possible scenairo.

Note that this is my personal review and may not fully express the customs of this community ;)

EDIT: Using vector<T>::size_type seems to be better idea since C++11. See comments.

• Nelfeal: After a bit of research, it seems that vector<T>::size_type is always the same, no matter the T, except when vector<T> is specialized (for a particular T). Also, what would be wrong with is_same<vector<pair<T, vector<size_t>>>::size_type, size_t>::value ? I do not understand the need for allocator<T>.
• user52292: I will look that up, because there were some changes in C++11 to separate typedefs in containers and allocators (namely I know that const_reference was borrowed from allocator prior to C++11). My asserts were just to express the idea, that they all should be the same. Feel free to use vector<T>::size_type and assert it to be the same to any other you use.
• Nelfeal: Oh I see. According to cppreference, for std::vector, reference is no longer Allocator::reference but value_type&, pointer is no longer Allocator::pointer but std::allocator_traits<Allocator>::pointer (and similar for const_). But there has never been any link between size_type and Allocator::size_type. Anyway, thanks for the idea, I think that I will go with it.

Answer 2

I can see that you already have an accepted answer, but I think there are a few things that you should consider:

• please do not inherit std:: containers. The code is UB (which in practice means you will probably have some memory leaks).

• Be consistent with coding conventions. If you have one convention imposed by your base class (though you shouldn't have a base class from std:: here -- see point above) you should respect that convention for the rest of the class.

Consider client code:

LinkedVector<int> v = some_function_generating_vector();
v.push_back(10); // looks like snake case
v.addLink(20, 5); // no wait! it's camel case (?!?)

• You could implement a class not inheriting from anything, and store your data internally as a std::vector<std::pair<T, std::vector<std::size_t>>>.

You say:

vector<pair<T, vector<V::size_type>>> - Obviously, this does not work because V is dependant on itself.

This is incorrect. std::vector<X>::size_type is "a type guaranteed to represent correctly the size/indexing of a std::vector". std::size_t is the same, for a native array. In practice, the two are the same (or compatible) ont the same platform. That means, you can definitely write:

std::vector<std::pair<T, std::vector<std::size_t>>>

• Nelfeal: A class is not "UB" by itself ; its use might be. But in my case, there is definitely no undefined behavior since I use private inheritance. I failed on the naming conventions, I grant you that. I probably mixed things up because I decided later on to provide a similar naming to the standard containers. Also, I do not see how my exemple with dependant size_type is incorrect. Of course I could use size_t, but this is where the problem lies. See firda's answer.
• user52292: @utnapistim: Do you have some reference why would private inheritance of std container be UB or at least bad? public could be (especially if you add some data member to change the public destructor), but that is different story. I got similar no-no already, but nobody could give me the why (for no-no private inheritance - I can only think about typo matching something inherited and strange error messages in a response, or bad behaviour in such case, but the typo is the error in such case, not the inheritance).
• utnapistim: @firda, while the construct works as it is (i.e. "not UB"), it's bad for maintenance and obscure/brittle: if people add a public destructor / releasable resource to the class, we get UB. There is nothing explicit in the code, that says "do not add this code" (at least, there are not as many sources that say "do not do this" as are many sources that say "do not inherit from std::containers"). In short, it works but it's still bad (also, it violates the principles of least surprise).
• user52292: @utnapistim: Aren't you missing the difference betwen public and private inheritance? From what I have seen so far, people just cannot distinquish between the two and give bookish answer all the times. In this situation (when you can clearly publish methods with using), the private inheritance is better than composition. Private inheritance is no evil. The rule usually is: use composition when you can, use private inheritance if you have to and this is the have to.