Thread: Connection between 2D array and list vector?

  1. #1
    Registered User
    Join Date
    May 2006
    Posts
    169

    Connection between 2D array and list vector?

    Hi there,

    For a maze generator I coded, I used a 2d array of struct Cell.
    One of the generation algorithms required to create a list, that would eventually hold pointers to those Cells.
    Then it was needed to choose one of the Cell pointers within the list, and work upon it. This one is easy, since I just need to reference to the pointer's location.
    Thing is when I needed to do it vice versa - finding a list element based on the array index, (such as finding the list element that points to array[4][7] in the list, and removing it from the list), is where it gets nasty.
    I solved it by iterating from list.begin() to list.end(), and comparing x and y values I added to Cell, but I'm not sure it's as fast a solution as can be.
    Can I both-way link a list and an array?

    Thanks!

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Sure, just make an array [MAXY][MAXX], and then generate the linked list from those elements rather than from allocations.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    May 2006
    Posts
    169
    Thanks for the quick reply Mats

    It's what I do really, the list is actually a vector <struct Cell*>
    The link works one-way, so I can know where the sixth element points to with *(list[5])
    My problem starts when I want it the opposite way, finding which element of the list points to the array index at [4][6] etc.

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Searching through a linked list by definition involves starting at the front and going element by element through the list until you find what you're looking for. If you want something faster, then you want something other than a list. (Edit: And then of course, you may not be able to insert as fast, etc.)
    Last edited by tabstop; 08-31-2008 at 12:58 PM.

  5. #5
    Registered User
    Join Date
    May 2006
    Posts
    169
    Thank you,
    This pretty much answers my question, will look into alternatives and see if anything is more appropriate to my particular case

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    You could of course store the "points to this" as you build your 2D array, so when you produce the maze, you put links to all other cells that refer to [4][6] in the cell [4][6] itself.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting linked list please help with CODE
    By scarlet00014 in forum C Programming
    Replies: 3
    Last Post: 09-27-2008, 11:24 PM
  2. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  3. linked list inside array of structs- Syntax question
    By rasmith1955 in forum C Programming
    Replies: 14
    Last Post: 02-28-2005, 05:16 PM
  4. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 05:46 PM