C++ Lobby Lister Class

[pubby8]

How can people overuse vectors or iterators in C++? STL containers are more or less meant to be used instead of old-fashioned plain array data structures, and iterators are meant to be used for iterating through them. It's kind of like std::string vs. C-string thing; in C++ using good ol' C strings is more or less considered bad practice(error prone, not always clear, POINTERS yuck!) because you've got std::string. Of course old C strings are perfectly valid, but I'd guess that it's more because of better backward compatibility with C and it's legacy rather than as an practical language feature.

Because people misuse the STL/STD all the time:
not using reserve
using push_back when there is no need to
improper use of temporary objects (c_str is very commonly misused)
iterator problems and quirks
using wrong algorithm/container

C library has just as many problems as C++ does, I just find it silly when people treat C++'s library as a holy scripture, and never write their own containers classes.

The results stay the same even after swapping them with GCC 4.45, that is not the reason. As I explained they boil down to simple pointers, THAT is the reason why they're faster.

I'm definitely getting a difference on the order, dunno why I am and you are not.

And you can easily change your code to:

Code: [Select]

                for (int* i = va; i < &va[100000000]; ++i) {
                        *i += 10; // do something so loop doesn't get optimized away
                }I find this more readable than the iterator code.

But it is all personal preference, so don't take what I say as argument, just as discussion   

[ramirez]

And you can easily change your code to:

Code: [Select]

                for (int* i = va; i < &va[100000000]; ++i) {
                        *i += 10; // do something so loop doesn't get optimized away
                }I find this more readable than the iterator code.

But it is all personal preference, so don't take what I say as argument, just as discussion   

That is just terrible, no offense. No C++ programmer in their right mind would code like that, that looks like something a C programmer that just started C++ would do. And while we're on the subject of aesthetics, in C++0x you can actually do this with iterators, which is much nicer:

Code: [Select]

for (auto i = v.begin(); i < v.end(); i++) { ... }
The auto keyword will deduce the type from the expression, in this case std::vector<int>::iterator; this is already supported in MSVC2010 and latest GCC versions.

[iDante]

Will auto acquire some new usefulness in C++0x?

Also jrgp you really don't need that much commenting. I'm normally a proponent of heavy comments but several of these made me cry a little bit.

Code: [Select]

// Result stored here
vector<std::string> result;

// Give
return result;

// Store actual servers here
vector<server_entry> servers;
etc.

Shoutout to ramirez btw, your posts are always really awesome and informative

[ramirez]

Will auto acquire some new usefulness in C++0x?

Well all it really does is simplify your code quite a bit. You can see the usefulness in using auto instead of say, std::map<std:.string, std::vector<int>>::iterator
Another good example is that if you want to eg. store a lambda function in 0x, it's much easier with the auto keyword, eg:

Code: [Select]

auto func = [](int x, int y) { return x + y; };

[pubby8]

And you can easily change your code to:

Code: [Select]

                for (int* i = va; i < &va[100000000]; ++i) {
                        *i += 10; // do something so loop doesn't get optimized away
                }I find this more readable than the iterator code.

But it is all personal preference, so don't take what I say as argument, just as discussion  

That is just terrible, no offense. No C++ programmer in their right mind would code like that, that looks like something a C programmer that just started C++ would do. And while we're on the subject of aesthetics, in C++0x you can actually do this with iterators, which is much nicer:

I don't see why that code is so "terrible" - it's very clear and simple.
In my opinion, if you want a language where you avoid pointers, memory, and anything slightly c-like, then go use java.

[ramirez]

For various reasons:

1) It's not consistent with the concept called iterators in C++, it'll not work for other containers that are non-sequential; you should try to keep consistent. This is C++, not C, use the facilities that C++ provide you. That method is pretty much only guaranteed to work with vector (actually it's not even valid for vector, but it could be by changing it a bit, see next reason).

2) That is actually defined as undefined behavior per standard when you run that code; you're accessing the array outside of its boundaries. It most likely works on most compilers, but the fact is that accessing outside the array's boundary. The proper way would be i < &va[0]+100000000 or i <= &va[99999999].

3) You're using a magic number, you probably meant to use va.size() instead of that 100000000.

4) In case you want it, you're not taking advantage of your compiler's some features, for instance MSVC has a feature called checked iterators that add extra security to them. This is arguable though, since checked iterators actually have a bit of an overhead to them, so if you care more about speed than safety, you would turn these off anyways.

So basically, iterators are generally safer and more consistent. If you get used to iterators, like you should, then you don't need to guess "how should I iterate this type of container", since every container would be iterated through similarly. There's no other way to iterate through some container's than the standard library iterators, take for example a list or a set or a map. Get used to the iterators everywhere.

Btw another fun fact about C++0x, it includes a feature called range-based for loop, which is essentially a foreach loop similar from other languages. It allows you to iterate containers (as well as regular arrays) like this:

Code: [Select]

for (int& x: va) {
    x += 10; // we're iterating by reference
}
This is by far the simplest and cleanest way to iterate a container.

[pubby8]

Oh, I think there is misunderstanding.
That code was being used on a normal array, not on a vector (that is why I renamed it "va" (a for array) and not "v")

2) That is actually defined as undefined behavior per standard when you run that code; you're accessing the array outside of its boundaries. It most likely works on most compilers, but the fact is that accessing outside the array's boundary. The proper way would be i < &va[0]+100000000 or i <= &va[99999999].

I see what you are saying, but &va[0]+100000000 could also be problematic if it happened to overflow (very  very unlikely)

3) You're using a magic number, you probably meant to use va.size() instead of that 100000000.

Here is another reason why I dislike vectors - they store additional values such as size and reserved size. 90% of arrays I need are a constant size. If it was actual code, of course there wouldn't be a magic number in there, but it was a test snippet so I hope you understand the purpose of it was not about use of magic numbers.

4) In case you want it, you're not taking advantage of your compiler's some features, for instance MSVC has a feature called checked iterators that add extra security to them. This is arguable though, since checked iterators actually have a bit of an overhead to them, so if you care more about speed than safety, you would turn these off anyways.

If iterators are so safe and consistent, why are there "checked iterators" then?

So basically, iterators are generally safer and more consistent. If you get used to iterators, like you should, then you don't need to guess "how should I iterate this type of container", since every container would be iterated through similarly. There's no other way to iterate through some container's than the standard library iterators, take for example a list or a set or a map. Get used to the iterators everywhere.

You should be thinking about "how should I iterate this container," as it can be very critical to your performance. Especially since STL wasn't designed for threading.

I've used the STL a great deal a while ago, but I found it limiting. I rewrote my code that was using it and actually got ~7 times performance improvement. It still remained readable, it was largely OO, and I didn't have to write too much code. You don't need to have some oversimplified helper library to hold your hand to get stuff done in a good way.
/rant

[ramirez]

Oh, I think there is misunderstanding.
That code was being used on a normal array, not on a vector (that is why I renamed it "va" (a for array) and not "v")

Okay, that was indeed confusing, you should have said so, just changing a name of a variable is not enough to jump from one topic to another. Last I checked we were discussing about the C++ standard library iterators here.

I see what you are saying, but &va[0]+100000000 could also be problematic if it happened to overflow (very  very unlikely)

That obviously depends on the size of the array.. If it has 100000000  elements, then doing &va[0]+100000000 is same as &va[100000000], there's no difference, it is not "very very unlikely" that one would overflow but other would not. I don't understand how this is relevant to the discussion at hand in anyway.

Here is another reason why I dislike vectors - they store additional values such as size and reserved size. 90% of arrays I need are a constant size. If it was actual code, of course there wouldn't be a magic number in there, but it was a test snippet so I hope you understand the purpose of it was not about use of magic numbers.

Those "additional values" are what makes them possible in the first place. If 90% of your arrays are of static size, you probably code way differently than I do (and I don't disagree btw, if your arrays are static size, there's not much point using vector then). But that is beyond the whole argument here, we were not talking about variable length arrays vs static length arrays, we were discussing the C++ standard library iterators, and how standard containers should be iterated.

In terms of additional overhead things like keeping track of the size; it's not much. What's expensive though is that if the vector goes over its reserved capacity, since it'll need to copy the data to a new location in that case (C++0x has a nifty feature called move semantics, that make copying larger objects that are being destructed after the copy much faster!) Once again a good C++ programmer is aware of this, and knows to reserve space for his vector when necessary.

If iterators are so safe and consistent, why are there "checked iterators" then?

They're mostly useful for finding bugs in your code. For example normally if you try to use an uninitialized iterator or one that has gone beyond the bounds of the container you'll get undefined behavior; you might spot the error or you might not. It might not happen for you, but it might happen to some of your users. With checked iterators you catch bugs like those much easier in your code, as they're checked and exceptions are thrown (it's mainly useful to keep on in debugging builds, for release builds and maximal speed you usually want to turn it off if you want the extra speed).

You should be thinking about "how should I iterate this container," as it can be very critical to your performance. Especially since STL wasn't designed for threading.

With most containers there is only one way to iterate the container. Also remember that the point of iterators is to, well, iterate through the container. The compiler manufacturers have taken steps to optimize the iterator code so that it'll be as fast as possible. Don't try to prematurely optimize code like this, I'm sure you've heard the saying that premature optimization is the root of all evil. In matter of fact, by not understanding how iterators really work, you can actually write more inefficient code than just trusting your compiler and its optimizer (as I showed before). I won't even start on talking about threading, as it is way off topic here, and it's actually implementation specific (there are thread safe implementations of the library).

I've used the STL a great deal a while ago, but I found it limiting. I rewrote my code that was using it and actually got ~7 times performance improvement. It still remained readable, it was largely OO, and I didn't have to write too much code. You don't need to have some oversimplified helper library to hold your hand to get stuff done in a good way.

I don't believe that. I would like to see some benchmarks and code where you custom written containers/code is 7 times faster. What is more likely is that you misused the standard library and used wrong containers for wrong things (it's essential to understand how each container works so you can use it for the purpose it was meant for), or perhaps you did your benchmarks using debug builds instead of release builds (as I demonstrated before, the containers/iterators are quite a bit faster in release builds due to optimizations taking place). Also note that the C++0x has new containers that are better for certain things, such as std::unordered_map (basically a hashmap), before C++0x most people prefer to use boost to get access to these useful containers (why reinvent the wheel right? boost containers follow the format of stdlib containers as in they're iteretable and compatible with the stdlib algorithms, and they are thoroughly tested and optimized). But I'm willing to be proven wrong, but I don't take your word for it. I want to see code and benchmarks, I'm sure you understand my skepticism of you being able to write ~7 times faster code than the people who write these compilers for living and know C++ and inside and out, plus how to optimize their code for their own compiler.

PS. It is confusing to call the standard library STL, and is not quite accurate. You might want to consider calling it C++ standard library, or stdlib, either, see the first answer here to as of why: http://stackoverflow.com/questions/5205491/whats-this-stl-vs-c-standard-library-fight-all-about

[pubby8]

That obviously depends on the size of the array.. If it has 100000000  elements, then doing &va[0]+100000000 is same as &va[100000000], there's no difference, it is not "very very unlikely" that one would overflow but other would not. I don't understand how this is relevant to the discussion at hand in anyway.

I was just saying that &va[0]+9999999 seemed better.

In terms of additional overhead things like keeping track of the size; it's not much. What's expensive though is that if the vector goes over its reserved capacity, since it'll need to copy the data to a new location in that case (C++0x has a nifty feature called move semantics, that make copying larger objects that are being destructed after the copy much faster!) Once again a good C++ programmer is aware of this, and knows to reserve space for his vector when necessary.

That overhead may not seem like much when you are testing 1 vector, but since you will likely have 1000s of vectors in actual code, the overhead will become noticeable. Not a big problem, but it makes a lot of sense to use arrays when you can.

They're mostly useful for finding bugs in your code. For example normally if you try to use an uninitialized iterator or one that has gone beyond the bounds of the container you'll get undefined behavior; you might spot the error or you might not. It might not happen for you, but it might happen to some of your users. With checked iterators you catch bugs like those much easier in your code, as they're checked and exceptions are thrown (it's mainly useful to keep on in debugging builds, for release builds and maximal speed you usually want to turn it off if you want the extra speed).

Yeah, those features are helpful. They work for normal arrays too though, like valgrind.

I don't believe that. I would like to see some benchmarks and code where you custom written containers/code is 7 times faster. What is more likely is that you misused the standard library and used wrong containers for wrong things (it's essential to understand how each container works so you can use it for the purpose it was meant for), or perhaps you did your benchmarks using debug builds instead of release builds (as I demonstrated before, the containers/iterators are quite a bit faster in release builds due to optimizations taking place). Also note that the C++0x has new containers that are better for certain things, such as std::unordered_map (basically a hashmap), before C++0x most people prefer to use boost to get access to these useful containers (why reinvent the wheel right? boost containers follow the format of stdlib containers as in they're iteretable and compatible with the stdlib algorithms, and they are thoroughly tested and optimized). But I'm willing to be proven wrong, but I don't take your word for it. I want to see code and benchmarks, I'm sure you understand my skepticism of you being able to write ~7 times faster code than the people who write these compilers for living and know C++ and inside and out, plus how to optimize their code for their own compiler.

While vector obviously isn't 7 times slower, stuff like list and map are not optimal in most cases. One algorithm I got big speed improvements was a LRU caching one - I originally used a list, and also tried a map+list, but by rewriting it using a custom hash table that uses a linked list with 4 pointers per node, and a custom stack-based allocator, I got massive improvements.

[ramirez]

While vector obviously isn't 7 times slower, stuff like list and map are not optimal in most cases. One algorithm I got big speed improvements was a LRU caching one - I originally used a list, and also tried a map+list, but by rewriting it using a custom hash table that uses a linked list with 4 pointers per node, and a custom stack-based allocator, I got massive improvements.

You can't really compare that. You wrote an entirely different kind of container and compared it to another kind of container. All that really shows is that hashmap was a better container than a sorted map for that situation. You should have used std::unordered_list or boost::hash_map in the first place if you needed hash map. But writing your own is understandable if you don't want to depend on boost and you didn't use 0x, or you needed some special features.

Btw std::map insertions are a lot faster if you know where in the container you insert it, and give a hint iterator to the .insert() function, and by a lot I mean it can easily be up to 5-10 times faster, or even more, depending on the size of the map.

[pubby8]

You can't really compare that. You wrote an entirely different kind of container and compared it to another kind of container.

I converted a list and an associative array into a list and an associative array. Yes, it did go from a RB-tree to a hash table, but map and list was the correct containers if using strictly standard library.

If you think boost::hash_map could get better performance, would you be willing to test it and write code that performs the same thing that mine does? I can give you the details if you are willing to do so.

Btw std::map insertions are a lot faster if you know where in the container you insert it, and give a hint iterator to the .insert() function, and by a lot I mean it can easily be up to 5-10 times faster, or even more, depending on the size of the map.

Yes, but there are few cases where you would iterate through a map, and then need to insert while iterating.

[VirtualTT]

The first thing is that res variable upon successful call to getaddrinfo() points to the first node of the linked-list of addrinfo structs (you must later call freeaddrinfo() with this first node). So you should loop through this list and try to create socket with each struct and try to connect it while currentaddrinfo->ai_next != NULL instead of trying to connect using only the first node.

Also under windows you should prefer WSAGetLastError() to get error codes.