C++ basics for competitive programming
topcoder.com
topcoder.com
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.)
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.
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.
No one claimed any of the things you seem to be arguing against...
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.
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.
All this information is readily found in any online docs about C++. Please read those.
https://isocpp.org/blog/2015/09/stroustrup-cppcon15-keynote
(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)
- 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.
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.
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."
what would be the right way to do this?
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())Just write C. C++ is too much of a pain.
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.
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.
lots of macros to do operations quickly, the code is not even readable.
vector< vector<int> >
Of course, it should also be std::vector<std::vector<int>> ...
Do you think compiler support is instantaneous for all platforms on all operating systems, retroactively, when the standard is published?
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 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.
Fixed that for you.
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.
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.
vector<vector<int>>