>  Anyways, these are technical details you don't have to worry about.

On the other hand, my computer science 2 class focused almost entirely on 
the STL data structures and how to implement them yourself. It was a good 
way to learn the intricacies of making a class that has to deal with 
cleaning itself up, thus needing copy constructors and assignment operators 
and destructors. Understanding how this all works gets you closer to 
understanding how your code is compiled and the sort of things that are 
allowed (such as how a vector of vectors works internally).

Another way to learn that sort of thing is to do it the C way first, where 
you have a struct with some pointers in it, and you write your own functions 
to initialize the data, copy the data, and destroy the data. Then you learn 
why those functions are necessary and what happens if you try to avoid using 
them. Finally you see why C++'s approach is so nice, even though it's so 
hard to learn. The POV-Ray source was helpful when I was learning this, but 
I don't know how well it's split between C and C++ anymore.

However, all of this should wait until you're comfortable with pointers.

 - Slime
 [ http://www.slimeland.com/ ]

Post a reply to this message

Orchid XP v8 wrote:
> Is there a "set" type laying around somewhere? The thing I'm processing
> *is* notionally a set, not an ordered collection.

Yes: std::set.

> So... does that mean the iterator is a nested class then? (Just trying
> to understand the syntax.) Clearly each container type would end up
> needing a completely different iterator implementation...

Yes, each container has its own iterator. For a vector, it could even be a
plain old pointer instead of a class. And you don't even have to worry
about that :)

Post a reply to this message

> Is there a "set" type laying around somewhere? The thing I'm processing 
> *is* notionally a set, not an ordered collection.

std::set, I believe. Internally it uses a binary tree so it can quickly 
search for things. This means that whatever type you use it on has to work 
with the < operator; it uses < to know how to order the tree. (This is 
relevant because it means you have to define the < operator if you want to 
use it with your own class.)

You can google "std set" for documentation. This works for most or all STL 
types. The useful member function here is find( value ), which returns an 
iterator to the element with the given value, or returns yourset.end() 
otherwise. (Oh, insert() is useful too.)

 - Slime
 [ http://www.slimeland.com/ ]

Post a reply to this message

Slime wrote:
>> Is there a "set" type laying around somewhere? The thing I'm processing 
>> *is* notionally a set, not an ordered collection.
> 
> std::set, I believe. Internally it uses a binary tree so it can quickly 
> search for things. This means that whatever type you use it on has to work 
> with the < operator; it uses < to know how to order the tree. (This is 
> relevant because it means you have to define the < operator if you want to 
> use it with your own class.)

Heh. Exactly like Haskell's Data.Set ;-)

Question: What happens if your class doesn't have the comparison operator?

> You can google "std set" for documentation. This works for most or all STL 
> types. The useful member function here is find( value ), which returns an 
> iterator to the element with the given value, or returns yourset.end() 
> otherwise. (Oh, insert() is useful too.)

I'm more likely to be iterating the whole set and removing elements from 
it, but yeah. ;-)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

On Sun, 28 Sep 2008 10:41:43 +0200, Orchid XP v8 <voi### [at] devnull> wrote:
>
> Heh. Exactly like Haskell's Data.Set ;-)
>
> Question: What happens if your class doesn't have the comparison  
> operator?

You create a set with some other predicate as comparator.

I wonder: Do you not have access to documentation that explains this?



-- 
FE

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> >   Note that erase() is an O(n) operation.

> Yeah, that's kind of unavoidable.

  If the vector doesn't need to preserve the order of the elements then
you can remove the element in O(1) like this:

theVector[smallestInd] = theVector.back();
theVector.pop_back();

  In other words, copy the last element over the element to be removed,
and then remove the last element.

-- 
                                                          - Warp

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> Question: What happens if your class doesn't have the comparison operator?

  If there's no way you can add an operator<() for your class, then you
can give std::set a comparator. A comparator is a functor used to compare
two elements of the same type (it takes two parameters of the type in
question, and returns a boolean telling if the first parameter is less
than the second parameter). This happens, for example, like this:

struct MyComparator
{
    // Note that this member function must be of 'const' type:
    bool operator()(const MyClass& lhs, const MyClass& rhs) const
    {
        return /* is lhs less than rhs? */;
    }
};

int main()
{
    // Make a type alias, to simplify the usage:
    typedef std::set<MyClass, MyComparator> TheSetType;

    TheSetType theSet;
    ...
}

  If your comparator has some state which may be different between sets,
you can give an initialized instance of your comparator to the set:

    TheSetType theSet(MyComparator(initialization, values));

  It is also possible to create a comparison function and use as a functor
(as you might remember). However, the syntax of the TheSetType definition
becomes a bit complicated.

  By the way, std::set (as well as std::map) *always* takes a comparator
(rather than using the < operator directly). When none is specified, the
default comparator used is std::less which, by template magic, makes it
completely equivalent to comparing the elements with the < operator
directly.

  This is good to know because you might sometimes want the elements
sorted in some other way. For example, if you want to sort them in
decreasing order, you can use the std::greater comparator (provided
by the standard C++ library). For example:

    typedef std::set<int, std::greater<int> > TheSetType;

  All integers added to this set will be in decreasing order rather than
in increasing one.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Orchid XP v8 <voi### [at] devnull> wrote:
>> Question: What happens if your class doesn't have the comparison operator?
> 
>   If there's no way you can add an operator<() for your class, then you
> can give std::set a comparator.

>   It is also possible to create a comparison function and use as a functor
> (as you might remember). However, the syntax of the TheSetType definition
> becomes a bit complicated.
> 
>   By the way, std::set (as well as std::map) *always* takes a comparator
> (rather than using the < operator directly). When none is specified, the
> default comparator used is std::less which, by template magic, makes it
> completely equivalent to comparing the elements with the < operator
> directly.
> 
>   This is good to know because you might sometimes want the elements
> sorted in some other way.

Sounds quite flexible.

(In particular, Haskell's own Data.Set provides no way to specify an 
alternate comparison operator. But then again, it only needs *a* 
comparison operator; which one you use doesn't really affect anything 
user-visible. The "sort" function allows you to specify a comparison 
operator manually though...)

What I was really interested to know is whether trying to construct a 
set without a comparison operator yields a compile-time error, a runtime 
error, or simply undefined behaviour.

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> What I was really interested to know is whether trying to construct a 
> set without a comparison operator yields a compile-time error, a runtime 
> error, or simply undefined behaviour.

  We are talking about templates here. Everything happens at compile
time. :)

  (Although the error message will probably be quite obfuscated. With
the next C++ standard compilers will have means to directly say "your
type has no operator< but one is required".)

-- 
                                                          - Warp

Post a reply to this message

Slime wrote:
> thing after another. It's a lot like math - they don't teach fractions to 
> first graders because they need to spend time learning addition and 
> subtraction to fully master the concepts.

Ummm... They do teach basic fractions to first graders nowadays.

-- 
~Mike

Post a reply to this message