Container where one dimension is constant and one is variable

Question

I have a system where I need to get "codes" for specific positions. There is a constant number of positions, 1 to 40, however, each position can have different number of codes (from 2 to 20). The container is constant, it needs to be defined, then is just used to look up positions for the rest of the program.

For example, I need to be able to do something like myCodes.at(position3) and get {1, 3, 9, 23, 52} and myCodes.at(position7) and get {23, 52}

So, the outer container is of constant size, but the inner container can vary in size from 2 to 20. The way I know how to do this is using arrays, and just make the second dimension the max possible size (20): const int myCodes[40][20], then just "pad" the inner array with extra 0's.

However, this feels really wasteful, especially because many of the inner arrays would only be holding 2 elements. I am also working on learning C++11, so I would prefer a "modern" solution if there is one.

score 3 · Accepted Answer · answered Nov 18 '12 at 01:03

3

This is likely what you want:

std::array<std::vector<code>, const_size>

The outer is constant and the inner is dynamic.

Having both be constant and using padding will be faster, but much uglier and so don't try it at first. 18*20 unused ints is not much of a waste on modern hardware.

answered Nov 18 '12 at 01:03

Pubby

51,882
13
139
180

My only concern with this approach is my compiler doesn't support initializer lists, so I'll have to do something hacky like [this](http://stackoverflow.com/questions/2236197/c-easiest-way-to-initialize-an-stl-vector-with-hardcoded-elements). Not a problem with the answer though, thank you – Nov 18 '12 at 01:08
1

Does your compiler support varardic templates? A `make_vector(...)` doesn't seem hard to write in that case. – Yakk - Adam Nevraumont Nov 18 '12 at 01:17

score 2 · Answer 2 · answered Nov 18 '12 at 01:14

For an insane approach, a tuple of std arrays of varying size plus an array of pairs of iterators to the start/end of the arrays. The first results in a non uniform contiguous block if memory, the second gives you uniform range based access to it. In theory the second is computable on the fly, but I would just cache it.

The code to turn the tuple of arrays into an array of pairs would be fun to write.

Well really I would do the previous answer of an array of vectors or even a vector of vectors. But this technique demonstrates how batshit you can get with modern C++11.

I really like the idea. I think I will go with the previous answer, but I'm going to give this a try for fun. Thanks — , Nov 18 '12 at 01:16

score 2 · Answer 3 · answered Nov 18 '12 at 01:25

2

You should use either an array of vectors or an array of lists.

std::array<std::vector<MyType>, const_size>

std::array<std::list<MyType, const_size>

Both are structures that are static in one dimension and dynamic in the other.

answered Nov 18 '12 at 01:25

evanmcdonnal

46,131
16
104
115

list, really? The OP did not ask for something that can be spliced quickly – Yakk - Adam Nevraumont Nov 18 '12 at 01:31
@Yakk he asked for something that can grow dynamically, lists are dynamic. A list satisfies all the requirements of the OP. – evanmcdonnal Nov 18 '12 at 01:39
Except it is a list, which is a container you should only use on pain of splice and constant inserts in the middle (more often than iterating). Advising someone to use a list is by default horrible advice. – Yakk - Adam Nevraumont Nov 18 '12 at 01:49
@Yakk says the guy who suggested he write his own container that is just plain stupid. – evanmcdonnal Nov 18 '12 at 01:52
http://yaserzt.com/blog/archives/615 -- look at this before using or recommending lists. – Yakk - Adam Nevraumont Nov 18 '12 at 02:08
@Yakk That is a good read, although I was already aware of the results. Keep in mind this user is going to have less than 21 objects per vector and the performance is equal for up to 10,000 objects. – evanmcdonnal Nov 18 '12 at 03:19

Container where one dimension is constant and one is variable

3 Answers3