«

Hello,

For coding contests I only have a solid knowledge of C. When problems
get hard, I won't have time to code up my own Andersson tree but will
have to use a binary search tree in the STL.

Is there a good tutorial on C++ you would recommend, covering especially
the STL, on the internet for C programmers? I need a solid understanding
of C++ programs that are the C++ version of the C counterpart (so I can
found out what I need to #include, what using namespace std means), and
don't need OOP *at all* (but I think the STL requires understanding of
OOP, I'm not sure).

TIA,

Albert

"Albert" <> wrote in message
news:KAM5n.2415$...
> Hello,
>
> For coding contests I only have a solid knowledge of C. When problems get
> hard, I won't have time to code up my own Andersson tree but will have to
> use a binary search tree in the STL.
>
> Is there a good tutorial on C++ you would recommend, covering especially
> the STL, on the internet for C programmers? I need a solid understanding
> of C++ programs that are the C++ version of the C counterpart (so I can
> found out what I need to #include, what using namespace std means), and
> don't need OOP *at all* (but I think the STL requires understanding of
> OOP, I'm not sure).

I recommend the book "Accelerated C++" by Andrew Koenig and Barbare E. Moo:
http://www.amazon.com/Accelerated-C-...4049594&sr=8-1

Leo Havmøller.

IMHO I dont think you can understand STL really well if you don't know C++
really well.

Bas

"Albert" <> wrote in message
news:KAM5n.2415$...
> Hello,
>
> For coding contests I only have a solid knowledge of C. When problems get
> hard, I won't have time to code up my own Andersson tree but will have to
> use a binary search tree in the STL.
>
> Is there a good tutorial on C++ you would recommend, covering especially
> the STL, on the internet for C programmers? I need a solid understanding
> of C++ programs that are the C++ version of the C counterpart (so I can
> found out what I need to #include, what using namespace std means), and
> don't need OOP *at all* (but I think the STL requires understanding of
> OOP, I'm not sure).
>
> TIA,
>
> Albert

"Francis Glassborow" <> wrote in message
news:...
> Bas wrote:
>
>>
>> "Albert" <> wrote in message
>> news:KAM5n.2415$...
>>> Hello,
>>>
>>> For coding contests I only have a solid knowledge of C. When problems
>>> get hard, I won't have time to code up my own Andersson tree but will
>>> have to use a binary search tree in the STL.
>>>
>>> Is there a good tutorial on C++ you would recommend, covering especially
>>> the STL, on the internet for C programmers? I need a solid understanding
>>> of C++ programs that are the C++ version of the C counterpart (so I can
>>> found out what I need to #include, what using namespace std means), and
>>> don't need OOP *at all* (but I think the STL requires understanding of
>>> OOP, I'm not sure).
>>>
>
> > IMHO I dont think you can understand STL really well if you don't know
> > C++ really well.
> >
> > Bas
>
> However you do not need to understand it in order to use it. E.g.
>
> std::vector<T>
>
> all the user needs to know is that creates an expendable sequence of T.

...I think you need at least some knowlegde of templates. If T is a compound
object (Base and derived class) you need to know etc.
I doubt one can use the STL without knowing C++.

Bas

Yannick Tremblay wrote:
> In article <4b584dcf$0$14127$>,
> Bas <> wrote:
>> <snip>
>>> <snip>
>>>> <snip>
>>>>> <snip>
>>>> <snip>
>>> <snip>
>> <snip>
> I think the point is the the OP (Albert) fears that using C++ would
> require him to switch completely to Object Oriented programming rather
> than the functional programming style that is more common in C and
> that he has been using for years and that he is familiar and
> confortable with.
> <snip>

Not quite. In coding contests, everyone I know uses a functional
programming style, it's just that they are about getting the algorithms
right in a limited time, not spending half the time debugging the
various operations/functions for the sometimes tricky data structures
required (eg. height-balanced binary search trees, *maybe* the
heap-based priority queue and the disjoint set operations for
Kruskal's). I'm keeping in mind that at international level (ie. the
IOI), no reference materials can be brought in by people, and the
computers only provide STL docs and C reference.

Albert <> writes:
> Yannick Tremblay wrote:
>> In article <4b584dcf$0$14127$>,
>> Bas <> wrote:
>>> <snip>
>>>> <snip>
>>>>> <snip>
>>>>>> <snip>
>>>>> <snip>
>>>> <snip>
>>> <snip>
>> I think the point is the the OP (Albert) fears that using C++ would
>> require him to switch completely to Object Oriented programming rather
>> than the functional programming style that is more common in C and
>> that he has been using for years and that he is familiar and
>> confortable with. <snip>
>
> Not quite. In coding contests, everyone I know uses a functional
> programming style, it's just that they are about getting the
[snip]

I don't think "functional programming style" is really what
you mean. A functional programming style is common in Lisp and
similar languages. The most common programming style in C is an
imperative or procedural style.

--
Keith Thompson (The_Other_Keith) kst- <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Keith Thompson wrote:
> Albert <> writes:
>> Yannick Tremblay wrote:
>>> In article <4b584dcf$0$14127$>,
>>> Bas <> wrote:
>>>> <snip>
>>>>> <snip>
>>>>>> <snip>
>>>>>>> <snip>
>>>>>> <snip>
>>>>> <snip>
>>>> <snip>
>>> I think the point is the the OP (Albert) fears that using C++ would
>>> require him to switch completely to Object Oriented programming rather
>>> than the functional programming style that is more common in C and
>>> that he has been using for years and that he is familiar and
>>> confortable with. <snip>
>> Not quite. In coding contests, everyone I know uses a functional
>> programming style, it's just that they are about getting the
> [snip]
>
> I don't think "functional programming style" is really what
> you mean. A functional programming style is common in Lisp and
> similar languages. The most common programming style in C is an
> imperative or procedural style.
>

Yep, you're right; that is indeed what I meant

Albert wrote:
> <snip>
> Is there a good tutorial on C++ you would recommend, covering especially
> the STL, on the internet for C programmers?
> <snip>

Read up to Chapter 17 of http://www.4p8.com/eric.brasseur/cppcen.html;
that should be enough information about templates to move on to
http://www.sgi.com/tech/stl/stl_introduction.html. That should be enough
to get though most of the documentation after reading the section about
iterators.

This should be enough for C programmers to be able to basically use the
STL when time is short for coding up tricky data structure operations

P.S. Where's the balanced binary search tree in the STL?

Albert

In article <dG76n.2639$>, Albert <> writes:

> P.S. Where's the balanced binary search tree in the STL?

If you can be sure that the C library provided to you will be the GNU
libc, you might get by with tdelete(), tfind(), tsearch(), and twalk()
from <search.h>.

http://www.opengroup.org/onlinepubs/.../search.h.html

Some characterization:

- None of these functions are standard C.

- All of them are SUS since SUSv1.

- The SUS versions don't require the trees to be balanced. (I'm saying
this after some very superficial checking.)

- The glibc implements the functions with red-black trees. See
"glibc-2.11.1/misc/tsearch.c". According to the heading comment
in that file, this is the situation since 1997. This seems to match
your balancedness requirement.

- The GNU libc provides an extension, tdestroy(); "man tdestroy".

The std::map template provides more operations. For example, you can't
easily walk two trees in lockstep with the t*() API unless you resort to
threads / longjmp() / swapcontext(), but you can easily do that with
std::map::iterator and co.

Cheers,
lacos