@Thiago Macieira
"The standard *can't* require them to implement using a
hashing table."
Of course not, but the standard could require to meet a certain time
complexity.

On Thu, Jul 9, 2020 at 10:21 PM Thiago Macieira via Std-Discussion <
std-discussion_at_[hidden]> wrote:

> On Thursday, 9 July 2020 01:37:37 PDT Artur Czajkowski via Std-Discussion
> wrote:
> > Then you should correct Thiago Maciera, he is the one that adamantly and
> >
> > arrogantly states that:
> > > " The standard doesn't
> > > care if the algorithms rerquired to implement it are quadratic or
> cubic or
> > > exponential. " [Misspelling original]
>
> Accepting the correction. I meant the compiler algorithms, not the
> standard
> library algorithms, but wasn't clear enough when writing it.
>
> This applies to the linker too. In an application I've had to maintain,
> the
> link time grew to 18 hours because the linker uses an (apparently)
> quadratic
> algorithm to search for symbols ("for each symbol processed, search symbol
> in
> the symbol table" sounds O(n²)). This sounds like it could be trivially
> fixed
> to use a sorted table, reducing the link time to O(n log n), or even a
> hashing
> table that could get us close to O(n). But my point is that there's no
> constraint in the algorithm that the developers of the linker choose to
> use to
> write their tool. The standard *can't* require them to implement using a
> hashing table.
>
> PS: the misspelling is a result of my laptop keyboard having some keys
> sticky,
> so they sometimes repeat-fire.
>
> --
> Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
> Software Architect - Intel System Software Products
>
>
>
> --
> Std-Discussion mailing list
> Std-Discussion_at_[hidden]
> https://lists.isocpp.org/mailman/listinfo.cgi/std-discussion
>

-- 
Best regards
*Artur Czajkowski*
https://marketplace.visualstudio.com/items?itemName=GitAtomic.GitAtomic