Managing a container of iterators (specifically, a vector of iterators of a list)

Question

I'm trying to have a vector of iterators of a list, that will allow me to access or erase a list element in O(1). The use case is on one hand to use the list to define priority (in front() to have the most prioritized item while in back() to have the least prioritized item), but on the other hand, to get a direct access to every list node (so that I can move any item from the middle of the list to back() - for this I need to erase it from the middle of the list). I'm aware that this is probably not possible, but I really want to make the least changes to have the code running, instead of writing an awkward code (e.g. using "pair") to gain the same functionality. I've read posts like: Keeping vector of iterators of the data and Why can't I make a vector of references? And I understand that its probably not possible the way I want it, but I'm sure that its possible to do with least changes.

Here is a sample program:

#include <iostream>
#include <list>
#include <vector>
#include <functional>

using namespace std;

typedef struct _data
{
    int d;
} tData;

typedef list <tData *> tListTest;
typedef vector <tListTest::iterator> tVecTest;

int main()
{
    tListTest mylist;
    tVecTest myvec;
    tData *myData;
    int i;

    for (i=0; i<10; i++) {
        cout << "Iteration " << i << endl;
        cout << "Stage 1" << endl;
        myData = new tData;
        cout << "Stage 2" << endl;
        myData->d = i;
        cout << "Stage 3" << endl;
        tListTest::iterator listIter = mylist.insert(mylist.end(), myData);
        cout << "Stage 4" << endl;
        myvec[i] = listIter;
        cout << "Stage 5" << endl;
    }

    tListTest::iterator listIter = myvec[7];
    cout << "Deleting " << (*listIter)->d << endl;
    delete *listIter;
    mylist.erase(listIter);

    return 0;
}

here is the output:

Iteration 0
Stage 1
Stage 2
Stage 3
Stage 4
Segmentation fault (core dumped)

I've tried to change the vector definition to:

typedef vector <reference_wrapper<tListTest::iterator>> tVecTest;

And the assignment to:

myvec[i] = ref(listIter);

and it didn't help.

Any idea how can I make this code running? I'm pretty sure I'm almost there.

Thanks in advance

`delete *listIter;` ?!? You dont `delete` what you didnt `new` — 463035818_is_not_an_ai, Jan 22 '18 at 09:49
...and `myvec[i] = listIter;` is out of bounds. Sorry, but it isnt really clear what you want to achieve, and I am afraid your code is more than a small step away from achieving it — 463035818_is_not_an_ai, Jan 22 '18 at 09:51
I assume you have detailed comparative performance metrics that provide a direct justification for writing such error-prone, memory leaking, unidiomatic, and complex code. — Aluan Haddad, Jan 22 '18 at 09:53
just realized that by the time you delete `*listIter` it points to something created via `new`, however why you do this I dont understand... — 463035818_is_not_an_ai, Jan 22 '18 at 09:54
You don't need to `typedef struct` in C++. All that does is double the number of names of your type. — Caleth, Jan 22 '18 at 10:11

Violet Giraffe · Accepted Answer · 2018-01-22T16:36:58.427

0

A vector has no elements by default, nor any memory allocated to hold the elements. Your line myvec[i] = listIter attempts to access the element i that hasn't been allocated. Change the declaration to tVecTest myvec(10) to pre-allocate 10 elements. Or better yet, change myvec[i] = listIter to myvec.push_back(listIter).

edited Jan 22 '18 at 16:36

answered Jan 22 '18 at 10:03

Violet Giraffe

32,368
48
194
335

Hi, thanks a lot for the answer Violet - the first remark about the vector pre-allocation was very useful. I was 100% positive that its done automatically, so I didn't pay any second thought to this point. Regarding the second remark about **listIter**, note that there are 2 of them - one inside the for loop, and one outside. Since its a tester, I didn't invest much time in pretty coding, but the code compiles an run. – user9250533 Jan 22 '18 at 13:17
@user9250533: good point, I was being inattentive, sorry for the confusion. Glad my answer was still partially useful. – Violet Giraffe Jan 22 '18 at 16:39

Managing a container of iterators (specifically, a vector of iterators of a list)

1 Answers1