# Del\_dict/4 behaviour and dict iteration

**URL:** <https://swi-prolog.discourse.group/t/del-dict-4-behaviour-and-dict-iteration/4135>\
**Category:** Predicate\
**Created:** [July 3, 2021, 11:23am UTC](https://swi-prolog.discourse.group/t/del-dict-4-behaviour-and-dict-iteration/4135 "2021-07-03T11:23:11Z")\
**Posts on this page:** 1\
**Showing post:** 7

<div class="post-metadata">

**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\
**Post date:** [July 3, 2021, 4:30pm UTC](https://swi-prolog.discourse.group/t/del-dict-4-behaviour-and-dict-iteration/4135/7 "2021-07-03T16:30:10Z")

</div>

> [@anon95304481](#):
>
> Insert is still O(n), because you need to create/copy a new dict?

The search for the insert location is O(log(N)). Next you have to make a new dict and copy the data. Copying the data are two simple memcpy() calls (the part before the new key and the part that follow it). So, yes, insert in O(n), but the constant factor is pretty low.

Long time I did a comparison with rbtrees and If I recall correctly rbtrees started to win around 1,000 k-v pairs. May have changed a bit. In other words, used for representing compound data structures they are typically fine. They are not suitable to implement (for example) word-counting a document using _for each word, update the count in the dict by one_. The way to implement that is to make a flat list of words, use sort/4 (or msort/2) to sort while keeping duplicates and walk over the list to establish the counts. Next you can do dict\_pairs/3 to create a dict for subsequent lookup if an on-stack data structure is desirable.

---

_[View the full topic](https://swi-prolog.discourse.group/t/del-dict-4-behaviour-and-dict-iteration/4135)._