www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Find in assoc array then iterate

reply Kevin Bailey <keraba yahoo.com> writes:
I'm trying to do this equivalent C++:

     unordered_map<string, int> map;

     for (auto i = map.find(something); i != map.end(); ++i)
         ...do something with i...

in D, but obviously with an associative array. It seems that it's 
quite
easy to iterate through the whole "map", but not start from the 
middle.
Am I missing something obvious (or not so obvious) ?
Oct 21 2022
next sibling parent Sergey <kornburn yandex.ru> writes:
On Friday, 21 October 2022 at 22:03:53 UTC, Kevin Bailey wrote:

 I'm trying to do this equivalent C++:

     unordered_map<string, int> map;

     for (auto i = map.find(something); i != map.end(); ++i)
         ...do something with i...

 in D, but obviously with an associative array. It seems that 
 it's quite
 easy to iterate through the whole "map", but not start from the 
 middle.
 Am I missing something obvious (or not so obvious) ?


How should that work, if map is unordered?

In D:
Implementation Defined: The built-in associative arrays do not 
preserve the order of the keys inserted into the array. In 
particular, in a foreach loop the order in which the elements are 
iterated is typically unspecified.
https://dlang.org/spec/hash-map.html
Oct 21 2022
prev sibling next sibling parent JG <someone simewhere.com> writes:
On Friday, 21 October 2022 at 22:03:53 UTC, Kevin Bailey wrote:

 I'm trying to do this equivalent C++:

     unordered_map<string, int> map;

     for (auto i = map.find(something); i != map.end(); ++i)
         ...do something with i...

 in D, but obviously with an associative array. It seems that 
 it's quite
 easy to iterate through the whole "map", but not start from the 
 middle.
 Am I missing something obvious (or not so obvious) ?


You can build a map using a red black tree.
Then you should be able to do what you want.

https://dlang.org/phobos/std_container_rbtree.html
Oct 21 2022
prev sibling next sibling parent =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 10/21/22 15:03, Kevin Bailey wrote:

 I'm trying to do this equivalent C++:
 
      unordered_map<string, int> map;
 
      for (auto i = map.find(something); i != map.end(); ++i)
          ...do something with i...
 
 in D, but obviously with an associative array. It seems that it's quite
 easy to iterate through the whole "map", but not start from the middle.
 Am I missing something obvious (or not so obvious) ?
 


Something like the following perhaps, which sorts the keys:

import std; // Sorry :(

void main() {
     auto m = iota(20).map!(i => tuple(i, format!"value_%s"(i))).assocArray;

     foreach (key; m.keys.sort.find(13)) {
         writeln(m[key]);
     }
}

Ali
Oct 21 2022
prev sibling next sibling parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 10/21/22 6:03 PM, Kevin Bailey wrote:

 I'm trying to do this equivalent C++:
 
      unordered_map<string, int> map;
 
      for (auto i = map.find(something); i != map.end(); ++i)
          ...do something with i...
 
 in D, but obviously with an associative array. It seems that it's quite
 easy to iterate through the whole "map", but not start from the middle.
 Am I missing something obvious (or not so obvious) ?
 


What you are missing is that it's something that provides almost no value.

A question to answer is *why* you want to iterate an "unordered" map 
from the middle?

-Steve
Oct 21 2022
parent reply Kevin Bailey <keraba yahoo.com> writes:
Hi Sergey,

While the unordered map doesn't guarantee an ordering (since its 
contents are
hashed), the order should remain static if you don't insert or 
delete.

Hi JG,

Thanks for the red-black tree reference. I'll read up on it in 
case I need it
but I'd prefer to use the built-in O(1) hash map.

Hi again Ali!,

I did consider a sort, but it has a number of downsides:
- it's O(n ln(n))
- if I'm understanding correctly, it would require additional 
memory
- Not relevant to my problem but, if you had duplicates, it 
wouldn't handle
stopping in the middle of some duplicates and re-starting; only 
iterators
support this.

One could more easily copy the keys into an array, and iterate on 
them.

Thus, I was hoping to find a member function that would support 
this.

Steven,

Just because you don't see the value doesn't mean I don't. You 
should try to
be more helpful, or don't bother.
Oct 21 2022
next sibling parent reply bachmeier <no spam.net> writes:
On Saturday, 22 October 2022 at 04:53:09 UTC, Kevin Bailey wrote:


 Steven,

 Just because you don't see the value doesn't mean I don't. You 
 should try to
 be more helpful, or don't bother.


Programs are written to do things that have value. Programming 
languages are designed to support that goal. It's perfectly 
reasonable to ask what you are trying to accomplish if you want 
to know how best to do it in a particular language.
Oct 22 2022
parent reply Kevin Bailey <keraba yahoo.com> writes:
Siarhei,

Thanks for this possibility. I didn't know D had "pointers" like 
this.
Unfortunately, it appears that you can't pick up where you left 
off with
that pointer? You have to re-scan forward?

bachmeier,

I didn't reply to Steven's question; I replied to his claim that 
there
was no value. I found his response insulting and patronizing, and 
has
no place on a public forum helping evangelize D. See Siarhei's 
response
for a better way.

Siarhei,

I'm attempting to do something like a DFS down a fixed list of 
strings.
It's doing something like generating permutations of the strings, 
however
the conditions for the search are fairly complicated, and of 
course I'm
trying to do as much "early exit" as possible. That is, I can 
prune
branches just seeing the first or second word.

IOW, if D could, for example, "iterate through all 3 word 
combinations
in this list", it would be useless to this problem (or at least 
*very*
expensive.) OTOH, a forward iterator (i.e. copyable but does not 
need to
go backwards) solves the problem elegantly and efficiently.

Go-lang supports it too:

     package main

     import "fmt"
     import "reflect"

     func main() {
         m := make(map[string]int)
         m["key1"] = 7
         m["key2"] = 8
         iter := reflect.ValueOf(m).MapRange()
         // Advance iterator
         iter.Next()
         // Preserve position
         iter2 := *iter
         // Exhaust first iterator
         for iter.Next() {
             fmt.Println("iter: ", iter.Key())
         }
         // What does second iterator see?
         for iter2.Next() {
             fmt.Println("iter2: ", iter2.Key())
         }
     }

will correctly print:

     iter: key2
     iter2: key2
Oct 22 2022
next sibling parent Paul Backus <snarwin gmail.com> writes:
On Saturday, 22 October 2022 at 15:21:07 UTC, Kevin Bailey wrote:

 OTOH, a forward iterator (i.e. copyable but does not need to
 go backwards) solves the problem elegantly and efficiently.


The builtin function [`byKeyValue`][1] returns a forward range 
(D's version of a forward iterator) over the contents of an 
associative array. To save the current iteration state, use the 
`.save` method.

Here's a simple example:

```d
import std.algorithm, std.range, std.stdio;

void main()
{
     auto aa = ["x": 123, "y": 456, "z": 789, "w": 10];

     // name of range type is private, so use auto + typeof
     auto it = aa.byKeyValue;
     typeof(it) saved;

     // iterate once and save our position partway through
     for (; !it.empty; it.popFront)
     {
         auto e = it.front;
         if (e.key == "y")
             saved = it.save;
         writefln("%s: %s", e.key, e.value);
     }

     writeln("--------");

     // iterate again from saved position
     foreach (e; saved)
         writefln("%s: %s", e.key, e.value);
}
```

[1]: https://druntime.dpldocs.info/object.byKeyValue.1.html
Oct 22 2022
prev sibling parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 10/22/22 08:21, Kevin Bailey wrote:


 his claim that there was no value.


I think he was questioning the need for iterating from a point forward 
inside an unordered container. When the container is unordered, the 
elements that are accessed after a found element could be anything. I 
think that's the puzzling part in your question.


      package main


Here is my interpretation of Paul Backus's solution:

module main;

import std.stdio;

void main() {
     int[string] m;
     m["key1"] = 7;
     m["key2"] = 8;

     auto iter = m.byKeyValue();
     // Advance iterator
     iter.popFront();
     // Preserve position
     auto iter2 = iter.save();
     // Exhaust first iterator
     foreach (kv; iter) {
         writeln("iter: ", kv.key, " = ", kv.value);
     }
     // What does second iterator see?
     foreach (kv; iter2) {
         writeln("iter2: ", kv.key, " = ", kv.value);
     }
}

May print (because its unordered):

iter: key2 = 8
iter2: key2 = 8

Ali
Oct 22 2022
parent Kevin Bailey <keraba yahoo.com> writes:
ah, I knew that I could iterate over byKey, but I didn't know 
that it was a
tangible thing, that you could hold in your hand. This should be 
fine, and
I'll use your template trick for passing it to a function.

Thanks Paul and Ali!
Oct 22 2022
prev sibling parent Steven Schveighoffer <schveiguy gmail.com> writes:
On 10/22/22 12:53 AM, Kevin Bailey wrote:

 Steven,
 
 Just because you don't see the value doesn't mean I don't. You should 
 try to
 be more helpful, or don't bother.


I just mean that I don't understand what iterating from a random 
position in the AA is. Why not iterate from the beginning? It isn't any 
different.

-Steve
Oct 22 2022
prev sibling next sibling parent Siarhei Siamashka <siarhei.siamashka gmail.com> writes:
On Friday, 21 October 2022 at 22:03:53 UTC, Kevin Bailey wrote:

 I'm trying to do this equivalent C++:

     unordered_map<string, int> map;

     for (auto i = map.find(something); i != map.end(); ++i)
         ...do something with i...

 in D, but obviously with an associative array. It seems that 
 it's quite
 easy to iterate through the whole "map", but not start from the 
 middle.
 Am I missing something obvious (or not so obvious) ?


Are you looking for something like this?

```D
import std;

void main() {
   int[string] map;
   foreach (v ; 1 .. 9)
     map[v.to!string] = v;
   writeln(map); // prints ["8":8, "4":4, "7":7, "6":6, "1":1, 
"5":5, "2":2, "3":3]

   auto something = "6";

   auto pointer_to_something = (something in map);
   if (pointer_to_something) {
     writeln(*pointer_to_something); // prints 6
     foreach (k, ref v ; map) {
       if (&v == pointer_to_something)
         break;
       writeln(v); // prints 8 4 7
     }
   }
}
```

This code finds something and then iterates elements between the 
"middle" and "begin". You asked for iterating between the 
"middle" and "end", but I don't see a big difference because the 
elements order is not guaranteed anyway. And just like Steven, 
I'm curious about what kind of practical utility is this supposed 
to have?
Oct 21 2022
prev sibling parent Tejas <notrealemail gmail.com> writes:
On Friday, 21 October 2022 at 22:03:53 UTC, Kevin Bailey wrote:

 I'm trying to do this equivalent C++:

     unordered_map<string, int> map;

     for (auto i = map.find(something); i != map.end(); ++i)
         ...do something with i...

 in D, but obviously with an associative array. It seems that 
 it's quite
 easy to iterate through the whole "map", but not start from the 
 middle.
 Am I missing something obvious (or not so obvious) ?


Maybe the following can help?

```d
import std;

void main(){
     int[int] a = [2 : 4,
                   5 : 6,
                   6 : 7,
                   10 : 12,
                   11 : 23
                   ];
     bool cont = true;
     foreach(k, v; a){ // use ref v instead of v if you wanna 
modify the values, like siarhei did in his post
         if (v != 7 && cont){
             continue;
         }
         else{
             cont = false;
         	writeln(k, ":", v);
         }
     }
     /+
     foreach(k, v; a.skipOver!((a, b) => a != b)(6)){ // this code 
could've worked if you had an inputRange, I think
         writeln(k, ":", v);
     }
     +/
}

```
Oct 22 2022