3

the C++ STL vector has a lot of decent properties, but only works when the size of each item is known at run-time.

I would like to have a vector class that features dynamic item size at run-time.

Background: My items consist of a sequence of integers and doubles; a sequence which is only known at run-time. It would suffice to have the vector be given the size of each item at run-time.

I am aware of possible workarounds, but these tend not to reflect the underlying idea of the algorithm, which is always a bad thing with regards to maintainance. Are there classes which provide such a convenience and work as efficient as one might expect?

EDIT:

This is not about item sizes varying throughout the array. It has nothing to do with that. It is at run-time deciding how large the items in the array are; i.e. a (very) weak form of dynamic typing, in contrast to static typing as used with templates.

Hence the initialization of the object should look like that:

DynamicVector V( lengthofvector, sizeofelement );

An application are simplicial meshes. The object $V$ contains items of fixed size or "type", each consisting of integers for the topological information and doubles for some geometric information. There might even come booleans into play, but this is irrelevant so far.

shuhalo
  • 5,732
  • 12
  • 43
  • 60
  • 1
    Sounds like you want a vector of vectors. There is no way in C++ of having a collection of objects of different sizes. –  Jun 09 '11 at 14:41
  • 1
    I take it that a vector of pointers is one of the workarounds you don't want to use? – badgerr Jun 09 '11 at 14:41
  • @Neil that looks like an answer to me. – andrewdski Jun 09 '11 at 14:43
  • What do you mean by `dynamic item size`? Is the item itself a container, or you mean `sizeof(item)` would vary? – Nawaz Jun 09 '11 at 14:45
  • So each item in your vector is a sequence? Or the vector contains a sequence of either integer or double items? How efficient might one expect such a data structure to be? – gregg Jun 09 '11 at 14:49
  • How does the typical code that uses this "DynamicVector" look like? Is it templated over the type? – Macke Jun 10 '11 at 14:39

9 Answers9

4

The problem is that if you don't have a way to store the size of each item in the vector you'll never be able to get the data back out.

What about just storing ALL the items as double? This drastically simplifies things.

Alternately you could consider boost::variant.

EDIT: But really can you explain further why you want to store two different types in the same sequence? That can sometimes indicate that the underlying design needs further thought.

Mark B
  • 95,107
  • 10
  • 109
  • 188
1

You could use a vector of pointers to your sequence object - preferably smart pointers, to simplify memory management in the vector.

Steve Townsend
  • 53,498
  • 9
  • 91
  • 140
1

If its just a sequence of int and double, then you can simply use:

 std::vector<double> sequence;

and then insert int and double into it. However, this approach doesn't keep track of the type of the items. If the type is critical for you, then probably the following may help you:

struct item
{
  union 
  {
     int i;
     double d;
  } data;
  char type; //store 0 for int, 1 for double;
};

std::vector<item> sequence;

Of course, this approach costs you atleast one extra byte per item, for storing the type of the item. You may want to use #pragma pack techniques to squeeze the extra padding.

Or even better would redesigning your code such that you've two sequences instead of one:

std::vector<int>     intSeq;
std::vector<double>  doubleSeq;
Nawaz
  • 353,942
  • 115
  • 666
  • 851
  • 2
    It may, and almost always will, be more than one extra byte: you forgot to take the padding into account. –  Jun 09 '11 at 14:55
0

vector represent a contiguous array in memory. This is efficient, since it can use pointer arithmetics to directly access elements by index. But doing that imply all elements having the same size, and to know this size before building the vector.

For your needs, either use a vector of pointers to elements, of a double linked list. vector of pointers is almost as fast as vector. It only needs one mode deference.

If your integers and doubles are the same size (e.g. 64 bits), you could use an union to access each item either as an integer or as a double. But you'd need a way to know what each element is supposed to be.

Charles Brunet
  • 21,797
  • 24
  • 83
  • 124
0

If you don't want to resort to workarounds, I think that you should think about an abstraction of those "dynamic-sized items". It should be designed having in mind that it must be used inside a STL vector (then some requisites have to be guaranteed), such that you can finally write something like:

std::vector<DynamicSizedItem> myVector;
Simone
  • 11,655
  • 1
  • 30
  • 43
0

Create a class that contains three vectors: one for ints, one for doubles, and one that has an entry for each item to tell the type of the corresponding item and its index in the corresponding vector.

Permaquid
  • 1,950
  • 1
  • 14
  • 15
0

Use std::vector where item is a wrapped smart pointer. The "item" class make a pointer look like a plain value :

class item {
private:
    boost:unique_ptr<base> p;
public:
    // ...
    public item(item that);

    public int someFunction() {
       // Forwarded
       return p->somefunction();
    }
};

class base {
    virtual ~base();
    // This is needed in order to implement copy of the item class
    virtual base* clone();
};

public item::item(item that) : p(that.p.clone()) {}

class some_real_type() : public base {
   // ....
}
ysdx
  • 8,889
  • 1
  • 38
  • 51
0

I think the best way forward (in terms of performance and maintaiability) is a workaround, where you wrap std::vector and std::vector in two classes that interhit a common base class with an appropriate interface.

If you want it dynamic at runtime, that's how to do it properly. It'd also help you write efficient code for processing each item, as well as accessing each element simply (but slowly).

Macke
  • 24,812
  • 7
  • 82
  • 118
0

I've seen this question before! Is there an STL container that stores an array of elements in contiguous memory where the element size is specified at runtime?

Guy wanted an "interleaved vector" (his word) that would hold dynamically sized objects, defined by a map of member types and offsets:

typedef Toffset uint; //byte offset;
typedef Ttype   uint; //enum of types
typedef std::pair<Toffset,Ttype> member;
typedef std::unordered_map<std::string, member> memberdefs;

And I came up with a (untested) class to handle that. The full code is in the link, but prototypes are: 

class interleaved_vector {
    const char* buffer;
    size_t count;
    size_t size;
    std::shared_ptr<memberdefs> members;
public: 
    class dynamic_object {
        const char* buffer;
        std::shared_ptr<memberdefs> members;
        friend interleaved_vector;
        dynamic_object(const char* buffer_, std::shared_ptr<memberdefs> members_);
        dynamic_object& operator=(const dynamic_object& b) = delete;
    public:
        dynamic_object(const dynamic_object& b) ;
        template <class T>
        T get(const std::string& member) const;
        template <>
        T* get<T*>(const std::string& member) const;
        void* operator[](const std::string& member) const;
    };
    interleaved_vector(const char* buffer_, size_t count_, size_t size_, const memberdefs& members_);
    dynamic_object get(size_t index) const;
    dynamic_object operator[](size_t index) const;
    size_t size();
};

As a warning: it does rely on some behavior that I think is undefined, and in general, is a bad idea. Go with a vector of pointers.

Community
  • 1
  • 1
Mooing Duck
  • 64,318
  • 19
  • 100
  • 158