C++链接列表遗留代码到STL - 动态分配链表大小

Question

我正在研究一些定义链表的遗留代码(不使用STL容器)

我想转换此代码以便使用STL列表.正如您在以下示例中所看到的,为链接列表分配了所有N的初始值.然后列表中的某些元素被赋予一些值.然后列表中的"空元素"被"清理".

我正在寻找一种更好的方法来使用STL.特别是,这可以避免删除空元素代码吗？我检查了STL文档..它定义了一个remove方法,但这不完全是我在这里需要的.有没有办法动态分配链表大小？我很感激你的建议!

更新 我修改了代码.这类似于我的主要代码.但为了避免任何混淆,我在下面编写一个伪代码来解释它是如何工作的.

脚步

1. elementIds为链表分配大小(struct my_list)
2. 还有另一个链表meshElem,我对meshElem->elemstruct的一些值感兴趣.
   • 例如:我需要elemId = meshElem->elem->id; 这elemId是在范围内0 to elementIds.
   • 的elemId将被用作索引来寻找一个特定的元素struct my_list lst 例如lst[elemId]
3. 在doSomething ()函数中,循环遍历0 to elementIds.在此循环中,如果满足某些条件,lst->number则为其分配一个整数值= someArray[i]其中i在范围内0 to N(完成appendElement)
4. 没有next进入的元素struct my_list lst被清理(问题:这可以避免吗？)
5. lst->数值在代码中进一步用于其他一些处理.

现在修改后的代码:

struct my_list
 {
  int  number;
  struct my_list *prev;
  struct my_list *next;
 }

void doSomething(void){
     const int N = 50000;
     const int elementIds = 10000;
     int i, elemId, node_i;     
     struct my_list *lst;     
     lst = new struct my_list[elementIds];
     int someArray[12];

     meshElem = mesh->next;     

     for(i=0; i<=elementIds; i++) {
        lst[i].num = 0;
        lst[i].next   = NIL;
        lst[i].prev  = NIL;
      }      

    while(meshElem != NIL){
        // Element id (int) 
        // Note that any elemId will be in range [0 - elemId ]
        elemId = meshElem->elem->id;

        // Do some operations to populate "lst"    
        // Note that 'lst' gets values ONLY for certain 
        // values of i
        for (i = 0; i<=N; i++){        
            // if certain conditions are satisfied, 
            // it updates the  linked list element 
            // lst[meshIdx]. foo1(), foo2() are just some conditions...

            if (foo1()){
               appendElement(someArray[i], &lst[meshIdx])
               }
            else if (foo2()){
               appendElement(someArray[i], &lst[meshIdx])           
            }
        }          

      meshElem = meshelem->next;

  } // End of while(meshElem != NIL)

  // Clean up the linked list lst 
  // by removing unassigned items. 

   struct my_list *lst_2

   for(i=1; i<=N; i++) {
     lst_2 = &lst[i];
     while( lst != NIL ) {      
      if( lst->next != NIL && lst->next->number == 0 ) {
        delete lst_2->next;
        lst_2->next = NIL;
      } // end of if loop
      lst = lst_2->next;

    } // end of while while( lst != NIL )

  } // End of for(i=1; i<=N; i++)


  //  Do some more stuff that uses struct my_list lst
  for(i=1;i<=elementIds;i++) {

      while( lst[i] != NIL && (node_i = lst[i]->number) ) {
            if( node_i == 0) {
              lst[i] = lst[i]->next; 
              continue;
            }
            // Use this "node_i" index in some other arrays to
            // do more stuff. 
            //..
            //..
            //..
            lst[i] = lst[i]->next;    
      }

}


void appendElement(int n, struct my_list *lst) {
  int exists = 0;
  while( lst->next != NIL ) {
    if( lst->number == n ) {
    exists = 1;
    lst=lst->next;
  }
  if( exists < 1 ) {
    lst->number = n2;
    insertElemAfter(lst, 0);
  }
}

Answer 1

您的旧链表实际上是一个线程稀疏向量.具有NULL的数组是稀疏向量,链接列表提供线程.这两者结合起来,可以持续访问各个节点(随机访问数组),并通过"有效"节点进行有效遍历(避免使用NULL).

假设这两个方面都很重要,并且假设Data可能比您显示的简单int更复杂,那么您可以创建一个数据结构,例如:

class ThreadedSparseVector {
private:
    std::vector<Data*> m_thread;
    std::vector<int> m_sparse_vector;
};

在初始化期间,您可以预先调整m_sparse_vector的大小并将值初始化为-1.在追加元素(或访问它们)时,首先检查它是否已经"有效",如果不是,则将其添加到线程中:

void ThreadedSparseVector::appendElement(int i) {
    if (-1 == m_sparse_vector[i]) {
        // Add new data
        m_sparse_vector[i] = m_thread.size()
        m_thread.push_back(new Data(i));
    }

    Data* data = m_thread[m_sparse_vector[i]];
    // Initialize/update data as necessary
}

如果线程比随机访问更重要,另一种选择是简单地使用STL映射.如果随机访问比线程更重要,那么您可以简单地使用STL向量并在迭代期间容忍NULL(或创建自动跳过NULL的自定义迭代器).

另一种选择,这取决于你的动机转换为STL,是创建一个围绕实现一个STL兼容的接口,而不是转换数据结构本身使用STL的遗留代码的包装.