Array like data structure with negetive index in C++

Question

I need a structure to keep track of presence of some items. I just wanted to take an array a0....aN and mark the elements as a[0]=0,a[1]=0,a[2]=1........(a[i]=1 if the element is present,a[i]=0 if element is not present). But the items range from -1000 to +1000. It can be done by putting the negative range from 1001 to 2000. I needed to know if there is any other data structure in c++ that can work like array and with negative indexes. Thank you for your time.

Answer 1

map is used for this only, to have key/index of any basic/user-defined data type. See - http://www.cplusplus.com/reference/map/map/

Example for your case:

#include <iostream>
#include <map>
#include <string>

int main ()
{
  std::map<int, int> mymap;

  mymap[-1]=1;
  mymap[-2]=0;
  mymap[-3]=1;

  std::cout << mymap[-1] << '\n';
  std::cout << mymap[-2] << '\n';
  std::cout << mymap[-3] << '\n';

  return 0;
}

Example for char:

#include <iostream>
#include <map>
#include <string>

int main ()
{
  std::map<char,std::string> mymap;

  mymap['a']="an element";
  mymap['b']="another element";
  mymap['c']=mymap['b'];

  std::cout << "mymap['a'] is " << mymap['a'] << '\n';
  std::cout << "mymap['b'] is " << mymap['b'] << '\n';
  std::cout << "mymap['c'] is " << mymap['c'] << '\n';
  std::cout << "mymap['d'] is " << mymap['d'] << '\n';

  std::cout << "mymap now contains " << mymap.size() << " elements.\n";

  return 0;
}

Answer 2

You an create your own data structure which supports -ve indexes. Just add an offset to the indexs while storing them in an array.

class MyArray {
    int *arr;
    public:
    MyArray(int offset) {
        arr = new int[2*offset]; // size must to double the offset
    }
    ~MyArray(){
        delete arr;
    }
    void add(int index, int val) {
        arr[index + offset] = val;
    }
    void get(int index) {
        return arr[index + offset];
    }
}

Then you can just use your class to add and get elements with any index.

MyArray arr = MyArray(1000); // pass max -ve index as offset
arr.add(10, -150);
cout << arr.get(100);

Answer 3

I need a structure to keep track of presence of some items.

If what you want is set semantics, use a set data structure. No need to implement a custom array wrapper. You can use a std::set (or std::unordered_set) for that. Remember that "premature optimization is the root of all evil".

Insert the values that are there, leave out the values that are missing. No need to worry about negative indices. You can use the methods std::set::find() or std::set::count() to check the presence of an item. Have a look at the documentation to find some example code.

If you later find it's a performance critical optimization, you can replace a std::set<int> with a data structure that you wrote yourself on the basis of an array of bits anytime. If it's not, doing so prematurely might turn out to be an unnecessary source of unexpected errors and a waste of time.

For reference:

• http://en.cppreference.com/w/cpp/container/set
• http://en.cppreference.com/w/cpp/container/unordered_set
• http://en.cppreference.com/w/cpp/container/set/find
• http://en.cppreference.com/w/cpp/container/set/count
• How to check that an element is in a std::set?

Answer 4

Most efficient approach will be just shifting your array indexes so all of them are non-negative. In your case just use a[i+1000] and it will be sufficient.

If you really need to use negative indexes it is also possible. C / C++ calculates memory address of array element using address of table and then adding index value to it. Using negative numbers just points to memory area placed before your table (which is not you normally want).

int a[2001];
int *b = &a[1000];
int x = b[-1000]; // This points to 1000 places before b which translates to a[0] (valid place)

Another approach will be using containers. Then any number can be translated to string and stored in proper container.

Answer 5

I think that the answer of @Rajev is almost fine. I have just replaced a plain array with a std::vector. Thus, the memory management is secure and copying and moving is easy.

template <typname T>
class MyArray {
  private:
    std::vector<T> arr;
  public:
    MyArray(int offset) {
        arr.resize(2*offset); // size must to double the offset
    }

    void set(int index, int val) {
        arr[index + offset] = val;
    }

    void get(int index) {
        return arr[index + offset];
    }
}

You can expand this further by overloading the operator [] of MyArray.