Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

Any sufficiently advanced technology is indistinguishable from a rigged demo.


devel / comp.lang.c++ / "Inside STL: The map, set, multimap, and multiset" by Raymond Chen

SubjectAuthor
* "Inside STL: The map, set, multimap, and multiset" by Raymond ChenLynn McGuire
+* Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chenwij
|`* Re: "Inside STL: The map, set, multimap, and multiset" by RaymondPaavo Helde
| +* Re: "Inside STL: The map, set, multimap, and multiset" by Raymond ChenÖö Tiib
| |+- Re: "Inside STL: The map, set, multimap, and multiset" by RaymondBonita Montero
| |`* Re: "Inside STL: The map, set, multimap, and multiset" by RaymondBonita Montero
| | +* Re: "Inside STL: The map, set, multimap, and multiset" by Raymond ChenÖö Tiib
| | |`- Re: "Inside STL: The map, set, multimap, and multiset" by RaymondBonita Montero
| | `* Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chenwij
| |  `- Re: "Inside STL: The map, set, multimap, and multiset" by RaymondBonita Montero
| `* Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chenwij
|  `* Re: "Inside STL: The map, set, multimap, and multiset" by RaymondPaavo Helde
|   `- Re: "Inside STL: The map, set, multimap, and multiset" by Raymond ChenÖö Tiib
`- Re: "Inside STL: The map, set, multimap, and multiset" by Raymond ChenTim Rentsch

1
"Inside STL: The map, set, multimap, and multiset" by Raymond Chen

<uaubnm$3i781$1@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=975&group=comp.lang.c%2B%2B#975

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: lynnmcgu...@gmail.com (Lynn McGuire)
Newsgroups: comp.lang.c++
Subject: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen
Date: Tue, 8 Aug 2023 16:23:02 -0500
Organization: A noiseless patient Spider
Lines: 11
Message-ID: <uaubnm$3i781$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Tue, 8 Aug 2023 21:23:02 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="9689201a4d173b0c1ed3840c82193f85";
logging-data="3742977"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19T81ewpTLLRJB2Welts0GlRzaoPOHZnk8="
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:102.0) Gecko/20100101
Thunderbird/102.14.0
Cancel-Lock: sha1:XsmBhUaKGGf7Pi/q0P44D7spGgA=
Content-Language: en-US
 by: Lynn McGuire - Tue, 8 Aug 2023 21:23 UTC

"Inside STL: The map, set, multimap, and multiset" by Raymond Chen
https://devblogs.microsoft.com/oldnewthing/20230807-00/

"The complexity requirements of the C+ standard library map, set,
multimap, and multiset basically narrow the possible implementation
options to AVL trees and red-black trees."

"In practice, everybody seems to choose a red-black tree, with an
explicit sentinel node. The sentinel node also doubles as a header."

Lynn

Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen

<aaa09f64-8320-4b9f-bd86-91d800de81e1n@googlegroups.com>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=976&group=comp.lang.c%2B%2B#976

  copy link   Newsgroups: comp.lang.c++
X-Received: by 2002:a05:622a:1987:b0:405:5657:2510 with SMTP id u7-20020a05622a198700b0040556572510mr24258qtc.0.1691542396168;
Tue, 08 Aug 2023 17:53:16 -0700 (PDT)
X-Received: by 2002:a05:6808:1789:b0:3a7:8c2c:8c8e with SMTP id
bg9-20020a056808178900b003a78c2c8c8emr700863oib.11.1691542395651; Tue, 08 Aug
2023 17:53:15 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!diablo1.usenet.blueworldhosting.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.c++
Date: Tue, 8 Aug 2023 17:53:15 -0700 (PDT)
In-Reply-To: <uaubnm$3i781$1@dont-email.me>
Injection-Info: google-groups.googlegroups.com; posting-host=124.218.76.41; posting-account=0Ek0TQoAAAAS0oceh95IuNV59QuIWNeN
NNTP-Posting-Host: 124.218.76.41
References: <uaubnm$3i781$1@dont-email.me>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <aaa09f64-8320-4b9f-bd86-91d800de81e1n@googlegroups.com>
Subject: Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen
From: wynii...@gmail.com (wij)
Injection-Date: Wed, 09 Aug 2023 00:53:16 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 2842
 by: wij - Wed, 9 Aug 2023 00:53 UTC

On Wednesday, August 9, 2023 at 5:23:23 AM UTC+8, Lynn McGuire wrote:
> "Inside STL: The map, set, multimap, and multiset" by Raymond Chen
> https://devblogs.microsoft.com/oldnewthing/20230807-00/
>
> "The complexity requirements of the C+ standard library map, set,
> multimap, and multiset basically narrow the possible implementation
> options to AVL trees and red-black trees."
>
> "In practice, everybody seems to choose a red-black tree, with an
> explicit sentinel node. The sentinel node also doubles as a header."
>
> Lynn

/*
Compare speed of Wy::Subset and std::set
*/
#include <Wy.stdlib.h>
#include <Wy.stdio.h>
#include <Wy.time.h>
#include <CSCall/Subset.h>
#include <set>

using namespace Wy;

void test() {
typedef int ElemType;
const size_t Cnt=1000000;
Rand48 rnd;
Timespec tm0,tm1;

Subset<ElemType> aa;
tm0=now(CLOCK_THREAD_CPUTIME_ID);
for(size_t i=0; i<Cnt; ++i) {
aa.insert(rnd.i32()%(Cnt/2));
}
cout << "Subset: " << (now(CLOCK_THREAD_CPUTIME_ID)-tm0) << WY_ENDL;

std::set<ElemType> bb;
tm0=now(CLOCK_THREAD_CPUTIME_ID);
for(size_t i=0; i<Cnt; ++i) {
bb.insert(rnd.i32()%(Cnt/2));
}
cout << "std::set: " << (now(CLOCK_THREAD_CPUTIME_ID)-tm0) << WY_ENDL;
};

int main(int argc, const char* argv[])
try {
test();
return 0;
} catch(const Errno& e) {
cerr << wrd(e) << WY_ENDL;
return -1;
} catch(...) {
cerr << "main() caught(...)" WY_ENDL;
throw;
};

-----------
[]$ ./sp_set
Subset: 0.562357101
std::set: 0.826916740

[]$ make sp_set CFLAGS=-O2
[]$ ./sp_set
Subset: 0.388614721
std::set: 0.413042782

Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen

<uavbi9$3q20f$1@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=979&group=comp.lang.c%2B%2B#979

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: eesn...@osa.pri.ee (Paavo Helde)
Newsgroups: comp.lang.c++
Subject: Re: "Inside STL: The map, set, multimap, and multiset" by Raymond
Chen
Date: Wed, 9 Aug 2023 09:26:16 +0300
Organization: A noiseless patient Spider
Lines: 72
Message-ID: <uavbi9$3q20f$1@dont-email.me>
References: <uaubnm$3i781$1@dont-email.me>
<aaa09f64-8320-4b9f-bd86-91d800de81e1n@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Wed, 9 Aug 2023 06:26:17 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="543e35197c7f803004998909477c8b58";
logging-data="3999759"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18gSNd1cjJHQFKGf60CckOIkdE1h/Erz4Y="
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:102.0) Gecko/20100101
Thunderbird/102.14.0
Cancel-Lock: sha1:D3gvIqZFBzt8P4TkrzbECGdOLZU=
In-Reply-To: <aaa09f64-8320-4b9f-bd86-91d800de81e1n@googlegroups.com>
Content-Language: en-US
 by: Paavo Helde - Wed, 9 Aug 2023 06:26 UTC

09.08.2023 03:53 wij kirjutas:
> /*
> Compare speed of Wy::Subset and std::set
> */
>
> []$ make sp_set CFLAGS=-O2
> []$ ./sp_set
> Subset: 0.388614721
> std::set: 0.413042782

I guess this shows that it is not really worth of effort to reinvent
one's own std::set.

If the point is that one can fine-tune something to beat a single
performance test, then I can do better. My my_set below beats std::set
100x for this insertion test ;-)

my_set: 0.006683
std::set: 0.597735

#include <set>
#include <chrono>
#include <random>
#include <iostream>
#include <vector>

void test() {
typedef int ElemType;
const size_t Cnt = 1000000;

std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> distr(0, Cnt / 2);

std::vector<unsigned char> my_set(Cnt / 2);
auto tm0 = std::chrono::high_resolution_clock::now();
for (size_t i = 0; i < Cnt; ++i) {
my_set[distr(gen)] = 1;
}
auto tm1 = std::chrono::high_resolution_clock::now();
double duration =
std::chrono::duration_cast<std::chrono::duration<double>>(tm1 -
tm0).count();
std::cout << "my_set: " << duration << "\n";

std::set<ElemType> bb;
tm0 = std::chrono::high_resolution_clock::now();
for (size_t i = 0; i < Cnt; ++i) {
bb.insert(distr(gen));
}
tm1 = std::chrono::high_resolution_clock::now();
duration =
std::chrono::duration_cast<std::chrono::duration<double>>(tm1 -
tm0).count();
std::cout << "std::set: " << duration << "\n";
};

int main(int argc, const char* argv[]) {
try {
test();
} catch (const std::exception& e) {
std::cerr << "Exception: " << e.what() << "\n";
return EXIT_FAILURE;
} catch (...) {
std::cerr << "Exception\n";
return EXIT_FAILURE;
}
}

Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen

<28833c3b-c58f-48f5-8ce4-6bbdce6f58d3n@googlegroups.com>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=981&group=comp.lang.c%2B%2B#981

  copy link   Newsgroups: comp.lang.c++
X-Received: by 2002:a05:622a:19a0:b0:40f:17f1:541 with SMTP id u32-20020a05622a19a000b0040f17f10541mr45406qtc.13.1691575720845;
Wed, 09 Aug 2023 03:08:40 -0700 (PDT)
X-Received: by 2002:a63:7b0e:0:b0:564:aca2:b22c with SMTP id
w14-20020a637b0e000000b00564aca2b22cmr64292pgc.4.1691575720282; Wed, 09 Aug
2023 03:08:40 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!209.85.160.216.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.c++
Date: Wed, 9 Aug 2023 03:08:39 -0700 (PDT)
In-Reply-To: <uavbi9$3q20f$1@dont-email.me>
Injection-Info: google-groups.googlegroups.com; posting-host=84.50.190.130; posting-account=pysjKgkAAACLegAdYDFznkqjgx_7vlUK
NNTP-Posting-Host: 84.50.190.130
References: <uaubnm$3i781$1@dont-email.me> <aaa09f64-8320-4b9f-bd86-91d800de81e1n@googlegroups.com>
<uavbi9$3q20f$1@dont-email.me>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <28833c3b-c58f-48f5-8ce4-6bbdce6f58d3n@googlegroups.com>
Subject: Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen
From: oot...@hot.ee (Öö Tiib)
Injection-Date: Wed, 09 Aug 2023 10:08:40 +0000
Content-Type: text/plain; charset="UTF-8"
 by: Öö Tiib - Wed, 9 Aug 2023 10:08 UTC

On Wednesday, 9 August 2023 at 09:26:32 UTC+3, Paavo Helde wrote:
> 09.08.2023 03:53 wij kirjutas:
> > /*
> > Compare speed of Wy::Subset and std::set
> > */
> >
> > []$ make sp_set CFLAGS=-O2
> > []$ ./sp_set
> > Subset: 0.388614721
> > std::set: 0.413042782
> I guess this shows that it is not really worth of effort to reinvent
> one's own std::set.
>
> If the point is that one can fine-tune something to beat a single
> performance test, then I can do better. My my_set below beats std::set
> 100x for this insertion test ;-)
>
> my_set: 0.006683
> std::set: 0.597735
>
Great example, intersting how std::bitset<500000> and
std::vector<bool>(500000) perform compared to that "my_set".

Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen

<uavstu$3tlid$1@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=982&group=comp.lang.c%2B%2B#982

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!news.eternal-september.org!.POSTED.ip-084-119-085-244.um24.pools.vodafone-ip.de!not-for-mail
From: Bonita.M...@gmail.com (Bonita Montero)
Newsgroups: comp.lang.c++
Subject: Re: "Inside STL: The map, set, multimap, and multiset" by Raymond
Chen
Date: Wed, 9 Aug 2023 13:22:41 +0200
Organization: A noiseless patient Spider
Message-ID: <uavstu$3tlid$1@dont-email.me>
References: <uaubnm$3i781$1@dont-email.me>
<aaa09f64-8320-4b9f-bd86-91d800de81e1n@googlegroups.com>
<uavbi9$3q20f$1@dont-email.me>
<28833c3b-c58f-48f5-8ce4-6bbdce6f58d3n@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 9 Aug 2023 11:22:38 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="ip-084-119-085-244.um24.pools.vodafone-ip.de:84.119.85.244";
logging-data="4118093"; mail-complaints-to="abuse@eternal-september.org"
User-Agent: Mozilla Thunderbird
Content-Language: de-DE
In-Reply-To: <28833c3b-c58f-48f5-8ce4-6bbdce6f58d3n@googlegroups.com>
 by: Bonita Montero - Wed, 9 Aug 2023 11:22 UTC

Am 09.08.2023 um 12:08 schrieb Öö Tiib:

> Great example, intersting how std::bitset<500000> and
> std::vector<bool>(500000) perform compared to that "my_set".

I think both are as fast and yours is at best as fast.

Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen

<uavumo$3ttih$1@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=984&group=comp.lang.c%2B%2B#984

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!news.eternal-september.org!.POSTED.ip-084-119-085-244.um24.pools.vodafone-ip.de!not-for-mail
From: Bonita.M...@gmail.com (Bonita Montero)
Newsgroups: comp.lang.c++
Subject: Re: "Inside STL: The map, set, multimap, and multiset" by Raymond
Chen
Date: Wed, 9 Aug 2023 13:52:59 +0200
Organization: A noiseless patient Spider
Message-ID: <uavumo$3ttih$1@dont-email.me>
References: <uaubnm$3i781$1@dont-email.me>
<aaa09f64-8320-4b9f-bd86-91d800de81e1n@googlegroups.com>
<uavbi9$3q20f$1@dont-email.me>
<28833c3b-c58f-48f5-8ce4-6bbdce6f58d3n@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 9 Aug 2023 11:52:56 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="ip-084-119-085-244.um24.pools.vodafone-ip.de:84.119.85.244";
logging-data="4126289"; mail-complaints-to="abuse@eternal-september.org"
User-Agent: Mozilla Thunderbird
Content-Language: de-DE
In-Reply-To: <28833c3b-c58f-48f5-8ce4-6bbdce6f58d3n@googlegroups.com>
 by: Bonita Montero - Wed, 9 Aug 2023 11:52 UTC

Am 09.08.2023 um 12:08 schrieb Öö Tiib:

> Great example, intersting how std::bitset<500000> and
> std::vector<bool>(500000) perform compared to that "my_set".

With this code bitset and vector<bool> have the same performance
under Windows (MSVC) and Linux (g++ / clang++).

#include <iostream>
#include <bitset>
#include <vector>
#include <random>
#include <chrono>
#include <atomic>

using namespace std;
using namespace chrono;

atomic<size_t> aSum;

int main()
{ constexpr size_t BITS = 0x10000;
bitset<BITS> bs;
vector<bool> vb( BITS );
mt19937_64 mt;
uniform_int_distribution<size_t> iBit( 0, BITS - 1 );
auto fill = []( auto &container )
{
bool bit = false;
for( size_t i = 0; i != BITS; ++i )
container[i] = bit,
bit = !bit;
};
fill( bs );
fill( vb );
constexpr size_t ROUNDS = 1'000;
auto linearBench = []( char const *what, auto const &container )
{
auto start = high_resolution_clock::now();
size_t sum = 0;
for( size_t r = ROUNDS; r--; )
for( size_t i = 0; i != BITS; ++i )
sum += container[i];
double ns = duration_cast<nanoseconds>( high_resolution_clock::now() -
start ).count() / ((double)BITS * ROUNDS);
::aSum = sum;
cout << what << ns << endl;
};
linearBench( "linear bitset: ", bs );
linearBench( "linear vector: ", vb );
auto gappedBench = []( char const *what, auto const &container )
{
auto start = high_resolution_clock::now();
size_t sum = 0;
for( size_t r = ROUNDS; r--; )
for( size_t g = 0, i = 0; g != BITS; ++g, i += 7, i = i < BITS ? i : 0 )
sum += container[i];
double ns = duration_cast<nanoseconds>( high_resolution_clock::now() -
start ).count() / ((double)BITS * ROUNDS);
::aSum = sum;
cout << what << ns << endl;
};
gappedBench( "gapped bitset: ", bs );
gappedBench( "gapped vector: ", vb );
}

Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen

<f1354b8a-5e4e-455d-b355-9f3a090d7600n@googlegroups.com>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=985&group=comp.lang.c%2B%2B#985

  copy link   Newsgroups: comp.lang.c++
X-Received: by 2002:a05:620a:1d07:b0:76c:af53:39fc with SMTP id dl7-20020a05620a1d0700b0076caf5339fcmr48403qkb.7.1691583011422;
Wed, 09 Aug 2023 05:10:11 -0700 (PDT)
X-Received: by 2002:a17:902:f685:b0:1b9:d335:1742 with SMTP id
l5-20020a170902f68500b001b9d3351742mr141723plg.11.1691583011192; Wed, 09 Aug
2023 05:10:11 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!209.85.160.216.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.c++
Date: Wed, 9 Aug 2023 05:10:10 -0700 (PDT)
In-Reply-To: <uavumo$3ttih$1@dont-email.me>
Injection-Info: google-groups.googlegroups.com; posting-host=84.50.190.130; posting-account=pysjKgkAAACLegAdYDFznkqjgx_7vlUK
NNTP-Posting-Host: 84.50.190.130
References: <uaubnm$3i781$1@dont-email.me> <aaa09f64-8320-4b9f-bd86-91d800de81e1n@googlegroups.com>
<uavbi9$3q20f$1@dont-email.me> <28833c3b-c58f-48f5-8ce4-6bbdce6f58d3n@googlegroups.com>
<uavumo$3ttih$1@dont-email.me>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <f1354b8a-5e4e-455d-b355-9f3a090d7600n@googlegroups.com>
Subject: Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen
From: oot...@hot.ee (Öö Tiib)
Injection-Date: Wed, 09 Aug 2023 12:10:11 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
 by: Öö Tiib - Wed, 9 Aug 2023 12:10 UTC

On Wednesday, 9 August 2023 at 14:53:14 UTC+3, Bonita Montero wrote:
> Am 09.08.2023 um 12:08 schrieb Öö Tiib:
> > Great example, intersting how std::bitset<500000> and
> > std::vector<bool>(500000) perform compared to that "my_set".
> With this code bitset and vector<bool> have the same performance
> under Windows (MSVC) and Linux (g++ / clang++).
>
> uniform_int_distribution<size_t> iBit( 0, BITS - 1 );

Unused variable "iBit", must be your test tests some other test case
as "distr" of Paavo was used in his tests.

Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen

<ub026o$3uqs6$1@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=986&group=comp.lang.c%2B%2B#986

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!news.eternal-september.org!.POSTED.ip-084-119-085-244.um24.pools.vodafone-ip.de!not-for-mail
From: Bonita.M...@gmail.com (Bonita Montero)
Newsgroups: comp.lang.c++
Subject: Re: "Inside STL: The map, set, multimap, and multiset" by Raymond
Chen
Date: Wed, 9 Aug 2023 14:52:43 +0200
Organization: A noiseless patient Spider
Message-ID: <ub026o$3uqs6$1@dont-email.me>
References: <uaubnm$3i781$1@dont-email.me>
<aaa09f64-8320-4b9f-bd86-91d800de81e1n@googlegroups.com>
<uavbi9$3q20f$1@dont-email.me>
<28833c3b-c58f-48f5-8ce4-6bbdce6f58d3n@googlegroups.com>
<uavumo$3ttih$1@dont-email.me>
<f1354b8a-5e4e-455d-b355-9f3a090d7600n@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 9 Aug 2023 12:52:41 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="ip-084-119-085-244.um24.pools.vodafone-ip.de:84.119.85.244";
logging-data="4156294"; mail-complaints-to="abuse@eternal-september.org"
User-Agent: Mozilla Thunderbird
Content-Language: de-DE
In-Reply-To: <f1354b8a-5e4e-455d-b355-9f3a090d7600n@googlegroups.com>
 by: Bonita Montero - Wed, 9 Aug 2023 12:52 UTC

Am 09.08.2023 um 14:10 schrieb Öö Tiib:
> On Wednesday, 9 August 2023 at 14:53:14 UTC+3, Bonita Montero wrote:
>> Am 09.08.2023 um 12:08 schrieb Öö Tiib:
>>> Great example, intersting how std::bitset<500000> and
>>> std::vector<bool>(500000) perform compared to that "my_set".
>> With this code bitset and vector<bool> have the same performance
>> under Windows (MSVC) and Linux (g++ / clang++).
>>
>> uniform_int_distribution<size_t> iBit( 0, BITS - 1 );
>
> Unused variable "iBit", must be your test tests some other test case
> as "distr" of Paavo was used in his tests.

I made it even shorter:

#include <iostream>
#include <bitset>
#include <vector>
#include <random>
#include <chrono>
#include <atomic>

using namespace std;
using namespace chrono;

atomic<size_t> aSum;

int main()
{ constexpr size_t BITS = 0x10000;
bitset<BITS> bs;
vector<bool> vb( BITS );
mt19937_64 mt;
auto fill = []( auto &container )
{
bool bit = false;
for( size_t i = 0; i != BITS; ++i )
container[i] = bit,
bit = !bit;
};
fill( bs );
fill( vb );
constexpr size_t ROUNDS = 10'000;
auto bench = []( char const *what, auto const &container, auto next )
{
auto start = high_resolution_clock::now();
size_t sum = 0;
for( size_t r = ROUNDS; r--; )
for( size_t g = 0, i = 0; g != BITS; ++g, i = next( i ) )
sum += container[i];
double ns = duration_cast<nanoseconds>( high_resolution_clock::now() -
start ).count() / ((double)BITS * ROUNDS);
::aSum = sum;
cout << what << ns << endl;
};
auto linear = []( size_t i ) { return i + 1; };
bench( "linear bitset: ", bs, linear );
bench( "linear vector: ", vb, linear );
auto gapped = []( size_t i ) { return i + 7 < BITS ? i + 7 : 0; };
bench( "gapped bitset: ", bs, gapped );
bench( "gapped vector: ", vb, gapped );
}

Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen

<590410fa-ae5b-4d85-a56d-560f6549e3ccn@googlegroups.com>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=989&group=comp.lang.c%2B%2B#989

  copy link   Newsgroups: comp.lang.c++
X-Received: by 2002:a37:b481:0:b0:762:407d:3837 with SMTP id d123-20020a37b481000000b00762407d3837mr46365qkf.6.1691590830556;
Wed, 09 Aug 2023 07:20:30 -0700 (PDT)
X-Received: by 2002:a05:6a00:190f:b0:687:322c:b72e with SMTP id
y15-20020a056a00190f00b00687322cb72emr274609pfi.5.1691590829983; Wed, 09 Aug
2023 07:20:29 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.cmpublishers.com!usenet.blueworldhosting.com!diablo1.usenet.blueworldhosting.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.c++
Date: Wed, 9 Aug 2023 07:20:29 -0700 (PDT)
In-Reply-To: <uavbi9$3q20f$1@dont-email.me>
Injection-Info: google-groups.googlegroups.com; posting-host=124.218.76.41; posting-account=0Ek0TQoAAAAS0oceh95IuNV59QuIWNeN
NNTP-Posting-Host: 124.218.76.41
References: <uaubnm$3i781$1@dont-email.me> <aaa09f64-8320-4b9f-bd86-91d800de81e1n@googlegroups.com>
<uavbi9$3q20f$1@dont-email.me>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <590410fa-ae5b-4d85-a56d-560f6549e3ccn@googlegroups.com>
Subject: Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen
From: wynii...@gmail.com (wij)
Injection-Date: Wed, 09 Aug 2023 14:20:30 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 3929
 by: wij - Wed, 9 Aug 2023 14:20 UTC

On Wednesday, August 9, 2023 at 2:26:32 PM UTC+8, Paavo Helde wrote:
> 09.08.2023 03:53 wij kirjutas:
> > /*
> > Compare speed of Wy::Subset and std::set
> > */
> >
> > []$ make sp_set CFLAGS=-O2
> > []$ ./sp_set
> > Subset: 0.388614721
> > std::set: 0.413042782
> I guess this shows that it is not really worth of effort to reinvent
> one's own std::set.

About the 'reinventing' things, I think C++ programmer should be able to
reinvent things. Otherwise why learning C++ (lots in stdc++ lib are about
implement things)? Isn't Python or others better?

One of the feature of Wy::Subset is that Subset has a member objimag(), allowing
the instance be saved to hard disk and read back (fast). I normally need Subset
for analysis of large data (10 Gbytes), many of them, e.g. generating 10
instances and read back as needed, this is because of the limits of RAM.

> If the point is that one can fine-tune something to beat a single
> performance test, then I can do better. My my_set below beats std::set
> 100x for this insertion test ;-)
>
> my_set: 0.006683
> std::set: 0.597735
>
> #include <set>
> #include <chrono>
> #include <random>
> #include <iostream>
> #include <vector>
> void test() {
> typedef int ElemType;
> const size_t Cnt = 1000000;
> std::random_device rd;
> std::mt19937 gen(rd());
> std::uniform_int_distribution<> distr(0, Cnt / 2);
>
> std::vector<unsigned char> my_set(Cnt / 2);
> auto tm0 = std::chrono::high_resolution_clock::now();
> for (size_t i = 0; i < Cnt; ++i) {
> my_set[distr(gen)] = 1;
> }
> auto tm1 = std::chrono::high_resolution_clock::now();
> double duration =
> std::chrono::duration_cast<std::chrono::duration<double>>(tm1 -
> tm0).count();
> std::cout << "my_set: " << duration << "\n";
>
> std::set<ElemType> bb;
> tm0 = std::chrono::high_resolution_clock::now();
> for (size_t i = 0; i < Cnt; ++i) {
> bb.insert(distr(gen));
> }
> tm1 = std::chrono::high_resolution_clock::now();
> duration =
> std::chrono::duration_cast<std::chrono::duration<double>>(tm1 -
> tm0).count();
> std::cout << "std::set: " << duration << "\n";
> };
>
> int main(int argc, const char* argv[]) {
> try {
> test();
> } catch (const std::exception& e) {
> std::cerr << "Exception: " << e.what() << "\n";
> return EXIT_FAILURE;
> } catch (...) {
> std::cerr << "Exception\n";
> return EXIT_FAILURE;
> }
> }

Why you show the comparison of std::vector's random access and std::set's insert?

Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen

<148d38f3-f6d9-49f5-9e5d-2b77b95e0713n@googlegroups.com>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=990&group=comp.lang.c%2B%2B#990

  copy link   Newsgroups: comp.lang.c++
X-Received: by 2002:ad4:4f26:0:b0:63d:30af:71b5 with SMTP id fc6-20020ad44f26000000b0063d30af71b5mr54663qvb.1.1691591537242;
Wed, 09 Aug 2023 07:32:17 -0700 (PDT)
X-Received: by 2002:a65:641a:0:b0:55a:c8fc:c5c7 with SMTP id
a26-20020a65641a000000b0055ac8fcc5c7mr205467pgv.6.1691591536648; Wed, 09 Aug
2023 07:32:16 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!209.85.160.216.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.c++
Date: Wed, 9 Aug 2023 07:32:15 -0700 (PDT)
In-Reply-To: <uavumo$3ttih$1@dont-email.me>
Injection-Info: google-groups.googlegroups.com; posting-host=124.218.76.41; posting-account=0Ek0TQoAAAAS0oceh95IuNV59QuIWNeN
NNTP-Posting-Host: 124.218.76.41
References: <uaubnm$3i781$1@dont-email.me> <aaa09f64-8320-4b9f-bd86-91d800de81e1n@googlegroups.com>
<uavbi9$3q20f$1@dont-email.me> <28833c3b-c58f-48f5-8ce4-6bbdce6f58d3n@googlegroups.com>
<uavumo$3ttih$1@dont-email.me>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <148d38f3-f6d9-49f5-9e5d-2b77b95e0713n@googlegroups.com>
Subject: Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen
From: wynii...@gmail.com (wij)
Injection-Date: Wed, 09 Aug 2023 14:32:17 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
 by: wij - Wed, 9 Aug 2023 14:32 UTC

On Wednesday, August 9, 2023 at 7:53:14 PM UTC+8, Bonita Montero wrote:
> Am 09.08.2023 um 12:08 schrieb Öö Tiib:
> > Great example, intersting how std::bitset<500000> and
> > std::vector<bool>(500000) perform compared to that "my_set".
> With this code bitset and vector<bool> have the same performance
> under Windows (MSVC) and Linux (g++ / clang++).
>
> #include <iostream>
> #include <bitset>
> #include <vector>
> #include <random>
> #include <chrono>
> #include <atomic>
>
> using namespace std;
> using namespace chrono;
>
> atomic<size_t> aSum;
>
> int main()
> {
> constexpr size_t BITS = 0x10000;
> bitset<BITS> bs;
> vector<bool> vb( BITS );
> mt19937_64 mt;
> uniform_int_distribution<size_t> iBit( 0, BITS - 1 );
> auto fill = []( auto &container )
> {
> bool bit = false;
> for( size_t i = 0; i != BITS; ++i )
> container[i] = bit,
> bit = !bit;
> };
> fill( bs );
> fill( vb );
> constexpr size_t ROUNDS = 1'000;
> auto linearBench = []( char const *what, auto const &container )
> {
> auto start = high_resolution_clock::now();
> size_t sum = 0;
> for( size_t r = ROUNDS; r--; )
> for( size_t i = 0; i != BITS; ++i )
> sum += container[i];
> double ns = duration_cast<nanoseconds>( high_resolution_clock::now() -
> start ).count() / ((double)BITS * ROUNDS);
> ::aSum = sum;
> cout << what << ns << endl;
> };
> linearBench( "linear bitset: ", bs );
> linearBench( "linear vector: ", vb );
> auto gappedBench = []( char const *what, auto const &container )
> {
> auto start = high_resolution_clock::now();
> size_t sum = 0;
> for( size_t r = ROUNDS; r--; )
> for( size_t g = 0, i = 0; g != BITS; ++g, i += 7, i = i < BITS ? i : 0 )
> sum += container[i];
> double ns = duration_cast<nanoseconds>( high_resolution_clock::now() -
> start ).count() / ((double)BITS * ROUNDS);
> ::aSum = sum;
> cout << what << ns << endl;
> };
> gappedBench( "gapped bitset: ", bs );
> gappedBench( "gapped vector: ", vb );
> }

I can't read these new C++ syntax. In case of 'vector<bool>', I would use
Wy::VLInt<unsigned int> (Very Large Integer), two access members bit(size_t)
and set_bit(size_t,bool). As you can see, every thing is 'concrete' and
direct. But such classes are not the purpose of libwy.

Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen

<ub089j$3vlgc$1@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=991&group=comp.lang.c%2B%2B#991

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!news.eternal-september.org!.POSTED.ip-084-119-085-244.um24.pools.vodafone-ip.de!not-for-mail
From: Bonita.M...@gmail.com (Bonita Montero)
Newsgroups: comp.lang.c++
Subject: Re: "Inside STL: The map, set, multimap, and multiset" by Raymond
Chen
Date: Wed, 9 Aug 2023 16:36:38 +0200
Organization: A noiseless patient Spider
Message-ID: <ub089j$3vlgc$1@dont-email.me>
References: <uaubnm$3i781$1@dont-email.me>
<aaa09f64-8320-4b9f-bd86-91d800de81e1n@googlegroups.com>
<uavbi9$3q20f$1@dont-email.me>
<28833c3b-c58f-48f5-8ce4-6bbdce6f58d3n@googlegroups.com>
<uavumo$3ttih$1@dont-email.me>
<148d38f3-f6d9-49f5-9e5d-2b77b95e0713n@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 9 Aug 2023 14:36:35 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="ip-084-119-085-244.um24.pools.vodafone-ip.de:84.119.85.244";
logging-data="4183564"; mail-complaints-to="abuse@eternal-september.org"
User-Agent: Mozilla Thunderbird
Content-Language: de-DE
In-Reply-To: <148d38f3-f6d9-49f5-9e5d-2b77b95e0713n@googlegroups.com>
 by: Bonita Montero - Wed, 9 Aug 2023 14:36 UTC

Am 09.08.2023 um 16:32 schrieb wij:
> On Wednesday, August 9, 2023 at 7:53:14 PM UTC+8, Bonita Montero wrote:
>> Am 09.08.2023 um 12:08 schrieb Öö Tiib:
>>> Great example, intersting how std::bitset<500000> and
>>> std::vector<bool>(500000) perform compared to that "my_set".
>> With this code bitset and vector<bool> have the same performance
>> under Windows (MSVC) and Linux (g++ / clang++).
>>
>> #include <iostream>
>> #include <bitset>
>> #include <vector>
>> #include <random>
>> #include <chrono>
>> #include <atomic>
>>
>> using namespace std;
>> using namespace chrono;
>>
>> atomic<size_t> aSum;
>>
>> int main()
>> {
>> constexpr size_t BITS = 0x10000;
>> bitset<BITS> bs;
>> vector<bool> vb( BITS );
>> mt19937_64 mt;
>> uniform_int_distribution<size_t> iBit( 0, BITS - 1 );
>> auto fill = []( auto &container )
>> {
>> bool bit = false;
>> for( size_t i = 0; i != BITS; ++i )
>> container[i] = bit,
>> bit = !bit;
>> };
>> fill( bs );
>> fill( vb );
>> constexpr size_t ROUNDS = 1'000;
>> auto linearBench = []( char const *what, auto const &container )
>> {
>> auto start = high_resolution_clock::now();
>> size_t sum = 0;
>> for( size_t r = ROUNDS; r--; )
>> for( size_t i = 0; i != BITS; ++i )
>> sum += container[i];
>> double ns = duration_cast<nanoseconds>( high_resolution_clock::now() -
>> start ).count() / ((double)BITS * ROUNDS);
>> ::aSum = sum;
>> cout << what << ns << endl;
>> };
>> linearBench( "linear bitset: ", bs );
>> linearBench( "linear vector: ", vb );
>> auto gappedBench = []( char const *what, auto const &container )
>> {
>> auto start = high_resolution_clock::now();
>> size_t sum = 0;
>> for( size_t r = ROUNDS; r--; )
>> for( size_t g = 0, i = 0; g != BITS; ++g, i += 7, i = i < BITS ? i : 0 )
>> sum += container[i];
>> double ns = duration_cast<nanoseconds>( high_resolution_clock::now() -
>> start ).count() / ((double)BITS * ROUNDS);
>> ::aSum = sum;
>> cout << what << ns << endl;
>> };
>> gappedBench( "gapped bitset: ", bs );
>> gappedBench( "gapped vector: ", vb );
>> }
>
> I can't read these new C++ syntax. In case of 'vector<bool>', I would use
> Wy::VLInt<unsigned int> (Very Large Integer), two access members bit(size_t)
> and set_bit(size_t,bool). As you can see, every thing is 'concrete' and
> direct. But such classes are not the purpose of libwy.

For me a vector<bool> or a bitset<N> is much more concrete.

Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen

<ub0idi$11pq$1@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=993&group=comp.lang.c%2B%2B#993

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!news.eternal-september.org!.POSTED.osa.pri.ee!not-for-mail
From: eesn...@osa.pri.ee (Paavo Helde)
Newsgroups: comp.lang.c++
Subject: Re: "Inside STL: The map, set, multimap, and multiset" by Raymond
Chen
Date: Wed, 9 Aug 2023 20:29:21 +0300
Organization: A noiseless patient Spider
Message-ID: <ub0idi$11pq$1@dont-email.me>
References: <uaubnm$3i781$1@dont-email.me>
<aaa09f64-8320-4b9f-bd86-91d800de81e1n@googlegroups.com>
<uavbi9$3q20f$1@dont-email.me>
<590410fa-ae5b-4d85-a56d-560f6549e3ccn@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Wed, 9 Aug 2023 17:29:22 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="osa.pri.ee:213.219.84.188";
logging-data="34618"; mail-complaints-to="abuse@eternal-september.org"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:102.0) Gecko/20100101
Thunderbird/102.14.0
Content-Language: en-US
In-Reply-To: <590410fa-ae5b-4d85-a56d-560f6549e3ccn@googlegroups.com>
 by: Paavo Helde - Wed, 9 Aug 2023 17:29 UTC

09.08.2023 17:20 wij kirjutas:

> Why you show the comparison of std::vector's random access and std::set's insert?

Because a linear array can be used as a set, if set elements are
reasonably small integers, with a potentially huge expense on memory.
And sometimes this approach is used in production, of course only if it
makes sense.

Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen

<74eda6cc-35a4-40e2-9a50-2f1e2aaf27afn@googlegroups.com>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=995&group=comp.lang.c%2B%2B#995

  copy link   Newsgroups: comp.lang.c++
X-Received: by 2002:a05:620a:8017:b0:76c:9791:167e with SMTP id ee23-20020a05620a801700b0076c9791167emr8858qkb.6.1691640559645;
Wed, 09 Aug 2023 21:09:19 -0700 (PDT)
X-Received: by 2002:a17:902:da8f:b0:1bb:b39d:8cb0 with SMTP id
j15-20020a170902da8f00b001bbb39d8cb0mr427271plx.1.1691640559416; Wed, 09 Aug
2023 21:09:19 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!diablo1.usenet.blueworldhosting.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.c++
Date: Wed, 9 Aug 2023 21:09:18 -0700 (PDT)
In-Reply-To: <ub0idi$11pq$1@dont-email.me>
Injection-Info: google-groups.googlegroups.com; posting-host=145.14.19.203; posting-account=pysjKgkAAACLegAdYDFznkqjgx_7vlUK
NNTP-Posting-Host: 145.14.19.203
References: <uaubnm$3i781$1@dont-email.me> <aaa09f64-8320-4b9f-bd86-91d800de81e1n@googlegroups.com>
<uavbi9$3q20f$1@dont-email.me> <590410fa-ae5b-4d85-a56d-560f6549e3ccn@googlegroups.com>
<ub0idi$11pq$1@dont-email.me>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <74eda6cc-35a4-40e2-9a50-2f1e2aaf27afn@googlegroups.com>
Subject: Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen
From: oot...@hot.ee (Öö Tiib)
Injection-Date: Thu, 10 Aug 2023 04:09:19 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 2046
 by: Öö Tiib - Thu, 10 Aug 2023 04:09 UTC

On Wednesday, 9 August 2023 at 20:29:39 UTC+3, Paavo Helde wrote:
> 09.08.2023 17:20 wij kirjutas:
>
> > Why you show the comparison of std::vector's random access and std::set's insert?
> Because a linear array can be used as a set, if set elements are
> reasonably small integers, with a potentially huge expense on memory.
> And sometimes this approach is used in production, of course only if it
> makes sense.

Such vector is typically used in counting sort algorithm. Sorting
million (N) items of half million (K) possible states with counting
sort O(N+K) time complexity is about 13 times better than with
O(N*log N) sort. But of course misuse of std::set for such sorting
adds another order of magnitude to loss in performance.

Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen

<86o7j871uz.fsf@linuxsc.com>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=1017&group=comp.lang.c%2B%2B#1017

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: tr.17...@z991.linuxsc.com (Tim Rentsch)
Newsgroups: comp.lang.c++
Subject: Re: "Inside STL: The map, set, multimap, and multiset" by Raymond Chen
Date: Tue, 15 Aug 2023 08:37:56 -0700
Organization: A noiseless patient Spider
Lines: 16
Message-ID: <86o7j871uz.fsf@linuxsc.com>
References: <uaubnm$3i781$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: dont-email.me; posting-host="4aa43ab23f99b81d777a1b3458fe2d41";
logging-data="3037868"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+u++EaTK2XUeB8V1tW4yX/I9/gLbJdSmc="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:EGePxlzMRCYDKIzBm94TiDf5ZNQ=
sha1:1qN2v19g6iZMcTGiBBmGEMQteH8=
 by: Tim Rentsch - Tue, 15 Aug 2023 15:37 UTC

Lynn McGuire <lynnmcguire5@gmail.com> writes:

> "Inside STL: The map, set, multimap, and multiset" by Raymond Chen
> https://devblogs.microsoft.com/oldnewthing/20230807-00/
>
> "The complexity requirements of the C+ standard library map, set,
> multimap, and multiset basically narrow the possible implementation
> options to AVL trees and red-black trees."

I find this claim hard to believe. There are other kinds of
balanced trees that offer the same kinds of performance
guarantees that AVL and red-black trees do. Is there some sort
of unexpected requirement in the C++ standard that would rule out
other balanced tree data structures? I confess I have not tried
to read the C++ standard looking for such a requirement, but I'm
willing to take a look if someone provides a specific reference.


devel / comp.lang.c++ / "Inside STL: The map, set, multimap, and multiset" by Raymond Chen

1
server_pubkey.txt

rocksolid light 0.9.81
clearnet tor