3

I'm in need for some guidance regarding a question from a programming languages course I'm taking.

We need to come up with a way to implement an array class in C++, so that accessing it's element is statically checked for overflow. We are not to use C++11 (static assertion) nor any other black-box solution - this is a theoretical question, not something I need for coding purposes.

we did get a strong hint in the lecture slides :

" it is impossible to detect overflow of array indices when indices are of type integer – not if the type of the indices corresponds to the array size (which must be part of the type of the array). "

I thought about using fixed-length (array size) string for indices, but other than thinking about the option I really did not get much :(.

Clarification: OK, this has got some confused replies to it, probably because I was unclear - So I will re-emphasize:

  1. "Statically" means "at compile time". The compiler should alert the user of the overflow (Warning/Error..). Not runtime!
  2. Read the "hint" given to us - it's to be used. specifically, the program may NOT check for bounds! specifically the at() method of arrays in c++ is not to be used or emulated.

In light of all this what I am thinking they want is some sort of transformation int->(Indices type) that somehow fails or computes wrong values for these indices in case the array is overflowed.

Hope that is clearer now. Thank you's

9
  • If I'm understanding you correctly (which I'm probably not) you can get a good hint/clue from std::vector's at() method if you want to create an array class that has a kind of built-in bounds-checking. It's supposed to throw an exception if the user tries to access an element that is out of bounds. I'm not going to bother providing you code but still, I hope it helps as a guideline Commented Jun 25, 2013 at 21:49
  • It sounds like he's asking you to reinvent std::array::at? Commented Jun 25, 2013 at 21:49
  • 1
    I think your question need rephrasing. A class can not staticly check itself. And while in theory it's possible to make functions with static checks, I doubt they would be any useful. Probably you wanted to ask something else, like runtime bounds checks? Commented Jun 25, 2013 at 21:50
  • what do you mean by "statically checked"? do you want compilation to fail? or do you just want to determine it at compile time and indicate the out-of-bounds at runtime? Commented Jun 25, 2013 at 21:54
  • 1
    Maybe he means like this? Commented Jun 25, 2013 at 22:01

1 Answer 1

2

Maybe he intends for you to index the array based on a type where the value is part of the type, such as std::integral_constant<int, value>. Using this, the size can be checked at compile time. However, without static_assert, it's hard to think of simple ways to assert that one constant is smaller than another.

Here, I use the trick of comparing if the index is less than the size, converting that to an integer (0 if it's out of bounds, or 1 otherwise), multiplying that by two and subtracting one, giving either (-1 for out of bounds, or 1 for valid), and then making an array of that size. This causes a compilation error if the index is out of bounds, and is optimized out if the index is valid.

#include <type_traits>

template<class T, int count>
struct array {
    array() : data() {}

    template<int N>
    T& operator[](std::integral_constant<int,N> index) {
        //compiler error if index is too small
        char index_is_too_large[(N<count)*2-1]={}; 
        index_is_too_large[0] = index_is_too_large[0]; 
        //second line makes the compiler ignore warnings

        return data[N];
    }
private:
    T data[count];
};

#include <iostream>
int main() {
    array<float, 3> thingy;

    std::integral_constant<int, 2> index2;
    std::cout << thingy[index2] << '\n';

    std::integral_constant<int, 3> index3;
    std::cout << thingy[index3] << '\n'; //COMPILER ERROR ON THIS LINE
}

This seems quite advanced for the restrictions placed on you, I think it's more likely you misunderstood your professor somewhere along the line.

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

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.