C++ basics for competitive programming(topcoder.com)
topcoder.com
C++ basics for competitive programming
https://www.topcoder.com/community/data-science/data-science-tutorials/power-up-c-with-the-standard-template-library-part-1/
3 comments
> No, it is not. A C array under the hood is a pointer to the start of the array. A vector is a data structure that includes a pointer to the start of an array.
I don't think the article meant a vector is identical to a C array. I think the article meant a view into the vector can be passed to a C routine expecting a C array.
This is guaranteed by the C++ standard for the vector standard container:
This is a problem in C and C++ with any memory. If you change the memory while someone else has a pointer to it, you lose. This has nothing to do with vector vs arrays, and actually works the same for vectors and arrays (if you realloc a C array, you have the same issue as if you append to a vector).
> Want another fun difference? In C programming you can easily allocate arrays in an mmapped block backed by a file, exit, then do another run and simply load the mmapped block.
Since you can't "point" a vector at a section of memory and tell it to use it, this is nonsensical. In C++ you would use a pointer or array_view if you already have contiguous memory allocated and want to refer to it by using an index.
I don't think the article meant a vector is identical to a C array. I think the article meant a view into the vector can be passed to a C routine expecting a C array.
This is guaranteed by the C++ standard for the vector standard container:
extern "C" void consume(int *x, size_t len);
void f(std::vector<int> v)
{
consume(&v[0], v.size()); // C++98
consume(v.data(), v.size()); // C++11
}
This is a problem in C and C++ with any memory. If you change the memory while someone else has a pointer to it, you lose. This has nothing to do with vector vs arrays, and actually works the same for vectors and arrays (if you realloc a C array, you have the same issue as if you append to a vector).
> Want another fun difference? In C programming you can easily allocate arrays in an mmapped block backed by a file, exit, then do another run and simply load the mmapped block.
Since you can't "point" a vector at a section of memory and tell it to use it, this is nonsensical. In C++ you would use a pointer or array_view if you already have contiguous memory allocated and want to refer to it by using an index.
>This has nothing to do with vector vs arrays, and actually works the same for vectors and arrays (if you realloc a C array, you have the same issue as if you append to a vector).
If you realloc a C array, you have "realloc" written somewhere in your source code. And a pointer that you updates.
> Since you can't "point" a vector at a section of memory and tell it to use it, this is nonsensical. In C++ you would use a pointer or array_view if you already have contiguous memory allocated and want to refer to it by using an index.
Yes. This is just not "backward-compatible to native C code", and the vector actually is NOT the array (which is also not a pointer, but anyway...). Deal with it.
If you realloc a C array, you have "realloc" written somewhere in your source code. And a pointer that you updates.
> Since you can't "point" a vector at a section of memory and tell it to use it, this is nonsensical. In C++ you would use a pointer or array_view if you already have contiguous memory allocated and want to refer to it by using an index.
Yes. This is just not "backward-compatible to native C code", and the vector actually is NOT the array (which is also not a pointer, but anyway...). Deal with it.
> If you realloc a C array, you have "realloc" written somewhere in your source code. And a pointer that you updates.
It's not much harder to spot with vector. The behaviour is fairly simple. So long as you don't expand past vector.capacity(), it's not going to realloc.
It's not much harder to spot with vector. The behaviour is fairly simple. So long as you don't expand past vector.capacity(), it's not going to realloc.
At the end, all things are equivalent, however for example explaining that to complete beginners (vector growing rules, their relationship to underlying memory allocation and pointers, the fact that "raw" memory allocation exists at all) would be IMO a bad idea, while introducing them to modern C++ without any legacy C++/C backward compatibility is probably both ok and quite safe.
I would also be OK in introducing plain C to complete beginners, exploring more about objects in memory and pointers and complete manual control of all code paths (although, on a side-note, its way harder now that compiler writer consider any undefined behavior to be a fatal sin, even when it would have an "obvious" meaning when looking at the target machine in term of what its ISA is).
However, for sure, I would not introduce pre-C++11 nor mixed C/C++ to beginners.
How does it matter? Well, I think that a beginner with a trivial source code is a reasonable approximation of a team working on a not so clean codebase as far as safety is concerned. Likewise for a tired confirmed developer on a clean codebase. Is it simple enough to be taught by a non expert teacher without needing too much preparation? If not, it means you risk to have to keep too much details in your head, that will either slow you down or you will eventually make mistakes.
I would also be OK in introducing plain C to complete beginners, exploring more about objects in memory and pointers and complete manual control of all code paths (although, on a side-note, its way harder now that compiler writer consider any undefined behavior to be a fatal sin, even when it would have an "obvious" meaning when looking at the target machine in term of what its ISA is).
However, for sure, I would not introduce pre-C++11 nor mixed C/C++ to beginners.
How does it matter? Well, I think that a beginner with a trivial source code is a reasonable approximation of a team working on a not so clean codebase as far as safety is concerned. Likewise for a tired confirmed developer on a clean codebase. Is it simple enough to be taught by a non expert teacher without needing too much preparation? If not, it means you risk to have to keep too much details in your head, that will either slow you down or you will eventually make mistakes.
It would be correct to say this about std::array<> but NOT about std::vector .
This article is probably one of the reasons why C++ gets the reputation it has. Please do not program like this. Aside from the fact that this is C++98, which lacks tons of features now widely accepted and useful in C++, the code in this article has no consistency, uses most bad practices I know, and is most certainly not geared towards competitive programming.
All this information is readily found in any online docs about C++. Please read those.
All this information is readily found in any online docs about C++. Please read those.
On that note, these links are the best place to start when it comes to writing "good" C++ these days:
https://isocpp.org/blog/2015/09/stroustrup-cppcon15-keynote
http://herbsutter.com/2015/09/27/my-talk-at-cppcon/
https://github.com/isocpp/CppCoreGuidelines
https://isocpp.org/blog/2015/09/stroustrup-cppcon15-keynote
http://herbsutter.com/2015/09/27/my-talk-at-cppcon/
https://github.com/isocpp/CppCoreGuidelines
Can you give concrete example what you are referring to? From a quick skim, I would say that's quite clean, straightforward algorithmic code -- while it could be improved a tiny little bit by sprinkling in a little C++11 syntax (don't overdo it).
(For context, I'm mainly a C / Python / Unix Programmer, with an interest in common sense and architectures based on clean plain data interfaces instead of wrong abstractions, and with a good track on SPOJ)
(For context, I'm mainly a C / Python / Unix Programmer, with an interest in common sense and architectures based on clean plain data interfaces instead of wrong abstractions, and with a good track on SPOJ)
Just random things that pop up:
- using namespace std;
- variable names inconsistent and random, using uppercase and lowercase randomly (code also would not compile since it is cased randomly)
- indenting and braces inconsistent
- use of macros for trivial tasks where they are absolutely not required
- use of macros in totally dangerous ways ("#define all(c) c.begin(), c.end()", seriously?)
- usage of compiler dependent features
- code should be for "competitive programming", and proposes a vector of vectors to make a 2D matrix
- Counterproductive and unhelpful typedefs
EDIT:
I'd like to tell you more, but looking at that page is making me feel unwell. The ostringstream example seems to be out of a nightmare. Just learn C++ from a reputable source and save yourself and everybody else around you the pain.
- using namespace std;
- variable names inconsistent and random, using uppercase and lowercase randomly (code also would not compile since it is cased randomly)
- indenting and braces inconsistent
- use of macros for trivial tasks where they are absolutely not required
- use of macros in totally dangerous ways ("#define all(c) c.begin(), c.end()", seriously?)
- usage of compiler dependent features
- code should be for "competitive programming", and proposes a vector of vectors to make a 2D matrix
- Counterproductive and unhelpful typedefs
EDIT:
I'd like to tell you more, but looking at that page is making me feel unwell. The ostringstream example seems to be out of a nightmare. Just learn C++ from a reputable source and save yourself and everybody else around you the pain.
For programming contests, often saving keypresses is more valuable than good style or practice. Agreed that no one should cut these corners when writing code that will be used again tomorrow, but when you're trying to hammer out something in under 10 minutes (or whatever), there are lots of bad practice tricks that become very useful (like macros that would be awful in any other context).
Before people lynch me, I just wants emphasize again that I'm not defending these practices in production code, but the article wasn't advocating that either. And of course there's the old debate about whether the contests themselves become harmful because they encourage bad practice, and that may be true, but that's a different conversation.
Before people lynch me, I just wants emphasize again that I'm not defending these practices in production code, but the article wasn't advocating that either. And of course there's the old debate about whether the contests themselves become harmful because they encourage bad practice, and that may be true, but that's a different conversation.
Did you read that this is for _competitive programming_?. I know you did as you mention it, but then some of your points don't make sense. In topcoder every second counts, and if using `all(c)` instead of writing up `c.begin(), c.end()` can save you two seconds, you should do it.
Also your code can be 'challenged' by someone else (they give an example where your code fails), and making obscure typedefs and macros that will make it ever so slightly harder for someone to decipher what you are going is allright.
You're right that some of those items are bad practices in normal development. But some of them would actually help a person bang together crappy but working code more quickly for a one-off task.
Perhaps we should read "competitive programming" as "programming quickly without regard for quality." Taken that way, the article could even be titled "programming to impress nontechnical managers so you can become one."
Perhaps we should read "competitive programming" as "programming quickly without regard for quality." Taken that way, the article could even be titled "programming to impress nontechnical managers so you can become one."
> proposes a vector of vectors to make a 2D matrix
what would be the right way to do this?
what would be the right way to do this?
2D arrays that are laid out as a linear array of mn elements are faster to iterate through. That's what happens when you declare e.g. int a[5][4], you get the same layout as int a[20]. A vector of vectors is fairly sprawling in memory, and generally matrices don't get resized so you want this compact form because it's quicker to loop through (either way is O(mn), but one has a way better coefficient).
Is this enough ?
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
#define sz(a) int((a).size())
#define pb push_back
#defile all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin() i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())That's just bad C code, and is exactly the type of stuff I'd expect on topcoder, which seems to attract the types that write incomprehensible code... but hey man, it's fast!
Just write C. C++ is too much of a pain.
Just write C. C++ is too much of a pain.
I do not agree, this is tutorial is very specific for competitive programming and it is well known that it doesn't mean good code, e.g. https://news.ycombinator.com/item?id=9324209 and actually it was great tutorial years ago but now we have c++11 and I would like an updated version of this tutorial that use c++11 features.
I cannot support this view enough. After reading about `typeof(a + b)` to do what `auto` in C++11 does, I cringed a little inside.
If you want to get good at C++, there are no shortcuts. Read books (Scott Meyers, Bjarne Stroustrup), read Herb Sutter's GotW series, but don't read this.
If you want to get good at C++, there are no shortcuts. Read books (Scott Meyers, Bjarne Stroustrup), read Herb Sutter's GotW series, but don't read this.
I would add "Physically based rendering" by Pharr and Humphreys to that list. They demonstrate how to construct a complex application using C++ using a fairly unique literary programming style, and they also provide the source code for a functional system in their homepage. It's domain specific but the domain happens to be concerned with efficiency and correctness so it's not a bad one to learn.
You don't get C++11 or newer features on gcc 4.0.2 (https://community.topcoder.com/tc?module=Static&d1=help&d2=g...).
You have to keep in mind that code for this kind of competitions is generally write only and uses basic facilities of a language to solve given algorithmic problem as fast as possible. Consistency isn't important when your solution fits on a single page.
You have to keep in mind that code for this kind of competitions is generally write only and uses basic facilities of a language to solve given algorithmic problem as fast as possible. Consistency isn't important when your solution fits on a single page.
You think this is bad? try reading the code submitted during coding competitions (hackerrank, google's code jam).
lots of macros to do operations quickly, the code is not even readable.
lots of macros to do operations quickly, the code is not even readable.
Seriously. Nobody needs to think about stuff like this any more:
vector< vector<int> >
Personally I find the version with spaces easier to read, but I'm not going to get annoyed either way.
Of course, it should also be std::vector<std::vector<int>> ...
Of course, it should also be std::vector<std::vector<int>> ...
or more spacey, like std::vector< std::vector< int > >
People on C++03 where vector<vector<int>> is defined as operator >>. This wasn't fixed until C++11.
https://en.wikipedia.org/wiki/C%2B%2B11#Right_angle_bracket
https://en.wikipedia.org/wiki/C%2B%2B11#Right_angle_bracket
Don't use C++03 in 2016 please.
Not all of us have the luxury of using the latest compilers. Or the systems we support don't even have compilers which handle anything newer than C++03.
Do you think compiler support is instantaneous for all platforms on all operating systems, retroactively, when the standard is published?
Do you think compiler support is instantaneous for all platforms on all operating systems, retroactively, when the standard is published?
instantaneous != retroactively, neither it is the same as "5 years after".
And all major compiler vendors have since learned that they need to be up to date with the standard ASAP, even before official publication when it is possible.
Advocating C++ < 11 is harmful to the community, given how bad it was at that time.
And all major compiler vendors have since learned that they need to be up to date with the standard ASAP, even before official publication when it is possible.
Advocating C++ < 11 is harmful to the community, given how bad it was at that time.
Suggesting that compilers immediately adopt the latest standards is the "instantaneous".
Suggesting that older versions of the compilers (which may be the latest available versions on certain systems) also do so is the "retroactive".
So no, they are not the same. But yes, they are both reasons why one can not just blindly start using the latest features from the latest standards.
Suggesting that older versions of the compilers (which may be the latest available versions on certain systems) also do so is the "retroactive".
So no, they are not the same. But yes, they are both reasons why one can not just blindly start using the latest features from the latest standards.
Except if the compiler for your target platform (cough TI DSP cough) supports only C++03, and never will support anything newer.
> Don't use C++ in 2016 please.
Fixed that for you.
Fixed that for you.
No, you really didn't.
For all it's problems (some of which are being addressed in recent standard update , some not so much yet) it remains the best available tool for some domains. More's the pity.
For all it's problems (some of which are being addressed in recent standard update , some not so much yet) it remains the best available tool for some domains. More's the pity.
Seriously. C++ seems like a layer of hacks, one upon another, each designed to "fix" things in the layers below, only to add more confusion. Maybe "D" is the answer, or Go...? I don't know.
I started with C++ a long time ago, but for whatever reason, kept getting out of it (for a few years) and then every time I'd get back in, I'd be surprised at the new stuff.
I started with C++ a long time ago, but for whatever reason, kept getting out of it (for a few years) and then every time I'd get back in, I'd be surprised at the new stuff.
Just curious, what should you use instead?
vector<vector<int>>
He's talking about the fact that older compilers used to get confused if you happened to open/close multiple template tags in sequence; i.e. "<<" or ">>". These were mistaken for operators, and the code failed to compile. Nowadays there's no need to keep them separated, and compilers parse them correctly.
Matrix2D<int>. Removing a space from between the brackets misses the forest.
[deleted]
xorblurb(1)
No, it is not. A C array under the hood is a pointer to the start of the array. A vector is a data structure that includes a pointer to the start of an array. This is needed because that data structure is where it includes things like the size. But you can easily get out the array pointer, so no big deal, right? Wrong.
The problem is that there are vector operations which do weird stuff with the array. For example suppose you pass the array to one data structure, then push_back on the vector. The vector may now realize it doesn't have enough room to add more data, so moves the actual array to a new location and frees the old.
You may not realize this because the freed array still contains something that looks like the array. But it isn't any more!
Want another fun difference? In C programming you can easily allocate arrays in an mmapped block backed by a file, exit, then do another run and simply load the mmapped block. Try that with a vector and you'll get metadata pointing at random memory that you haven't allocated. BOOM!
So it is really wrong to say that a vector IS just a C array with extra features. They are different, and the differences can bite you pretty hard.
(That's the point I decided that continuing with this article was more likely to mislead than be helpful for me.)