Reference to std::array of different sizes instead of std::array in a base class

Question

I have the following problem. Consider the classes

class face {
    virtual std::vector<ptr>& get_vertices(void) const = 0;
};

class triangle : public face {
private:
    std::vector<ptr> vertices;
public:
    std::vector<ptr>& get_vertices(void) const { return vertices; };
};

class quadrilateral : public face {
private:
    std::vector<ptr> vertices;
public:
    std::vector<ptr>& get_vertices(void) const { return vertices; };
};

Obviously, a triangle and quadrilateral will always have 3 and 4 vertices respectively. Thus, I would like to exchange std::vector by std::array of appropriate size to save the overhead induced by the three additional pointers in std::vector. (This is because I will have millions of faces ...) Now, is there a chance to have a common access function in face with std::array as with std::vector above? With a standard C-array, I would simply return a pointer to the first array entry and its size. Is there a STL-way to do the same or something similar? Or is there any other nice way to achieve this functionality?

Thanks for reading and possibly answering!! Andreas

Which additional pointers in std::vector are you talking about? — Sarfaraz Nawaz
– Sarfaraz Nawaz, Commented May 29, 2011 at 8:27
Do you really need to return them as an STL container? If there's only 3 or 4 elements I don't see much advantage in vector or array. I would just store the pointers in a fixed size array and have some function or operator that returns the elements directly, like virtual ptr& operator[](unsigned idx);, and another function for getting their count. — Timo
– Timo, Commented May 29, 2011 at 9:01
@Nawaz: The implementation of std::vector (at least for gcc) uses three pointers for the begin of storage, finish of storage and end of storage in addition to the stored data itself. This becomes none neglectable overhead if one has a huge amount of std::vectors with relatively few entries. — Andreas
– Andreas, Commented May 29, 2011 at 18:53
@Timo: This is a solution I was thinking of, but it does not seem to be a "nice" STL-like solution. — Andreas
– Andreas, Commented May 29, 2011 at 18:56

juanchopanza · Accepted Answer · 2011-05-30 06:40:33Z

6

std::arrays of different sizes are different types, so I cannot see any way to do what you want. But what if you return the begin() and end() const iterators to whatever container you hold internally, or an small range object containing both? That way you decouple the size of the container from the interface, leaving it to the implementation.

EDIT: Just to clarify, in order to hide the data storage representation (in this case, size of the std::array), you will need your own iterator class for face. This is easy to implement in terms of pointers since for each face specialization you know the size, begin and end of the underlying data structure. But you cannot directly use the std::array's begin() and end() in the interface, obviously.

Example:

This is a quick and dirty example illustrating how to implement part of the forward iterator behaviour using pointers. I use the virtual base class and one of the implementations from OP as starting point. I have also omitted all constructors, assignment operators, etc. It also assumes a class Edge (presumably a 2D or 3D point?).

class face {

public:

  typedef Edge* iterator;
  typedef const Edge* const_iterator;

  virtual iterator begin() = 0;
  virtual const_iterator begin() const = 0;
  virtual iterator end() = 0;
  virtual const_iterator end() const = 0;
  virtual size_t size() const = 0;

  virtual ~face() {};

};

class triangle : public virtual face {

public :
  virtual iterator begin() {return m_edges.begin();}
  virtual const_iterator begin() const {return m_edges.begin();}
  virtual iterator end() {return m_edges.end();}
  virtual const_iterator end() const {return m_edges.end();}
  virtual size_t size() const {return m_edges.size();}

private:
    std::array<Edge, 3> m_edges;

};

edited May 30, 2011 at 6:40

answered May 29, 2011 at 8:36

juanchopanza

228k35 gold badges421 silver badges493 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Andreas Over a year ago

This seems to be an appropriate solution. However, I thought that there may be a "nicer" solution, i.e., some array size independent iterator already implemented. Anyway, thanks a lot!!

juanchopanza Over a year ago

@Andreas, I added a simple example, just to give an idea of a simple implementation. Please treat it with caution, it was done in haste!

Sarfaraz Nawaz · Accepted Answer · 2011-05-29 08:42:52Z

std::array doesn't seem to be a solution here, since get_vertices is a pure virtual function, that means, you would want to access it using pointer (or reference) of base class type. And if you use std::array, you've to provide an integral value as second argument to std::array class template, which is possible, if you make face a class template, something like this:

template<size_t N>
class face {
    virtual std::array<ptr, N>& get_vertices(void) const = 0;
};
class triangle : public face<3>{
    //...
    std::array<ptr, 3>& get_vertices(void) const { return vertices; };
};
class quadrilateral : public face<4> {
    //...
    std::array<ptr, 4>& get_vertices(void) const { return vertices; };
};

But this causes triangle and quadrilateral to have different base classes : face<3> and face<4> are two different classes. That means, you cannot mix triangle and quadrilateral together, say in a standard container, and you cannot access get_vertices using pointers of the same base class type, since there is no single base class now. Each derived class has its own base class.

So the solution is this:

class triangle : public face {
private:
    std::vector<ptr> vertices;
public:
    triangle() 
    {
           //it ensures that you've a vector of size 3, no more no less 
           vertices.reserve(3); 
    }
    std::vector<ptr>& get_vertices(void) const { return vertices; };
};

Similarly, you can do in quadrilateral :

    quadrilateral() 
    {
           //it ensures that you've a vector of size 4, no more no less 
           vertices.reserve(4); 
    }

Now your vector doesn't arbitrarily resize itself to a greater size than it actually needs, because you've define the capacity by calling reserve(), and you'll add more items than its capacity. No resizing occurs.

As in my comment above, this does only save me from "costly" reallocations, but not from the induced overhead of the std::vector.

Collectives™ on Stack Overflow

Reference to std::array of different sizes instead of std::array in a base class

2 Answers 2

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related