vector problems

Hi,

The following piece of code compiles and runs as expected on Windows, but when I try and compile my program on FreeBSD, the following error occurs (I'm pretty new to STL)

Code:

---


void removeConnection(cnx_inf_vector::pointer p) {
        closesocket(p->sock);
        v_clients.erase(p);
}

---

The following errors are generated by gcc on FreeBSD 5.2:

Code:

---


main.cpp:258: error: no matching function for call to `std::vector<cnx_inf,
  std::allocator<cnx_inf> >::erase(cnx_inf*&)'
/usr/include/c++/3.3/bits/vector.tcc:105: error: candidates are:
  __gnu_cxx::__normal_iterator<_Tp*, std::vector<_Tp, _Alloc> >
  std::vector<_Tp, _Alloc>::erase(__gnu_cxx::__normal_iterator<_Tp*,
  std::vector<_Tp, _Alloc> >) [with _Tp = cnx_inf, _Alloc =
  std::allocator<cnx_inf>]
/usr/include/c++/3.3/bits/vector.tcc:117: error:
  __gnu_cxx::__normal_iterator<_Tp*, std::vector<_Tp, _Alloc> >
  std::vector<_Tp, _Alloc>::erase(__gnu_cxx::__normal_iterator<_Tp*,
  std::vector<_Tp, _Alloc> >, __gnu_cxx::__normal_iterator<_Tp*,
  std::vector<_Tp, _Alloc> >) [with _Tp = cnx_inf, _Alloc =
  std::allocator<cnx_inf>]

---

I realise that erase takes an iterator and not a pointer as a paramater, but this seems to work fine on Windows (Aren't iterators just pointers anyway?)

The reason I'm using pointers is to make the rest of my program a lot simpler, and I had trouble getting my code to run reliably using iterators without exceptions.

Any help greatly appreciated.

Many thanks,

Daniel Briley

I've managed to make it work by casting p to cnx_inf_vector::iterator, i.e

Code:

---

void removeConnection(cnx_inf_vector::pointer p) {
        closesocket(p->sock);
        v_clients.erase((cnx_inf_vector::iterator)p);
}

---

Is this safe?

Daniel

Iterators are not just pointers, at least not necessarily. It is quite possible that your STL implementation on Windows used pointers, and a lazy compiler allowed it. However, you don't know that your FreeBSD implementation does. A cast could cause major problems depending on the implementation.

The real question is why are you using pointers in this way? I don't see how this could make the rest of your program easier, especially considering the headaches you are already starting to experience.

If you really want to use pointers, use a vector of pointers instead of a vector of objects. Just make sure to manage the memory appropriately.

I had some trouble when using iterators because the code within the loop that iterates through the objects often erases some of the objects (by design). This was throwing everything out because the locations of the elements after the deleted one would all shift backwards.

I had some trouble getting my code to handle this properly, so I went for this approach instead:

Code:

---

        for (i = 0; i < v_clients.size(); i++) {
                cnx_inf_vector::pointer p = &v_clients[i];
                if (FD_ISSET(p->sock,fds)) {
                        r = recv(p->sock,buffer,80,MSG_PEEK);
                        if (r < 1) {
                                log_printf("[main] Connection to %s lost.\n",inet_ntoa(p->sin.sin_addr));
                        }
                        removeConnection(p);
                } else {
                        proc_data(p);
                }
        }

---

Yeah, I was sort of wondering the same thing about erasing from vectors. Since in my program I need to randomly access elements of the vector, I use the [] operator. But then, if (after processing some data) I decide that I need to remove that element, since erase() takes an iterator, I can't exactly random-access erase that element; I'd always just done vect.erase(&vect[index]); but, apparently, that isn't exactly foolproof. So how DO you do it?

**EDIT**
Actually yeah, codec's example is exactly what I was talking about, except with asynchronous sockets instead, so you can't exactly go through the vector with an iterator :cool:

It is an interesting question.

I'm starting to wonder whether there's much point in me using an STL container to store client information. Maybe I should go back to the old array[max_connections] style.

What do people think?

Daniel

No way! Just learn about how to use vectors properly. I recommend you buy and read "Effective STL" by Scott Meyers.

Ok, the erase. Iterators are invalidated by it, but so are pointers. That's why erase returns an iterator, it points to the element directly after the deleted one.
The correct loop to delete some elements in a container is:

Code:

---

for(container::iterator it = cont.begin(); it != cont.end();) {
  if(should_delete(*it)) {
    // Cleanup here.
    it = cont.erase(it);
  } else {
    ++it;
  }
}

---

If you don't have to do any cleanup (for example because use a class to wrap up your resources) you can use remove_if and erase to make this easier to code:

Code:

---

cont.erase(remove_if(cont.begin(), cont.end(), should_delete), cont.end());

---

Erase an element in a vector at a random location? Vector's iterators are random access, you can do arithmetics with them.

Code:

---

cont.erase(cont.begin()+index);

---

Stay with vectors, don't let yourself be scared back to arrays.

A regular array would be give the same problems in this situation. How do you "remove" something from an array? You wouldn't, you would probably just leave it there so as not to mess up the index of the later elements. You could do the same for the vector.

Here is an example of how I would remove something from a vector using erase. It goes through the vector one at a time, and if the entry meets a certain condition it is erased, otherwise it moves to the next one. Focus on the part in red.

Code:

---

#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>

int main()
{
    std::vector<int> intVec;
    for (int i = 0; i < 20; i++)
        intVec.push_back(i);

    std::vector<int>::iterator iterInt = intVec.begin();
    while (iterInt != intVec.end())
    {
        if ((*iterInt) % 3 == 0)
            iterInt = intVec.erase(iterInt);
        else
            ++iterInt;
    }

    std::copy(intVec.begin(), intVec.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
}

---

Notes:
Since erase returns an iterator pointing at the next element, you don't need to increment it with a "++". This was your main problem with your for loop. It increments i even when the element at i was erased. A quick fix would be to decrement i by one after erasing an element.

I prefer using the iterator syntax of the vector instead of the array syntax. This is mostly because I am familiar with it, but also because it provides more power. If you only use the array syntax you get stuck with the same problems you have with regular arrays.

I use intVec.end() in the loop condition, even though it is sometimes more efficient to save a copy of the end at first and just use that variable. In this case you can't do that with a vector (it is OK for a list) because when you call erase that invalidates the iterator.

I had an app where I needed to keep track of sockets. Instead of a vector (I actually rarely use vectors) I used a map. The key was the unique address of the client (its been a few years, but I think it was just IP and port encapsulated in a class). This may not be relevant for your situation, but it made it much easier to access a connection when I wanted to send data to a specific client.

[EDIT] - Oh, and what CornedBee said (faster than me).

Thanks for all the input guys, really appreciate it.

Dan

I've tried putting the code you suggested into my application so it uses iterators, and I'm having the same problem as when I tried to use iterators before.

It gets stuck in an infinite loop in the for loop when I test the server by connecting and then disconnecting 10 sockets.

The proc_data() function does not erase any elements, only the removeConnection() function does.

Here's my code:

Code:

---

cnx_inf_vector::iterator removeConnection(cnx_inf_vector::iterator it) {
        closesocket(it->sock);
        return v_clients.erase(it);
}

void read_socks(SOCKET sock_Serv, fd_set *fds) {

        char b;
        int r;
        unsigned int i;

        if (FD_ISSET(sock_Serv,fds)) {
                acceptConnection(sock_Serv);
                return;
        }
       
        for(cnx_inf_vector::iterator it = v_clients.begin(); it != v_clients.end();) {
                printf("for loop\n");
                if (FD_ISSET(it->sock,fds)) {
                        r = recv(it->sock,&b,sizeof(b),MSG_PEEK);
                        if (r < 1) {
                                log_printf("[main] Connection to %s lost.\n",inet_ntoa(it->sin.sin_addr));
                                it = removeConnection(it);
                        } else {
                                proc_data(it);
                                ++it;
                        }
                }
        }
}

---

Any ideas what's going on?

Daniel

That might be because the iterator advance is inside the the FD_ISSET if-statement. If it is false for an element, the loop won't continue.

Brilliant. I feel really stupid for not seeing that :-)

It always helps to have someone who hasn't been staring at the code for hours to have a look, hehe. (Or someone who's just better at it than me, lol)

Thanks a lot.

And for the benefit of anyone who searches for this thread in the future, here's the working code:

Code:

---

        for(cnx_inf_vector::iterator it = v_clients.begin(); it != v_clients.end();) {
                if (FD_ISSET(it->sock,fds)) {
                        r = recv(it->sock,&b,sizeof(b),MSG_PEEK);
                        if (r < 1) {
                                log_printf("[main] Connection to %s lost.\n",inet_ntoa(it->sin.sin_addr));
                                it = removeConnection(it);
                                continue;
                        } else {
                                proc_data(it);
                        }
                }
                ++it;
        }

---

Now that you've devised a solution using vectors have you thought about using an alternate container type to store the information? As already mentioned a map can help eliminate some of the hassles you've encountered, as can a list. Unfortunately, both maps and lists have their own quirks, so I can't say one container is better than another. It amounts to how comfortable you are with a given container, what sort of hassles you are willing to put up with, etc.


Sometimes it's fun to speculate about what's happening under the hood with the array/vector element erasure, to see if this can clarify what's happening during the process. I don't know that any of this is true, but if I'm way off base, I'm confident someone will put me on the correct course.

Start with an array of three objects:

array[0] = a
array[1] = b
array[2] = c

now erase b;

How do you erase b? You can't really. You can write over b with c and end up with

array[0] = a
array[1] = c
array[2] = c

and then if you know the size of the array is 2 rather than 3 then you can ignore whatever is in array[2]. Alternatively, you could use a struct with a data element and a flag instead of just a data element;

array[0] = a, flag = true
array[1] = b, flag = true
array[2] = c, falg = true

now to erase b you change the flag to false

array[0] = a, flag = true
array[1] = b, flag = false
array[2] = c, flag = true

The size of array still equals three but you only use elements where flag is true. Again you really haven't erased anything, just indicated what you ignore by using size in one protocol and a flag in the other.

You can envision erase() using either method. If it uses the former, then after the erasure of b is completed you should be able to do this:

cout << array[1] << endl;

and have output of: c

Therefore, I suspect that's the method used. But let's say you had an iteratorB that points to b and and iteratorC that points to c. If you erase() b and shift c over to element array[1] then iteratorC no longer holds a valid address, so it is invalidated, and iteratorB no longer holds b, so it is invalidated. So far so good, we know erasure and insertions invalidate all vector iterators. But how do you return a valid iterator to the "next" item in the vector. I suspect that the "next" item is identified before the overwrite and the value is stored in a temporary variable. Then the overwrite occurs, invalidating iteratorB and iteratorC. Finally, the value of c, which has been stored in the temporary variable is located after the erasure and that iterator is returned. I suspect the address of the data member in the return iterator will have the same address as the data member in iteratorB prior to the erasure. This would allow the use of the [] operator in the appropriate fashion post erasure, explain the need for invalidation of iterators following erasure/insertion, and which iterator to return.

Good point elad. I think in codec's case, a list might be a better solution. This is because I don't see where that code uses the indexes for each element. If no index is used and the vector is never accessed with operator[] except when looping, then a list would make more sense.

Erasing from a vector is an expensive operation because it is implemented like elad's first example. All of the following elements are copied one at a time to their new position. If you erase from a list, no copying is done, it is just updating a couple pointers. Basically, if you don't need the random access (operator []) and you are erasing elements from the middle of the container, a list would be a better idea. And if you are using iterator syntax (as opposed to array syntax) it would likely not take a lot of work to replace the vector with the list.

The requirements on the internal structure of vector enforce the former erasure method. Therefore you cannot envision erase() using the second method.

erase() and insert() also don't invalidate all iterators. erase() invalidates all iterators to the erased and all later elements. insert() depends. If capacity() > size() previous to the insertion, then insert() invalidates all iterators after the insert position, otherwise it invalidates all iterators.

Your explanation about the next valid item is also off. The vector simply temporarily stores the index of the first erased element and returns an iterator pointing to the element at that location after the erasure.

Thanks. I am going to look into which container would best fit my requirements. I haven't yet got a unique identifier for each record (local port number?), but I could always implement one, and use a map, as someone suggested. If I don't use a unique ID then I could use a list as jlou suggested, to minimize the cost of erasing elements.

Thanks for the suggestions. If I mis-interpreted someone, sorry. I'm going to have a good read through your suggestions as soon as I get some time to read them thoroughly.

Dan