CODEWITHSUNDEEP
c++debuggingaddress-sanitizer
cpchung
cpchung

Reputation: 844

what are good ways to debug c++ runtime error?

What are good ways to debug the following problem?

I tried to use address sanitizer and set break point in Clion running the code in ubuntu. None of them provide helpful debug message to locate the problem.

SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_vector.h:1043:34

The following code coming from this problem can reproduce the runtime error:

https://leetcode.com/problems/maximum-length-of-pair-chain/

#include <bits/stdc++.h>

using namespace std;


class Solution {
public:
    int findLongestChain(vector<vector<int>> &pairs) {


        int n = pairs.size();
        if (n == 0) return 0;
        sort(pairs.begin(), pairs.end(), [](vector<int>& a, vector<int>& b) { return a[1] <= b[1]; });


        int lastRight = pairs[0][1];
        int res = 1;
        for (int i = 1; i < n; i++) {
            if (pairs[i][0] > lastRight) {
                res++;
                lastRight = pairs[i][1];
            }

        }

        return res;

    }
};

int main() {

    vector<vector<int>> pairs = {{-994,-938},{19,592},{-232,-209},{788,937},{772,838},{741,801},{-229,747},{242,907},{-592,730},{-517,996},{380,693},{98,662},{-760,169},{-844,541},{-535,461},{-544,138},{-799,390},{-998,-965},{680,1000},{-73,698},{-955,51},{-909,-891},{-61,558},{217,357},{-721,108},{351,421},{608,903},{449,615},{-31,165},{979,998},{-849,-69},{627,974},{-880,918},{-766,209},{178,695},{266,917},{518,763},{-183,665},{878,996},{77,430},{-906,-403},{136,594},{-694,-525},{806,845},{-445,8},{-813,687},{-730,247},{909,925},{-360,741},{-418,-199},{-111,498},{367,873},{341,664},{-27,14},{-450,814},{-405,-117},{249,932},{703,864},{141,888},{278,646},{-851,-804},{-956,-819},{192,686},{-779,69},{-803,-502},{619,969},{-973,14},{-659,-136},{340,951},{-31,137},{-801,-701},{189,323},{107,615},{403,918},{452,753},{-224,-6},{697,959},{312,787},{-862,-398},{634,971},{-645,-148},{464,613},{570,592},{710,910},{-422,-139},{-148,360},{572,716},{905,909},{237,709},{-636,274},{-759,-693},{-937,112},{796,879},{-927,857},{-861,-767},{898,946},{667,719},{-234,-94},{259,911},{-870,-125},{-378,-138},{593,712},{-572,-219},{160,387},{-72,480},{870,943},{-182,669},{-713,-151},{-859,-524},{108,371},{-861,786},{17,579},{205,644},{-527,312},{752,933},{113,896},{-164,100},{-128,961},{-998,986},{551,757},{388,990},{-211,530},{853,886},{-174,762},{700,912},{-708,-655},{-414,793},{362,828},{556,850},{-501,-437},{39,215},{-311,-115},{-798,122},{965,995},{-84,246},{-469,-95},{581,841},{-625,-430},{347,561},{-969,-43},{362,412},{-829,850},{-17,571},{-763,784},{-591,776},{700,877},{619,855},{-222,895},{-340,436},{-651,-9},{-836,-361},{458,987},{653,975},{-105,-66},{261,924},{715,803},{107,235},{809,958},{17,46},{-856,140},{-311,835},{-185,146},{-348,200},{338,662},{170,495},{687,902},{-889,-622},{-886,-117},{-11,679},{-496,196},{-314,-242},{-238,194},{510,658},{237,826},{-977,505},{-326,311},{-207,416},{563,979},{-526,536},{698,843},{522,829},{135,505},{-959,253},{19,258},{-945,-105},{-229,906},{798,978},{-857,-452},{-56,320},{309,649},{143,328},{-195,-8},{-464,320},{-172,13},{68,332},{-713,-74},{936,966},{276,860},{-425,334},{-461,730},{852,938},{-828,-818},{-562,-6},{-722,723},{945,975},{165,989},{-629,274},{484,486},{977,995},{-378,263},{3,836},{-661,-558},{-384,839},{-783,237},{719,795},{-52,768},{521,949},{-235,107},{846,885},{-257,159},{-447,461},{202,550},{902,977},{558,983},{830,882},{-174,631},{-424,926},{248,521},{107,173},{97,738},{-593,-441},{302,435},{703,792},{-994,308},{-543,926},{-794,398},{936,984},{-422,-107},{-122,982},{834,836},{-694,63},{341,755},{442,672},{-866,647},{545,978},{352,700},{73,635},{-201,-123},{-237,140},{-395,205},{921,968},{-806,166},{-951,256},{436,863},{-996,-435},{853,907},{-999,-686},{443,506},{788,827},{-133,238},{-630,284},{934,939},{-385,536},{387,637},{547,565},{919,927},{-271,742},{-263,141},{-359,712},{-323,-18},{494,674},{348,526},{-537,-437},{911,935},{936,953},{15,829},{-666,874},{-808,496},{-393,366},{957,974},{681,961},{-747,-420},{-713,-213},{445,782},{900,952},{348,562},{-929,957},{622,667},{725,837},{177,931},{959,969},{-156,466},{680,966},{-869,-822},{313,785},{-627,469},{-313,518},{-626,498},{29,754},{83,386},{-502,506},{-672,647},{-507,47},{393,553},{293,312},{-524,-100},{325,350},{-817,31},{-421,695},{-400,227},{-387,-9},{-556,412},{732,763},{-18,394},{-478,-370},{-326,-305},{254,997},{-341,837},{-727,859},{349,451},{-335,202},{-540,-481},{186,272},{647,975},{-281,919},{284,758},{-500,58},{464,828},{479,628},{828,1000},{-500,-132},{-41,532},{734,995},{3,232},{-358,185},{669,807},{-524,501},{-240,608},{75,683},{833,923},{-454,917},{707,858},{322,651},{887,974},{63,263},{-705,462},{-606,366},{-792,-699},{5,315},{265,573},{-735,461},{632,755},{250,329},{861,915},{-93,577},{-107,-2},{164,313},{-222,72},{165,343},{600,639},{-954,-355},{682,700},{195,387},{263,649},{532,642},{732,919},{-321,-219},{423,701},{-2,638},{-697,591},{474,921},{266,481},{-80,51},{305,906},{-265,242},{896,963},{-930,120},{877,932},{453,599},{-851,486},{-571,-28},{-659,597},{-72,978},{-494,385},{686,797},{40,874},{-245,115},{23,680},{-950,34},{-763,558},{464,786},{-4,566},{-289,-102},{92,799},{628,887},{301,813},{355,414},{-452,865},{41,587},{816,983},{887,953},{-4,753},{-112,10},{12,554},{-1000,994},{-332,142},{653,965},{419,453},{612,687},{-205,877},{-931,-548},{-686,61},{371,944},{-740,837},{-622,196},{-604,-45},{913,957},{741,808},{355,470},{666,938},{-79,235},{53,126},{-250,5},{40,584},{806,975},{-29,416},{352,835},{-914,-733},{-171,809},{651,935},{-893,-364},{33,433},{506,856},{682,725},{-380,476},{-542,-135},{478,571},{-986,13},{871,947},{698,845},{-255,259},{-52,247},{-953,494},{920,964},{-996,622},{249,858},{243,739},{199,644},{467,862},{-262,-130},{754,908},{-408,990},{885,951},{978,996},{-506,740},{-437,536},{542,750},{695,891},{564,601},{-388,760},{257,908},{348,615},{558,989},{106,214},{-163,922},{396,788},{-980,-381},{-477,450},{-144,741},{551,770},{642,979},{-91,314},{595,840},{-391,349},{-751,541},{618,912},{9,213},{953,962},{-377,728},{-53,566},{-809,485},{-275,111},{221,658},{340,903},{-964,448},{279,554},{666,742},{-818,-13},{934,963},{-396,877},{320,472},{-257,-186},{536,927}};


    cout << Solution().findLongestChain(pairs);

}

edit: The original intention was to seek suggestions for debugging tools. Looks like such a tool does not exist for the example problem given.

Upvotes: 0

Views: 352

Answers (1)

PaulMcKenzie
PaulMcKenzie

Reputation: 35440

One issue is this:

sort(pairs.begin(), pairs.end(), [](vector<int>& a, vector<int>& b) 
 { return a[1] <= b[1]; });  // <-- Not a strict-weak-ordering.

The sort criteria must be a strict-weak-ordering. Any sort criteria that has <= or >= are always suspect of violating this rule. A violation of the strict-weak-order rule leads to undefined behavior.

The fix is to compare that the item is strictly less than the other.

sort(pairs.begin(), pairs.end(), [](vector<int>& a, vector<int>& b) 
 { return a[1] < b[1]; });

Please note:

If you're using Visual Studio, the debug runtime does this exact check for ordering violations like this. The comparison function is called twice, the first time with A,B order, and the second time with B,A order. The return values for each call are compared, and an assert() will occur if there is a violation.

Upvotes: 2

Related Questions