0

So, I'm trying to implement a Trie tree for sorting lexicographically my code. But because it's for a competition, I'm trying to cut down on time. Because of that, instead of a std::vector, I decided to use std::list, so I don't have to deal with all the reallocation. But I ran into a problem, namely using pointers for storing where my element is (because I don't want to have linear time instead of constant time when restoring my elements).

My idea is to make a list of lists, where each sub-list contains pairs of int's and "pointers". So:

list<list<pair<int, list<void>::iterator>> trie;

As you can see, I tried to use iterators as "pointers", but then I run into a recursive type. I've replaced it with void as a placeholder, but normally it would look like this:

list<list<pair<int, list<list<list<pair<int, list<(......)>::iterator>>>::iterator>>

Doesn't sound too good. As my "pointer" I also tried an actual pointer, but from what I saw, making an iterator from a pointer is as good as searching the list for an element with that pointer, which brings me back to my problem. Is there a way to get rid of the recursive type? Or, even better, is there some better "pointer" which would work for me?

huB1erTi2
  • 23
  • 5
  • *Because of that, instead of a std::vector, I decided to use std::list, so I don't have to deal with all the reallocation.* -- A vector stores its data in contiguous memory, thus is cache-friendly. A `std::list` doesn't do this. Thus your claim that `vector` is slower needs to be backed up by solid proof. – PaulMcKenzie Jan 06 '19 at 20:37
  • @PaulMcKenzie, what I mean is reallocation takes a lot of time in my case, especially that I would have nested `vector`s. At least, that's how I understand it. If you think it's not worth it, I'd probably go back to the `vector`, but I thought I could be sneaky with the `list`. – huB1erTi2 Jan 06 '19 at 20:39
  • You also are claiming "all of thise reallocations". A `std::vector` allocates only when the number of elements reaches capacity (and on instantiation), and capacity can be much more than the reported `size()`. Also, a 1-d vector emulating a two dimensional vector is faster. – PaulMcKenzie Jan 06 '19 at 20:40
  • Also, [this answer](https://stackoverflow.com/questions/21943621/how-to-create-a-contiguous-2d-array-in-c/21944048#21944048), even though it uses `**`, can be used to create the contiguous space *and* still be able to use `[ ][ ]` syntax. – PaulMcKenzie Jan 06 '19 at 20:42
  • @PaulMcKenzie How do I make a 1-d vector emulating a two dimensional vector in my case? – huB1erTi2 Jan 06 '19 at 20:42
  • Row x, column y would have the the formula `[x * number_of_columns + y]`. – PaulMcKenzie Jan 06 '19 at 20:44
  • Yeah, but I don't know the number of columns at any time, and neither do I know the number of rows. It's a Trie tree, so it's quite irregular. – huB1erTi2 Jan 06 '19 at 20:47
  • *But because it's for a competition* -- You really should make the code work first. You may wind up not completing the code, all in the name of (premature) optimization. Once the code is working, maybe you don't need to change anything -- assuming that using pointers is "faster", and thus try to code up something that is hard-to-understand with the results (in many cases) run the same relative speed, and in the worse-case, slower, becomes a waste of time. – PaulMcKenzie Jan 06 '19 at 20:55
  • 1
    Why such a complicated structure for a trie ? I typically implement a `Trie` with only two data members - a `bool` to mark words and an `std::map`. (or `std::unordered_map`) to keep track of children. – Sid S Jan 06 '19 at 21:13
  • @SidS I also need my Trie sorted and with `std::list` I can insert in the middle while reading the I/O. – huB1erTi2 Jan 07 '19 at 08:06
  • @huB1erTi2, `std::map` is sorted. Insertion complexity is logarithmic, as opposed to the linear complexity of finding out where to insert in a `list`.. – Sid S Jan 07 '19 at 08:30
  • @SidS How scared should I be of elements colliding if I have up to 100000 of nodes? – huB1erTi2 Jan 07 '19 at 09:13
  • @SIdS I just realized that std::map is a red-black tree and not a hash map. I'll try using it and thanks! – huB1erTi2 Jan 07 '19 at 09:44
  • How can you have a collision in a trie ? – Sid S Jan 08 '19 at 02:30

0 Answers0