std::vector>: Debug assertion failed. C++ vector subscript out of range reserving memory

Question

What's wrong here?

std::vector<std::vector<int>> mSectionsSubsets;

int count = (int)powf(2, NUM_SECTIONS);

mSectionsSubsets.reserve(count);
for (int i = 0; i < count; i++) {
    mSectionsSubsets[i].reserve(NUM_SECTIONS);
}

On MSVC++ it says vector subscript out of range once I mSectionsSubsets[i].reserve(NUM_SECTIONS); at the first i = 0.

Now sure what's wrong and how to fix it.

`reserve` doesn't change the size of the vector. – n. m. could be an AI Jun 12 '19 at 15:13 — n. m. could be an AI, Jun 12 '19 at 15:13

Lightness Races in Orbit · Answer 1 · 2019-06-12T15:49:37.737

You wrote mSectionsSubsets[i] with i from 0 to count.

Every single one of those accesses is illegal, because mSectionsSubsets has no elements in it.

Reserving capacity, and resizing the vector, are two different things.

In this particular case, perhaps:

mSectionsSubsets.resize(count);
for (int i = 0; i < count; i++) {
    mSectionsSubsets[i].reserve(NUM_SECTIONS);
}

However, overall I would caution against vectors of vectors: they're poison for your cache and just generally not necessary when your dimensions are square.

How about a nice std::vector<int> instead? If you need count*NUM_SECTIONS elements, then simply do that. You can always create a two-dimensional façade for its indexes:

i = x + width*y

Cache of a quick mockup from the comments:

#include <iostream>
#include <vector>
#include <stdexcept>
#include <cassert>

// Like a vector<vector<T>>, but *better*!
template <typename T>
class RowList
{
public:
    RowList(const std::size_t rowCount, const std::size_t maxRowLength)
        : rowCount(rowCount)
        , maxRowLength(maxRowLength)
        , data(rowCount * maxRowLength)
        , utilisation(rowCount)
    {}

    std::size_t getRowCount() const
    {
        return rowCount;
    }

    std::size_t getMaxRowLength() const
    {
        return maxRowLength;
    }

    // UB if you give an invalid row number
    std::size_t getRowLength(const std::size_t rowNumber) const
    {
        assert(rowNumber < rowCount);
        return utilisation[rowNumber];
    }

    // UB if you give an invalid row number
    void clearRow(const std::size_t rowNumber)
    {
        assert(rowNumber < rowCount);
        utilisation[rowNumber] = 0;

        #ifdef NDEBUG
            // Debug builds only - make all the dead values -1
            // so we can maybe more easily spot misuse
            const std::size_t start = rowNumber*maxRowLength;
            const std::size_t end   = start + maxRowLength;

            for (std::size_t i = start; i < end; ++i)
                data[i] = -1;
        #endif
    }

    // UB if you give an invalid row number
    // throws std::out_of_range if the row is full
    void pushToRow(const std::size_t rowNumber, T value)
    {
        assert(rowNumber < rowCount);

        std::size_t& columnNumber = utilisation[rowNumber];
        if (columnNumber == maxRowLength)
            throw std::out_of_range("Row is full!");

        data[rowNumber*maxRowLength + columnNumber] = std::move(value);
        columnNumber++;
    }

    // UB if you give an invalid row or column number
    T& elementAt(const std::size_t rowNumber, const std::size_t columnNumber)
    {
        assert(rowNumber < rowCount);
        assert(columnNumber < utilisation[rowNumber]);

        return data[rowNumber*maxRowLength + columnNumber];
    }

    // UB if you give an invalid row or column number
    const T& elementAt(const std::size_t rowNumber, const std::size_t columnNumber) const
    {
        assert(rowNumber < rowCount);
        assert(columnNumber < utilisation[rowNumber]);

        return data[rowNumber*maxRowLength + columnNumber];
    }

private:
    const std::size_t rowCount;
    const std::size_t maxRowLength;

    std::vector<T> data;
    std::vector<std::size_t> utilisation;
};

template <typename T>
std::ostream& operator<<(std::ostream& os, const RowList<T>& matrix)
{
    const auto height = matrix.getRowCount();
    for (std::size_t y = 0; y < height; ++y)
    {
        const auto width = matrix.getRowLength(y);
        const auto remainder = matrix.getMaxRowLength() - width;

        for (std::size_t x = 0; x < width; ++x)
            os << matrix.elementAt(y, x) << '\t';

        for (std::size_t i = 0; i < remainder; ++i)
            os << "?\t";

        os << '\n';
    }

    return os;
}

int main()
{
    RowList<int> matrix(5, 5);

    matrix.pushToRow(2, 100);
    matrix.pushToRow(2, 101);
    matrix.pushToRow(4, 102);
    std::cerr << matrix << '\n';

    matrix.clearRow(2);
    matrix.pushToRow(1, 103);
    std::cerr << matrix << '\n';
}

g++ -std=c++17 -O2 -Wall -pedantic -pthread main.cpp && ./a.out
?   ?   ?   ?   ?   
?   ?   ?   ?   ?   
100 101 ?   ?   ?   
?   ?   ?   ?   ?   
102 ?   ?   ?   ?   

?   ?   ?   ?   ?   
103 ?   ?   ?   ?   
?   ?   ?   ?   ?   
?   ?   ?   ?   ?   
102 ?   ?   ?   ?

The second half of this answer contains very good advice indeed. Upped. — Bathsheba, Jun 12 '19 at 15:19
@Lightness Races in Orbit its not "square". I'm making the "edge" for the content I could reach, but some elements can be lower. What I need is not to allocate memory at runtime. So I game in advance, and clear() and push during the time (allowing the correct size during the process). — markzzz, Jun 12 '19 at 15:19
Exceptional C++ Chapter 1. Uses and Abuses of vector describes exactly that — Aykhan Hagverdili, Jun 12 '19 at 15:22
@markzzz In terms of memory consumption your container is square, so you may as well have a square container for real. You don't have to fill every "row". That'll help you _reduce_ usage too because you don't need `count`*vector machinery. Although I concede it sounds like you'll need some way to track row utilization. — Lightness Races in Orbit, Jun 12 '19 at 15:22
So: any way to reserve memory for both dimension keeping size() = 0? — markzzz, Jun 12 '19 at 15:24
@markzzz That makes no sense. push_back elements as you have them. Do you want holes in the vector? — Aykhan Hagverdili, Jun 12 '19 at 15:25
@Ayxan I need to have empty arrays, but allocated. So later I can push element without allocate memory. `size()` and `capacity()` are different things. — markzzz, Jun 12 '19 at 15:26
The only solution is to `.resize()` on both dimension and than `.clear()`... — markzzz, Jun 12 '19 at 15:27
As I said. Use a single vector. Map indices. Track utilisation if you need (a single other vector that contains "cells used" for each row will do it and still be cheaper in the long run, I think - but measure it to be sure!). You'd wrap this in a class. You can give it `clearRow(i)` and `pushToRow(i, val)` as much as you like :) (Well, up to the "max row length" with which you constructed it!) — Lightness Races in Orbit, Jun 12 '19 at 15:29
@Lightness Races in Orbit and what if I need to compare another `std::vector` vector with `mSectionsSubsets[i]`? Single vector will become a pain... at that point I manage raw pointers and manual indexes :P — markzzz, Jun 12 '19 at 15:33
@markzzz [Here's a simple example to get you started](https://coliru.stacked-crooked.com/a/5c1c058f0095f0db). That was 10 minutes. :) Writing something to compare rows with another vector would be pretty trivial. — Lightness Races in Orbit, Jun 12 '19 at 15:45
@LightnessRacesinOrbit that's what I'm looking for: http://coliru.stacked-crooked.com/a/6caba779e8c1b343 - Can you show to me why this "easy" code would be poison to cache? (or should I open a new question?) — markzzz, Jun 13 '19 at 07:15

score 2 · Answer 2 · answered Jun 12 '19 at 15:13

2

reserve doesn't set the size, it sets the capacity (i.e. it's more concerned with memory management). In your case mSectionsSubsets still has a zero size after mSectionsSubsets.reserve(count);.

Use resize to set the size of a vector.

Note that using .at rather than [] is safer insofar that in the former case, a runtime exception will be thrown, rather than the program behaviour simply being undefined.

answered Jun 12 '19 at 15:13

Bathsheba

231,907
34
361
483

However, at least in debug, and at least on VS, the OP's result shows how slowing your program down with `.at()` (particularly in a little loop like this) is not always called for! – Lightness Races in Orbit Jun 12 '19 at 15:17
@LightnessRacesInOrbit This might surprise you but in my shop I've banned `[]` unless you can prove that not using it would materially degrade performance. It survives in very few places. – Bathsheba Jun 12 '19 at 15:18
2

Why not just swap to Java and be done with it :P – Lightness Races in Orbit Jun 12 '19 at 15:24
@LightnessRacesinOrbit Not sure if I misunderstand, but in my edition of VS, `.at` has zero additional overhead in debug builds compared to release (it always checks ranges). `[]` only does the range check with `_ITERATOR_DEBUG_LEVEL != 0`. So I don't quite get what you mean with "at least in debug"... – Max Langhof Jun 12 '19 at 15:24
@LightnessRacesinOrbit: Java is an extremely pernicious language in which to write quantitative code (no operator overloading, `==` comparing references, integer caching). I know you're joking! – Bathsheba Jun 12 '19 at 15:24
@MaxLanghof That's exactly what I mean - in debug _you already get the benefits_ and _at the same cost_, but without ruining your release build with pointless checks ;) – Lightness Races in Orbit Jun 12 '19 at 15:26
@Bathsheba Only partially ;) – Lightness Races in Orbit Jun 12 '19 at 15:27
@LightnessRacesinOrbit This is the obligatory moment where I cry about MSVC changing the complexity of one of my algorithms from linear to square with debug iterator checks on because of a (large) vector of iterators... – Max Langhof Jun 12 '19 at 15:29
A confession: I also have all iterator checking switched off in my MSVC builds. In debug too. Too slow even on machines with liquid cooled processors. – Bathsheba Jun 12 '19 at 15:30
@MaxLanghof For the record, I would actually have voted against iterator checking if I could ;P – Lightness Races in Orbit Jun 12 '19 at 15:51
I just use lots of assertions in my member functions and don't expose containers :D – Lightness Races in Orbit Jun 12 '19 at 15:53

std::vector>: Debug assertion failed. C++ vector subscript out of range reserving memory

2 Answers2