STL implementation performance

Hello,

We are using standard containers in our code except task specific parts
where we write our own specific containers that can handle huge data
and/or optimized for specific algorithms. But there are places where
some standard containers are used but implementation could be faster.
Correct me if i'm wrong, but in both Dinkumware & STLPort
implementations of rb_tree::equal_range are similar:

pair<iterator,iterator> equal_range(const key_type& x)
{
return pair<iterator, iterator>(lower_bound(x), upper_bound(x));
}

which has double cost for set/map and is not optimal for
multiset/multimap. Sure in case of set/map the usage of equal_range can
be replaced by lower_bound, but having standard function with obvious
flaw is not a good practice.

What do you think?

Regards,
    Armen


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
10/19/2005 8:48:40 AM
comp.lang.c++.moderated 10708 articles. 0 followers. allnor (8507) is leader. Post Follow

15 Replies
298 Views

Similar Articles

[PageSpeed] 46
"Nemra�" <armen_grigoryan@hotmail.com> wrote in message
news:1129707345.606089.294840@o13g2000cwo.googlegroups.com...

> We are using standard containers in our code except task specific parts
> where we write our own specific containers that can handle huge data
> and/or optimized for specific algorithms. But there are places where
> some standard containers are used but implementation could be faster.
> Correct me if i'm wrong, but in both Dinkumware & STLPort
> implementations of rb_tree::equal_range are similar:
>
> pair<iterator,iterator> equal_range(const key_type& x)
> {
> return pair<iterator, iterator>(lower_bound(x), upper_bound(x));
> }
>
> which has double cost for set/map and is not optimal for
> multiset/multimap. Sure in case of set/map the usage of equal_range can
> be replaced by lower_bound, but having standard function with obvious
> flaw is not a good practice.
>
> What do you think?

I think you need to find a realistic case where the difference
amounts to a hill of beans. If you do, you already know how
to do it faster, don't you?

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com



      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
P
10/20/2005 11:25:43 AM
Nemra� wrote:
> Hello,
>
> We are using standard containers in our code except task specific parts
> where we write our own specific containers that can handle huge data
> and/or optimized for specific algorithms. But there are places where
> some standard containers are used but implementation could be faster.
> Correct me if i'm wrong, but in both Dinkumware & STLPort
> implementations of rb_tree::equal_range are similar:
>
> pair<iterator,iterator> equal_range(const key_type& x)
> {
> return pair<iterator, iterator>(lower_bound(x), upper_bound(x));
> }
>
> which has double cost for set/map and is not optimal for
> multiset/multimap. Sure in case of set/map the usage of equal_range can
> be replaced by lower_bound, but having standard function with obvious
> flaw is not a good practice.
>
> What do you think?

I think you could call corresponding member function of set/map
directly. Or provide your own my::equal_range that does the right thing
for you, or hack the library and overload std::equal_range() for
std::set/map.


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Maxim
10/20/2005 12:53:24 PM
Nemra� wrote:
> Hello,
>
> We are using standard containers in our code except task specific parts
> where we write our own specific containers that can handle huge data
> and/or optimized for specific algorithms. But there are places where
> some standard containers are used but implementation could be faster.
> Correct me if i'm wrong, but in both Dinkumware & STLPort
> implementations of rb_tree::equal_range are similar:
>
> pair<iterator,iterator> equal_range(const key_type& x)
> {
> return pair<iterator, iterator>(lower_bound(x), upper_bound(x));
> }
>
> which has double cost for set/map and is not optimal for
> multiset/multimap. Sure in case of set/map the usage of equal_range can
> be replaced by lower_bound, but having standard function with obvious
> flaw is not a good practice.
>
> What do you think?

I think that describing the equal_range implementation above as
"obviously flawed" is not justified. On the contrary, the
implementation is obviously correct, combining as it does its two
logical sub-operations. And correctness has tremendous value,
especially in a library.

I would be disappointed though with any routine, that is the logical
combination of other routines, not to take advantage of any obvious
optimizations that the combination makes possible. To keep the
discussion abstract and free of reference to any existing library, I
will choose as an example, a different routine, say
std::string::replace. Now calling string::replace logically deletes
then inserts characters into a std::string. But I would not expect that
an implementation of std::string simply to call erase() and insert().
For one, an obvious opportunity for optimizing this operation would
have been lost, and worse, there is no further opportunity left to the
client to optimize this operation outside of std::string itself. In
other words, unless the optimization is made in the library, then it
cannot be made at all.

But there is a complication. Even though the library author is often in
the best position to make optimizations, it is the application author
who will know best which optimizations are needed for a particular
program. So there has to be some information flow back to the library
author from the library clients to the ensure that useful optimizations
can be made in the appropriate places.

So as a client of the library I would point out (or even supply code
with the suggested improvement) to the library author where a useful
optimization could be made. I would be careful to do so in a
constructive manner, especially when the existing implementation is
obviously correct, if not optimally efficient.

Greg


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Greg
10/21/2005 9:12:50 AM
Greg Herlihy wrote:

    [...]
> I would be disappointed though with any routine, that is the
> logical combination of other routines, not to take advantage
> of any obvious optimizations that the combination makes
> possible.  To keep the discussion abstract and free of
> reference to any existing library, I will choose as an
> example, a different routine, say std::string::replace.  Now
> calling string::replace logically deletes then inserts
> characters into a std::string. But I would not expect that an
> implementation of std::string simply to call erase() and
> insert().  For one, an obvious opportunity for optimizing this
> operation would have been lost, and worse, there is no further
> opportunity left to the client to optimize this operation
> outside of std::string itself.  In other words, unless the
> optimization is made in the library, then it cannot be made at
> all.

Not really relevant to the current discussion (unless to say
that you chose a bad example), but it would seem more reasonable
for erase and insert to be implemented in terms of replace.
After all, erase() is just replace() with an empty string, and
insert() replace a substring of length 0.

I don't know about current implementations, but that's the way
my pre-standard string was implemented.

(For the rest of what you said, concerning library correctness
and ways of communicating with library implementors, I can only
concur.)

--
James Kanze                                           GABI Software
Conseils en informatique orient�e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S�mard, 78210 St.-Cyr-l'�cole, France, +33 (0)1 30 23 00 34


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
kanze
10/21/2005 4:15:59 PM
Even if multiset is not the most used container, but here nobody could
make search faster unless he will hack the library code. So its usage
for "heavy" cases will bring to performance problem without easy
solution.
As i already wrote we replaced equal_range by lower_bound because we
know that we are using std::set, but not every user knows that they
differ in a time twice for some libraries. Becides we need to replace
this simple code:

std::pair<SetIt, SetIt> range = someSet.equal_range(someVal);
if (range.first != range.second)
{
     range.first = someSet.insert(range.first, someVal);
}
// use range.first which points to the required value

With the following:

SetIt it = someSet.lower_bound(someVal);
if (it == someSet.end() || someSet.key_comp(*it, someVal) ||
someSet.key_comp(someVal, *it))
{
     it = someSet.insert(it, someVal);
}
// use it which points to the required value

I'd prefer using first one...

Regards,
     Armen


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
iso
10/22/2005 1:49:19 PM
"Greg Herlihy" <greghe@pacbell.net> wrote in message 
news:1129850301.991311.94290@g14g2000cwa.googlegroups.com...

> But there is a complication. Even though the library author is often in
> the best position to make optimizations, it is the application author
> who will know best which optimizations are needed for a particular
> program. So there has to be some information flow back to the library
> author from the library clients to the ensure that useful optimizations
> can be made in the appropriate places.
>
> So as a client of the library I would point out (or even supply code
> with the suggested improvement) to the library author where a useful
> optimization could be made. I would be careful to do so in a
> constructive manner, especially when the existing implementation is
> obviously correct, if not optimally efficient.

And the library author might politely decline to make the
"obvious" improvement, in some cases, particularly  if there
is any chance that improving one use of the library might
deoptimize another use. Library authors must continually
guess, on the basis of incomplete information, what are
the best tradeoffs to make.

In the case originally cited in this thread, the OP presumed
that equal_range is suboptimal if it merely calls lower_bound
and upper_bound. But that is often the best approach, even
for a set or map with unique elements. If a user has reason
to believe that a *particular* set or map can find an
equal range faster -- say by calling lower_bound and testing
the element it designates (if any) -- and if the user has
reason to believe that the difference in performance *warrants*
writing, debugging, and maintaining a bespoke function,
then the user is of course free to do so. But there are
enough "if"s here to dissuade most library writers from
tinkering much with equal_range.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com



      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
P
10/22/2005 1:56:52 PM
On 22 Oct 2005 09:49:19 -0400, "Nemra�" <armen_grigoryan@hotmail.com>
wrote:

> As i already wrote we replaced equal_range by lower_bound because we
> know that we are using std::set, but not every user knows that they
> differ in a time twice for some libraries. Becides we need to replace
> this simple code:

> std::pair<SetIt, SetIt> range = someSet.equal_range(someVal);
> if (range.first != range.second)
> {
>      range.first = someSet.insert(range.first, someVal);
> }
> // use range.first which points to the required value

Since it does nothing, it is a good thing to replace it.  I'm sure the
real code must have == rather than !=.

> With the following:

> SetIt it = someSet.lower_bound(someVal);
> if (it == someSet.end() || someSet.key_comp(*it, someVal) ||
> someSet.key_comp(someVal, *it))

Some knowledge of lower_bound would help.  It returns end, something
larger, or the target.  Something less is impossible because that would
not be a lower bound.  Remove the redundant middle test.

> {
>      it = someSet.insert(it, someVal);
> }
> // use it which points to the required value

> I'd prefer using first one...

I can't imagine why.  The logic of the code makes no sense for a
multi_set because it prevents insertion of duplicates.  The best
possible code for equal_range in a set would be to determine lower_bound
and then make the above test to determine whether upper_bound is the
same or next item.  Now your code adds an extra test on top of that not
to mention returning two iterators when one was enough.  Using
equal_range on a set makes no sense.

John

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
John
10/24/2005 12:16:09 AM
John, thanks for pointing out mistakes!
My statement was that either equal_range should be optimized or it have
to be well documented, because it is easy for user who doesnt know the
library implementation well to get a performance flaw. Concerning
multi_set/multi_map: it might be hard to imagine where equal_range can
be used in a way that it is hard to replace it with different
processing, but again we come to the same conclusion: if equal_range
should be replaced for performance then why we need it at all?

Regards,
    Armen


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
iso
10/24/2005 9:01:21 AM
In article <1129707345.606089.294840@o13g2000cwo.googlegroups.com>,
 "Nemra�" <armen_grigoryan@hotmail.com> wrote:

> Hello,
> 
> We are using standard containers in our code except task specific parts
> where we write our own specific containers that can handle huge data
> and/or optimized for specific algorithms. But there are places where
> some standard containers are used but implementation could be faster.
> Correct me if i'm wrong, but in both Dinkumware & STLPort
> implementations of rb_tree::equal_range are similar:
> 
> pair<iterator,iterator> equal_range(const key_type& x)
> {
> return pair<iterator, iterator>(lower_bound(x), upper_bound(x));
> }
> 
> which has double cost for set/map and is not optimal for
> multiset/multimap. Sure in case of set/map the usage of equal_range can
> be replaced by lower_bound, but having standard function with obvious
> flaw is not a good practice.
> 
> What do you think?

Here's a test case I'm running:

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <time.h>

template <class F>
float
test(F f)
{
    std::vector<float> t;
    int i;
    for (i = 0; i < 10; ++i)
        t.push_back(f());
    double total_time = std::accumulate(t.begin(), t.end(), 0.0);
    while (i < 1000 && total_time < 1.0)
    {
        t.push_back(f());
        total_time += t.back();
        ++i;
    }
    std::sort(t.begin(), t.end());
    t.resize(t.size() * 9 / 10);
    return (float)(std::accumulate(t.begin(), t.end(), 0.0) / t.size());
}

const int M = 5;
const int N = 1000000;
const int F = N-1;

#include <set>

std::multiset<int> s;

void load(std::multiset<int>& s)
{
    for (int j = 0; j < N; ++j)
        for (int i = 0; i < M; ++i)
            s.insert(j);
}

float
time_multiset_equal_range()
{
    clock_t t = clock();
    {
    std::pair<std::set<int>::iterator, std::set<int>::iterator> p = 
s.equal_range(F);
    }
    t = clock() - t;
    return (float)(t/(double)CLOCKS_PER_SEC);
}

float
time_multiset_lower_upper()
{
    clock_t t = clock();
    {
    std::pair<std::set<int>::iterator, std::set<int>::iterator> p;
    p.first = s.lower_bound(F);
    p.second = s.upper_bound(F);
    }
    t = clock() - t;
    return (float)(t/(double)CLOCKS_PER_SEC);
}

int main()
{
    load(s);
    float t1 = test(time_multiset_equal_range);
    float t2 = test(time_multiset_lower_upper);
    std::cout << t2/t1 << '\n';
}

For me it prints out (approximately):

1.24239

YMMV.

The point of the test is to compare equal_range to calls to 
lower/upper_bound.  In the implementation I'm running, something has 
obviously been done to consistently increase the speed of equal_range 
over calls to lower/upper_bound by about 24%.  Maybe that is significant 
for you, maybe it isn't.  Obviously the number you get is going to vary 
with the tweaking parameters M, N and F.  But if you start consistently 
getting a number very close to 1 (and you can define "very close" 
yourself), perhaps you and your vendor should have a little talk.  If 
the number I've reported here doesn't amount to a hill of beans for you, 
then no action at all is warranted.

-Howard

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Howard
10/25/2005 12:45:34 PM
On 24 Oct 2005 05:01:21 -0400, "Nemra�" <armen_grigoryan@hotmail.com>
wrote:

> My statement was that either equal_range should be optimized or it have
> to be well documented, because it is easy for user who doesnt know the
> library implementation well to get a performance flaw. Concerning
> multi_set/multi_map: it might be hard to imagine where equal_range can
> be used in a way that it is hard to replace it with different
> processing, but again we come to the same conclusion: if equal_range
> should be replaced for performance then why we need it at all?

Well, we need it when it makes sense.  It might make sense for a
multi-set/map or other sorted container with duplicates.  Your real
question is about the associatives not using a more efficient algorithm.
My implementation has an efficient <algorithm> and your less than
efficient <tree>.  Since many libraries are derived from the original
HP/SGI library, yours may be the same.

Here is a little test program which compares the <algorithm> to the
<tree>.  The <algorithm> version is very inefficient, but is used to
show the number of compares which is the unit to count for search.

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <iterator>
#include <set>
using namespace std;
template <class N>
struct LinearProgression {
    N val;
    N inc;
    LinearProgression (N const& val = 0, N const& inc = 1)
: val(val - inc), inc(inc) {
        }
    N operator() () {
        return val += inc;
        }
    };
struct I {
    int i;
    I (int i = 0) : i(i) {
        }
    static int compares;
    };
int I::compares;
bool operator< (I lhs, I rhs) {
    ++ I::compares;
    return lhs.i < rhs.i;
    }
struct Test {
    multiset<I> const& s;
    int ca, cs;
    Test (multiset<I> const& s) : s(s), ca(0), cs(0) {
        }
    void operator() (I t) {
        I::compares = 0;
        equal_range(s.begin(), s.end(), t);
        ca += I::compares;
        I::compares = 0;
        s.equal_range(t);
        cs += I::compares;
        }
    ostream& print (ostream& os) const {
        return os << "algo " << ca << " member " << cs << endl;
        }
    };
int main (int, char** argv) {
    int max(atoi(argv[1]));
    max |= 1;
    multiset<I> data;
    for (int x(1); x != max; x += 2)
        for (int y = x; y & 1; y /= 2)
            data.insert(x);
    set<I> test;
    generate_n(inserter(test, test.end()), max / 2,
            LinearProgression<int>(1, 2));
    for_each(test.begin(), test.end(),
            Test(data)).print(cout << "Hit  ");
    test.clear();
    generate_n(inserter(test, test.end()), max / 2 + 1,
            LinearProgression<int>(0, 2));
    for_each(test.begin(), test.end(),
            Test(data)).print(cout << "Miss ");
    test.clear();
    generate_n(inserter(test, test.end()), max,
            LinearProgression<int>(0, 1));
    for_each(test.begin(), test.end(),
            Test(data)).print(cout << "All  ");
    }

My results for 1000 were:

Hit  algo 8183 member 10362
Miss algo 7526 member 10388
All  algo 15709 member 20750

The efficient algorithm is only 25% better than the inefficient member.
Is the difference worth changing the <tree> algorithm?  I wonder why the
two algorithms are not the same in a library.  History?

Maybe Code Warrior beats this with an efficient <tree>?

Maybe nobody cares?

John

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
John
10/25/2005 1:21:58 PM
On 25 Oct 2005 08:45:34 -0400, Howard Hinnant <howard.hinnant@gmail.com>
wrote:

> Here's a test case I'm running:

[snip]

> const int M = 5;
> const int N = 1000000;
> const int F = N-1;

[snip]

> float
> time_multiset_equal_range()
> {
>     clock_t t = clock();
>     {
>     std::pair<std::set<int>::iterator, std::set<int>::iterator> p =
> s.equal_range(F);

Is your implementation that slow or your clock that fast?

>     }
>     t = clock() - t;
>     return (float)(t/(double)CLOCKS_PER_SEC);
> }

[snip]

> int main()
> {
>     load(s);
>     float t1 = test(time_multiset_equal_range);
>     float t2 = test(time_multiset_lower_upper);
>     std::cout << t2/t1 << '\n';
> }

> For me it prints out (approximately):

> 1.24239

Knowing that it is your library, I will assume that you remember or
checked that equal_range in the tree really does do something other than
call lower and upper like most libraries.  However, I wonder what you
really measured with this test.

For me it prints NaNq because nothing is ever measured.  Adding a for
loop between the two calls of clock and executing 100 times gives
results.  I kicked it up to 100000 to get meaningful results.

Now I get 0.99 to 1.01 as expected for the gcc implementation.

> The point of the test is to compare equal_range to calls to
> lower/upper_bound.  In the implementation I'm running, something has
> obviously been done to consistently increase the speed of equal_range
> over calls to lower/upper_bound by about 24%.  Maybe that is significant
> for you, maybe it isn't.  Obviously the number you get is going to vary
> with the tweaking parameters M, N and F.  But if you start consistently
> getting a number very close to 1 (and you can define "very close"
> yourself), perhaps you and your vendor should have a little talk.  If
> the number I've reported here doesn't amount to a hill of beans for you,
> then no action at all is warranted.

Replacing the multiset with vector and using the general algorithms
where I know that equal_range is done well gives nice results.  Kicked
the loop up to 1000000 to get meaningful results.  Considering that you
used a search for N-1 which should go to a leaf before a match, I would
expect equal_range to be about twice as fast as the two calls.

I get 1.62 to 1.68.

If that 1.24 is really measuring something other than random clock tics,
maybe you should have a talk with your vendor.  :)

John

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
John
10/26/2005 1:07:27 PM
On 25 Oct 2005 08:45:34 -0400, Howard Hinnant <howard.hinnant@gmail.com>
wrote:

> For me it prints out (approximately):

> 1.24239

I modified the gcc library to do a "smart" equal_range.  Using your
tests with the loops to get meaningful results, I got about 2.  This is
a best case.  Changing F to 0 which searches down the other side making
two compares at each step, I got about 1.3.  This is a worst case.  On
average, we should expect about 1.5.

With the builtin < for int, turning on optimization gives more
improvements because the two compares are reduced to one.  The worst
case changed to about 1.7.  The unoptomized results above are realistic
for a complex compare.

John

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
John
10/26/2005 1:16:57 PM
In article <sJx7f.113$2y.40@newsread2.news.atl.earthlink.net>,
 John Potter <jpotter@lhup.edu> wrote:

> Is your implementation that slow or your clock that fast?

The clock is that fast.

> > For me it prints out (approximately):
> 
> > 1.24239
> 
> Knowing that it is your library, I will assume that you remember or
> checked that equal_range in the tree really does do something other than
> call lower and upper like most libraries.

<nod>

> However, I wonder what you
> really measured with this test.
> 
> For me it prints NaNq because nothing is ever measured.  Adding a for
> loop between the two calls of clock and executing 100 times gives
> results.  I kicked it up to 100000 to get meaningful results.

I should have mentioned the fast clock.

> Replacing the multiset with vector and using the general algorithms
> where I know that equal_range is done well gives nice results.  Kicked
> the loop up to 1000000 to get meaningful results.  Considering that you
> used a search for N-1 which should go to a leaf before a match, I would
> expect equal_range to be about twice as fast as the two calls.
> 
> I get 1.62 to 1.68.
> 
> If that 1.24 is really measuring something other than random clock tics,
> maybe you should have a talk with your vendor.  :)

To tell you the truth I was expecting something closer to what you got 
too.  But ...

In article <N4B7f.224$2y.141@newsread2.news.atl.earthlink.net>,
 John Potter <jpotter@lhup.edu> wrote:

> I modified the gcc library to do a "smart" equal_range.  Using your
> tests with the loops to get meaningful results, I got about 2.  This is
> a best case.  Changing F to 0 which searches down the other side making
> two compares at each step, I got about 1.3.  This is a worst case.  On
> average, we should expect about 1.5.
> 
> With the builtin < for int, turning on optimization gives more
> improvements because the two compares are reduced to one.  The worst
> case changed to about 1.7.  The unoptomized results above are realistic
> for a complex compare.

I'll just trust you to check that in, and thanks. :-)

-Howard

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
Howard
10/27/2005 9:29:25 AM
Hello,

Thanks for benchmarking! As you see difference can be big, because even
20% is a big number, when working with long-lasting algorithm.
Anyway, it's up to library implementors to provide effective solution
vs. easy-to-maintain one, so let's hope they will do us a favour...

Regards,
     Armen


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
iso
10/27/2005 10:36:30 AM
Nemra� wrote:
> Hello,
> 
> Thanks for benchmarking! As you see difference can be big, because even
> 20% is a big number, when working with long-lasting algorithm.
> Anyway, it's up to library implementors to provide effective solution
> vs. easy-to-maintain one, so let's hope they will do us a favour...
> 

Both STLport and libstdc++-v3 (the implementation of the C++ standard
library in g++) are open source. I know libstdc++-v3 is always happy to
consider patches which improve the library, and I'm sure STLport is
similar. Remember a reasonable mumber of the "library implementators"
are just C++ users who decided to start hacking at whatever
implementation of the standard library they happened to have lying around :)

Chris

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
chris
10/27/2005 4:40:43 PM
Reply:
Similar Artilces:

stl questions: how can I compare 2 stl list?
is there a better way to compare 2 stl list? I write a function like this below, but I wonder if there is a better way to achieve that (e.g. less code)? bool isSame(const list<int>& srcList, const list<int>& destList ) { if (srcList.size() != destList.size()) { return false; } int size = srcList.size(); for (int i = 0; i < size; i++) { if (srcList[i] != destList[i]) { return false; } } return true; } Thank you. silverburgh.meryl@gmail.com wrote: > is there a better way to compare 2 stl list? I write a function like > this below, but I wonder...

US-TX-Austin: Solutions Architect/Sales Eng.Design/config/implement SW apps; C-P (45329657601)
US-TX-Austin: Solutions Architect/Sales Eng.Design/config/implement SW apps; C-P (45329657601) ============================================================================================== Position: Solutions Architect/Sales Reference: SMC01698 Location: Austin TX Duration: C-P Skills: BS Degree in Computer Science, MIS, or equivalent combination of education and experience. Exp designing, configuring and implementing custom and packaged enterprise software applications (Java and .NET preferred). ...

how to implement a menu ?
hey, i'm having this problem when i'm trying to implement menu capability in my program, using direction key UP and DOWN to move the a bar between the menu items, press enter to select it, cudgle my brain hardly as possibly could I just couldn't figure out how to do this. and i'm using Visual C++ and I don't know if there's any library functions to handle text attributes like in Borland C (textcolor() etc.). so hope some could help me out, thanx in advance. int scan,extended; printf("1. log on system\n"); printf("2. log out system\n"); pri...

ANNOUNCE: Telecom Log Service Erlang Implementation (tlserl) 0.3.0
tlserl 0.3.0 is now available. tlserl is an Erlang implementation of the CORBA Telecom Log Service. It currently features: creation, persistence, deletion and search of log records for basic log only. WARNING: the current release is alpha quality; I've used it as a toy project to learn Erlang, Mnesia and the CORBA mapping. For more information on tlserl, see the wiki page on Bitbucket: https://bitbucket.org/tgg/tlserl/wiki/Home Source is available for download at: https://bitbucket.org/tgg/tlserl/downloads/tlserl-0.3.0.tar.gz MD5SUM 1ac4d232836d11acb2ed8b4bb2b86b...

String concatenation performance
I was just reading a "Python Speed/Performance Tips" article on the Python wiki http://wiki.python.org/moin/PythonSpeed/PerformanceTips and I got to the part that talks about string concatenation and that it is faster when using join instead of += because of strings being immutable. So I have tried it: from time import time t=time() s='almfklasmfkmaskmkmasfkmkqemkmqeqw' for x in range(40): #s+= s[len(s)/2:] s="".join((s,s[len(s)/2:])) print 'duration', time() - t And I get 1.55016708374 for the concatenation and 3.01116681099 for the join. I hav...

[ace-users] Re: Why ACE_Based_Pointer copy constructor is not implemented
Hi Ariel, > Is there a good reason for not implementing copy constructor for > ACE_Based_Pointer and ACE_Based_Pointer_Basic? As far as I can tell, there's a copy constructor implemented for both these classes: /// Copy constructor (not implemented yet). ACE_Based_Pointer (const ACE_Based_Pointer<CONCRETE> &); /// Copy constructor. ACE_Based_Pointer_Basic (const ACE_Based_Pointer_Basic<CONCRETE> &); To ensure that we have proper version/platform/compiler information, please make sure you fill out the appropriate problem report form (...

Tomcat 4.1.x Performance advice
Hi all, hopefully someone can offer some sagely advice regarding Production use of Jakarta's Tomcat. First, some brief background. My company have a servlet application that connects to a MySQL database. The servlet is deployed on two seperate win2k servers (Access to the tomcat servers is via DNS round robin load balancing). The database is on a another win2k server. These three servers are used for no other purpose than the servlet application. Three or four times a year, 4000 employees are required to access the servlet application across a time period of 14 days, each ...

Is there any Matrix in the STL?
Hi, Is there any kind of "std::matrix<>" in the STL that is optimized for matrix operations, or do I have to do a std::vector< std::vector<someType> > myMatrix; Best regards Daniel On Thu, 05 Feb 2004 14:06:23 +0100, DeMarcus wrote: > > Hi, > > Is there any kind of "std::matrix<>" in the STL that is optimized > for matrix operations, or do I have to do a > std::vector< std::vector<someType> > myMatrix; IMO, multiple dimension arrays in C and C++ are a pain in the ass, an issue that should have been addresse...

Try to understand the clisp implementation #3
Hi, I try to understand the clisp implementation and downloaded clisp-2.37-i686-pc-linux-gnu-2.6.8.tar.gz In the Makefile, target "base/lisp$(exe):", the cc command has a number of tags for which I cannot find any documentation on gnu.org. These tags are: -lcrypt -lm ; -ldl ; -lsigsegv ; -lc So far I have learned from the archives that -lsigsegv is related to ncurses. Anybody who knows where can I found more on these tags ? Apart from the above, I have run make, which cannot find -lsigsegv, although ncurses is installed. >From the archives I learn that the LD_LIBRARY_PATH needs ...

STL ?
Hi, I am getting compiling error on the following line. I could not figure it out. Could someone please kindly help me fixing the error ? //////////////////////////// Error message //////////////////// bash-2.05b$ g++ test5c.cpp test5c.cpp:20: error: parse error before numeric constant test5c.cpp: In function `int main()': test5c.cpp:36: error: `11' cannot be used as a function test5c.cpp: At global scope: test5c.cpp:48: error: parse error before numeric constant ////////////////// Below is the code //////////////////////////////// #include<iostream> #include <string> #inc...

US-TX-Austin: SQL DBA, Relational DB design, Design/implement, Erwin; 4M (45343357615)
US-TX-Austin: SQL DBA, Relational DB design, Design/implement, Erwin; 4M (45343357615) ====================================================================================== Position: SQL DBA Reference: SMC01989 Location: Austin TX Duration: 4M Skills: Strong understanding of relational database design and development 5+yrs full-time work experience in advanced design and implementation of Microsoft SQL Server-based databases 3+yrs full-time work experience using Microsoft SQL Server datab...

javascript implementation of XMLHTTP and SOAP objects?
I don't know enough about the technology yet to know whether this is a ridiculous question-- but is there no cross-browser javascript implementation of XMLHTTP and SOAP for use in calling web services? It looks as though MSFT expects the client to be running Windows and ActiveX and have certain DLLs installed; and Mozilla seems to have its own implementation of SOAP. Is it possible to implement these protocols in pure client-side javascript? Thanks! Timo On Tue, 25 May 2004 20:44:34 -0400, Timo <Timo@anonymous.biz> wrote: >I don't know enough about the technology yet ...

How to write the transform equivalent in STL?
I have the following code snippet: class converter { // ... public: virtual polar_point convert_to_polar(const point&) = 0; }; void f(const std::vector<point>& points, converter& cvt) { vector<polar_point> polarpoints(points.size()); for (unsigned int i = 0; i < points.size(); ++i) { polarpoints[i] = cvt.convert(points[i]); } print_points(polarpoints); // ... } I'd like to replace the for loop with an appropriate std::transform call. But I can't figure out...

How to implement a toolbox ?
Hello, I need to implement a steerable pyramids, but I could't find any information about toolbox design or implementation ? I have the steerable pyramids' equations and stuff but how do I design a toolbox ? Thanks a lot already for the fast replies... ...

To STL or not to STL
Hi there, I am interested to know if there are any C++ programmers who do not use STL. I have been coding in C++ for a year or so now, although only recently have I started a large(ish)-scale project. I do not use any STL, and I was wondering if there are any others out there that program in C++ without using STL? (Just to see if I am being stupid by not using it) Thanks Allan -- Allan Bruce Dept. of Computing Science University of Aberdeen Aberdeen AB24 3UE Scotland, UK Allan Bruce <allanmb@takeawayf2s.com> wrote: > I am interested to know if there are any C++ programmers who...

US-TX-Austin: Lead Gen/ Call center/ sales exp, Top Performer WANTED! ASAP! (45330857606)
US-TX-Austin: Lead Gen/ Call center/ sales exp, Top Performer WANTED! ASAP! (45330857606) ========================================================================================= Position: Lead Generator/Recruiter Reference: SMC01792 Location: Austin TX Duration: Perm Skills: Experienced LEAD GENERATOR / sales professional 2yrs previous CALL CENTER sales experience. College degree preferred, but not a must. Seasoned, phone sales professional, able to make 50-70 phone calls a day, and be an effective pla...

my little implementation of malloc
is it possible that a malloc function that use a nobody student is better than all yours :) How many errors do you see? Bug1: memory<13MB Bug2: it seems do you have to write you own sprintf "Ps_m" Ps_m(char* out, int len, char* fmt, ...) that has the len of array in the second arg #include <windows.h> #include <winbase.h> #include <wincon.h> #include <math.h> #include <float.h> #include <limits.h> #include <winuser.h> #include "winb.h" #define IVA_ INVALID_HANDLE_VALUE #define P printf #define W while #define...

Shall I implement this in javascript?
Hi all, I need to add a new functionality to our product, where I need to access some web services. Since our product is completely written in C++ thus I implemented this initially in C++ as well. However, the function requires changes frequently and maintaining the changes in C+ + with MS Soap toolkit is becoming a pain because it's no longer supported by Microsoft any more. Therefore, I'm considering implementing this using javascript and use an embedded IE control for the user interface. I'm new to javascript so I'm not sure if this is feasible at all. The web service access...

Fortran2003 and STL
When f2003 arrives will it have enough facilities for the STL (Standard Template Library) to be implemented? Is so would it be desirable, if not what is the mechanism by which standard data-structures (e.g. list, queue, stack, tree, map, set, ...) will made available to fortran programmers? You can have a look at http://flibs.sf.net to see how you can already do that with Fortran 90/95. Perhaps not as elegantly (and my code is not at all complete :)), but there are surely enough mechanisms to provide a clean (!) implementation. Regards, Arjen simon@whiteowl.co.uk wrote: > When f2003 a...

stl vector help
if I have: vector<Car*> car; vector<Car*>::iterator cari; for(cari = car.begin(); cari != car.end(); cari++) { *(cari)->printDetails(); } where printDetails() is a function in class Car why can I not comple this code the error? I get is: main.cpp: In function `int main()': main.cpp:75: error: base operand of `->' has non-pointer type `Car' * Greg: > if I have: > > > vector<Car*> car; > > vector<Car*>::iterator cari; > for(cari = car.begin(); cari != car.end(); cari++) > { > *(cari)->printDetails(); > ...

Ice Performance data released
We have conducted extensive performance tests for Ice, and compared the results against TAO, a popular high-performance CORBA implementation. You can view our results here: http://www.zeroc.com/performance/ We have tried to perform the tests as carefully and fair as possible, and have provided all information that is required to independently reproduce our results. Should there be anything unclear about how we conducted the performance tests, please feel free to use our forums to post your questions: http://www.zeroc.com/vbulletin/ Hi Folks, >> We have conducte...

NetApp filer OS and SMB/CIFS implementation origin
Hi all, A question, just wondering, The ONTAP OS, which Unix architecture is this OS based on and the SMB/CIFS accompanying the implementation? Does anybody have info on that? Cheers, Mike In article <30dd1747.0310290658.626c969d@posting.google.com>, midisam@wanadoo.nl <midisam@wanadoo.nl> wrote: >Hi all, > >A question, just wondering, >The ONTAP OS, which Unix architecture is this OS based on and the None, though it uses a small amount of machine-dependent code from NetBSD. >SMB/CIFS accompanying the implementation? Does anybody have info on...

US-TX-Austin: Lead Gen/ Call center/ sales exp, Top Performer WANTED! ASAP! (45359557607)
US-TX-Austin: Lead Gen/ Call center/ sales exp, Top Performer WANTED! ASAP! (45359557607) ========================================================================================= Position: Lead Generator/Recruiter Reference: SMC01792 Location: Austin TX Duration: Perm Skills: Experienced LEAD GENERATOR / sales professional 2yrs previous CALL CENTER sales experience. College degree preferred, but not a must. Seasoned, phone sales professional, able to make 50-70 phone calls a day, and be an effective pla...

[ANNOUNCE] CHSM: Statecharts implementation for C++ and Java
CHSM (Concurrent Hierarchical State Machine) is a Statecharts implementation for C++ and Java that allows one to integrate state definitions, event handlers, and transitions seamlessly into the host language's object model. CHSM allows normal Java or C++ code to be intermixed with the Statechart definition promoting a clear and natural programming paradigm. The CHSM is a full implementation of Harel's Statecharts and it is compliant with the UML 2.0 specification, including mechanisms for Statechart inheritance, event inheritance, and generic event dispatching. ...

Problem with my automatic pointer implementation
Hi, I assume, to be right here :-) My automatic pointer implementation is packaged into a macro, that could be placed into a class definition. I have the following code (snippets) that brought me to a problem: UAP(lb_I_Database, database, __FILE__, __LINE__) UAP(lb_I_Query, sampleQuery, __FILE__, __LINE__) long l; // This buffer gets overwritten. char buf[100]; // This not. wxWindow* firstButton; wxWindow* prevButton; wxWindow* nextButton; wxWindow* lastButton; If I do not include this long l or the char buffer, I get overwritten my real in use window member firstB...