c++ Segmentation Fault using struct pointer

Question

I have a class called Dictionary that contains a key-value pair, a pointer to this key-value pair, and an int that holds the size of the dictionary.

template<typename K, typename V>
class Dictionary
{
public:

V& operator[](K key);

private:

struct KeyValue
{
    K key;
    V value;
}; //the key-value pair struct

KeyValue* array; //pointer to an array of items (the key-value pairs)

int size; //size of the dictionary (i.e. the array size)
};

I am trying to overload the [] operator for this class and when I do so, I get a segmentation fault error

template<typename K, typename V>
V& Dictionary<K,V>::operator[](K key){
  for (size_t i = 0; i < size; i++) {
    if (key == array[i].key) {
      return array[i].value;
    }
  }
  array[size].value = 0;
  size++;
  return array[size-1].value;
}

I beleive that the seg fault is occuring in this line

array[size].value = 0;

However, I don't know exactly why it's happening. Any help is greatly appreciated. Thanks!

Sounds like you are reimplementing std::map (badly). Why would you do that rather than just using std::map? — Jesper Juhl
– Jesper Juhl, Commented Nov 16, 2019 at 15:11
Just because the program crashes on this line doesn't mean that's where the problem is. C++ does not work this way. The problem can be anywhere in your program, which is why stackoverflow.com's help center instructs you to provide a minimal reproducible example, otherwise it is unlikely that anyone will be able to help you. See How to Ask for mroe information. — Sam Varshavchik
– Sam Varshavchik, Commented Nov 16, 2019 at 15:12

NicholasM · Accepted Answer · 2019-11-16 15:16:10Z

5

When an array in C and C++ has N elements, the valid indexes are: 0, 1, 2, ... N-1. In contrast N is not a valid index: it is past the end of the array.

In this particular case, the last element of array is array[size - 1]:

array[0]         // first element
array[1]         // second element
// ...
array[size - 2]  // second-to-last element
array[size - 1]  // last element

array[size]      // error: beyond the last element

Using array[size] is accessing beyond the end of the array and results in a segmentation fault.

In the bigger picture, if you need to add elements to an array and you are out of space in the array, you would need to allocate a new array with larger size, and move (or copy) elements from the old array to the new array.

This is "reallocating", and this is what std::vector<T> does when it grows beyond its current capacity.

You may want to replace your use of a dynamic array with an std::vector<KeyValue>. That would let the std::vector take care of these operations.

edited Nov 16, 2019 at 15:16

answered Nov 16, 2019 at 15:10

NicholasM

4,7441 gold badge24 silver badges49 bronze badges

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

4 Comments

Sam Varshavchik Over a year ago

This assumes that array was actually alocated for size elements, and there aren't any additional reserve capacity (like what std::vector does). There's nothing in the question to support this assumption. The question is unanswerable without a minimal reproducible example.

Zachary Rudebeck Over a year ago

I have also tried incrementing size first and then calling array[size-1] however this also results in a segmentation fault

NicholasM Over a year ago

@SamVarshavchik, that is correct, I made that assumption based on the comment in the questioner's code: //size of the dictionary (i.e. the array size)

NicholasM Over a year ago

@ZacharyRudebeck, the segmentation fault is expected in that case: the array index is equal to the size of the array, which means it is an invalid index. Just incrementing the variable size does not increase the size of the array. You need to allocate a new array with a larger size, or use std::vector which takes care of this for you.

Collectives™ on Stack Overflow

c++ Segmentation Fault using struct pointer

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related