Thread: 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.

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

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

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.