关于list容器的remove()

SybaseLU

main()
{

        char* as = "aaaaaa";
        char* bs = "bbbbbb";
        char* cs  = "aaaaaa";

        list<char*> S;
        list<char*>::iterator j;
        S.push_back(as);
        S.push_back(bs);
        S.push_back(cs);

        for(j=S.begin(); j != S.end(); ++j) cout << *j << " ";
        cout << endl;

        S.remove("aaaaaa");
        for(j=S.begin(); j != S.end(); ++j) cout << *j << " ";
        cout << endl;

   return 0;
}
看来sgi中版本的list的remove()是这样实现的
void list<T>::remove(const T& value)
{
    iterator first = begin();
    iterator last = end();
    while (first != last)
    {
                iterator next = ++first;
                if (*first == value) erase(first);
                first = next;
        }
}
我的问题是：push_back()推到container中的是字符串地址， 当删除container中的某个element时， 在remove中使用*first来判断是否等于value, *first返回的是iterator所指node的data, 此时的data是字符串地址，怎么和remove()中的实参使用等号进行比较呢？

[ 本帖最后由 SybaseLU 于 2007-8-13 10:24 编辑 ]

jigloo

用remove_if

逸远

从代码来看＝＝应该是重载了的，看＝＝的重载代码

SybaseLU

不应该是重载==，因为list的迭代器iterator的重载的*代码如下

1. return node->data;

复制代码

除非node.data是一个class,在这个class中重载了==【这样调用void operator==(value) { ... }】, 而现在我的element是char*字符串地址,返回的就是一个普通的字符串地址，如何重载==?

逸远

那就不知道了，期待高人回答~

jigloo

本来list通常放string的。
如果用char*,当然没法用remove

变通一下可以用remove_if

1. 
   
2. #include <iostream>
   
3. #include <fstream>
   
4. #include <list>
   
5. #include <iterator>
   
6. #include <functional>
   
7. #include <cstring>
   
8. 
   
9. using namespace std;
   
10. 
    
11. int main(void)
    
12. {
    
13.         char *ss[] = {"aaaa", "bbbb", "cccc"};
    
14.         list<char*> S(ss, ss+sizeof(ss)/sizeof(*ss));
    
15.         S.remove_if(bind2nd(not2(ptr_fun(strcmp)), "aaaa"));
    
16.         copy(S.begin(), S.end(), ostream_iterator<char*>(cout, "\n"));
    
17.         return 0;
    
18. }
    

复制代码

SybaseLU

目的并不是为了使用标准的STL库，而是在为了Linux/Embeded系统中动态的存放需要的各种类型数据，所以自己定制一个tiny STL list库，代码如下：

节点：

1. 
   
2. #include <stdlib.h>
   
3. #include <stdio.h>
   
4. 
   
5. /* list's node implementation */
   
6. template<class T>
   
7. struct _list_node {
   
8.         struct _list_node *prev;
   
9.         struct _list_node *next;
   
10.         T        data;
    
11. };
    

复制代码

迭代器：

1. 
   
2. /* iterator implementation */
   
3. template<class T>
   
4. struct        _list_iterator {
   
5.         typedef _list_node<T> NODE;
   
6.         typedef _list_iterator<T> self;
   
7.        
   
8.         /* the member node can be  used kept down the NODE's address */
   
9.         NODE *node;
   
10.        
    
11.         self& operator = (const self& x)
    
12.         {
    
13.                 if (node == x.node)
    
14.                         return *this;
    
15.                 node = x.node;
    
16.                 node->data = x.node->data;
    
17.                 node->next = x.node->next;
    
18. 
    
19.                 /* as for  iterator, it's address never be altered or midified */
    
20.                 return *this;
    
21.         }
    
22.         bool operator != (const self& x) const
    
23.         {
    
24.                 return node != x.node;       
    
25.         }
    
26.         bool operator == (const self& x) const
    
27.         {
    
28.                 return node == x.node;       
    
29.         }
    
30. 
    
31.         self& operator++()
    
32.         {
    
33.                 node = node->next;
    
34.                 return *this;
    
35.         }
    
36.        
    
37.         self operator++(int)
    
38.         {
    
39.                 self tmp = *this;
    
40.                 node = node.next;
    
41.                 return tmp;
    
42.         }
    
43.         T& operator*() const
    
44.         {
    
45.                 return node->data;
    
46.         }       
    
47. };
    

复制代码

链表：

1. 
   
2. template<class T>
   
3. class AList
   
4. {
   
5. public:
   
6.           AList();
   
7.           ~AList() {}
   
8.         typedef _list_node<T> NODE;
   
9.         typedef _list_iterator<T> iterator;
   
10.        
    
11.           void push_back(const T value);
    
12.         void pussh_front(const T value);
    
13.        /* Note that! pop_back not mean remove element, just pop element what I need*/
    
14.           const T  pop_back();       
    
15.         const T  pop_front();
    
16.         void remove(const T value);
    
17.         int  eof() const { return !m_index; }
    
18.         void erase(iterator position);
    
19.         int  size() {return m_size; }
    
20.         void destroy();
    
21.         iterator begin() const { return start; }
    
22.         iterator end() const { return finish; }
    
23. 
    
24. private:
    
25.           iterator start;
    
26.           iterator finish;
    
27.         iterator m_prev;
    
28.         iterator m_now;
    
29. 
    
30.         NODE        *m_headnode;
    
31.         NODE         *m_tailnode;
    
32.         int                m_index;
    
33.         int         m_size;
    
34. };
    
35. 
    
36. 
    
37. 
    
38. template<class T>
    
39. AList<T>::AList()
    
40. {
    
41.         m_headnode = new NODE();  
    
42.         if (m_headnode == NULL)
    
43.         {
    
44.                     return;
    
45.         }
    
46.         m_headnode->next = NULL;  
    
47.         m_tailnode = m_headnode;
    
48. 
    
49.         start.node = m_headnode;
    
50.         finish.node = m_tailnode;
    
51.         m_index = 0;
    
52.         m_size = 0;
    
53. }
    
54. 
    
55. template<class T>
    
56. void AList<T>::push_back(const T value)
    
57. {
    
58.             NODE *element =  new NODE();
    
59.             if (element == NULL)
    
60.             {
    
61.                 return;
    
62.             }
    
63.             element->data = value;
    
64.         element->next = m_headnode;
    
65.         m_headnode = element;
    
66.         start.node = m_headnode;
    
67.         m_index++;
    
68.         m_size++;
    
69. }
    
70. 
    
71. template<class T>
    
72. const T AList<T>::pop_back()
    
73. {
    
74.         if (m_index == size())
    
75.         {
    
76.                 m_now = begin();
    
77.                 m_index--;
    
78.                 return m_now.node->data;
    
79.         }
    
80.         else
    
81.         {
    
82.                 if (!eof())
    
83.                 {
    
84.                         ++m_now;
    
85.                         m_index--;
    
86.                         return m_now.node->data;
    
87.                 }
    
88.         }
    
89. 
    
90. }
    
91. 
    
92. template<class T>
    
93. void AList<T>::remove(const T value)
    
94. {
    
95.         iterator first = begin();
    
96.         iterator last = end();
    
97.         m_prev = first;
    
98.         while (first != last)
    
99.         {
    
100.                 iterator next = first;
     
101.                 ++next;
     
102.                 if (*first == value)
     
103.                         erase(first);
     
104.                 else
     
105.                         m_prev = first;
     
106.                 first = next;
     
107.         }
     
108. }
     
109. 
     
110. template<class T>
     
111. void AList<T>::erase(iterator position)
     
112. {
     
113.         if (position == start)
     
114.         {
     
115.                 start = position;
     
116.                 ++start;
     
117.                 delete position.node;
     
118.         } else
     
119.         {
     
120.                 m_prev.node->next = position.node->next;
     
121.                 delete position.node;
     
122.         }
     
123.         m_size--;
     
124.         m_index = m_size;                       
     
125. }       
     
126. 
     
127. template<class T>
     
128. void AList<T>::destroy()
     
129. {
     
130.           NODE *p = NULL;
     
131.           while (m_headnode->next != NULL )
     
132.           {
     
133.                 p = m_headnode->next;
     
134.                 m_headnode = m_headnode->next;       
     
135.                 delete (p);
     
136.           }
     
137.         delete m_headnode;
     
138. }
     
139. 
     

复制代码

测试：

1. 
   
2. 
   
3. typedef AList<char*>         strLoader;
   
4. typedef AList<char*>::iterator strIte;
   
5. strLoader x;
   
6. strIte          xi;
   
7. 
   
8. typedef AList<int>        intLoader;
   
9. typedef AList<int>::iterator intIte;
   
10. intLoader y;
    
11. intIte          yi;
    
12. 
    
13. typedef AList<AString>        asLoader;
    
14. typedef AList<AString>::iterator asIte;
    
15. asLoader z;
    
16. asIte          zi;
    
17. 
    
18. 
    
19. typedef AList<DataDirectHeadend> lHeadend;
    
20. typedef AList<DataDirectHeadend>::iterator iteHeadend;
    
21. lHeadend HeadendLoader;
    
22. iteHeadend ite;
    
23. 
    
24. int
    
25. main(int argc, char** argv)
    
26. {
    
27.             DataDirectHeadend headend;
    
28.             sprintf(headend.zipcode, "%s", "510010");
    
29.             sprintf(headend.headendname, "%s", "GZTV");
    
30.             headend.channels  = 64;
    
31. 
    
32.         for (int j=0; j<5; j++)
    
33.         {
    
34.                     headend.headendid = j;
    
35.                 HeadendLoader.push_back(headend);
    
36.         }
    
37.         for (ite = HeadendLoader.begin(); ite != HeadendLoader.end(); ++ite)
    
38.         {
    
39.                 printf("zipcode:%s,headendid:%d,headendname:%s,channels:%d\n",\
    
40.                                         (*ite.node).data.zipcode, \
    
41.                                         (*ite.node).data.headendid, \
    
42.                                         (*ite.node).data.headendname, \
    
43.                                         (*ite.node).data.channels);
    
44.         }
    
45. 
    
46.         printf("===========headend==============\n");
    
47.         char context[][10] = {
    
48.                 "aaaaaa",
    
49.                 "bbbbbb",
    
50.                 "aaaaaa",
    
51.                 "cccccc",
    
52.                 "dddddd"
    
53.         };
    
54. 
    
55.         for (int i=0; i<5; i++)
    
56.         {
    
57.                 x.push_back(context[i]);
    
58.         }
    
59. 
    
60.         for (xi = x.begin(); xi != x.end(); ++xi)
    
61.         {
    
62.                 printf("strIte:%s\n", (*xi.node).data);
    
63.         }
    
64.         x.remove("dddddd");
    
65.         while (1)
    
66.         {
    
67.                 if (!x.eof())
    
68.                         printf("pop:%s\n", x.pop_back());
    
69.                 else {
    
70.                         printf("Is empty\n");
    
71.                         break;
    
72.                 }
    
73.         }       
    
74. 
    
75.         printf("==========char*==============\n");
    
76.         for (int k=0; k<3; k++)
    
77.                 y.push_back(k);
    
78. 
    
79.         for (yi = y.begin(); yi != y.end(); ++yi)
    
80.                 printf("intIte:%d\n", (*yi.node).data);
    
81. 
    
82.         y.remove(1);
    
83.         while (1)
    
84.         {       
    
85.                 if (!y.eof())
    
86.                         printf("pop:%d\n", y.pop_back());
    
87.                 else {
    
88.                         printf("Is empty\n");
    
89.                         break;
    
90.                 }
    
91.         }
    
92. 
    
93.         printf("==========int=============\n");
    
94.         char context2[10];
    
95.         for (int m=0; m<5; m++)
    
96.         {
    
97.                 sprintf(context2, "%d.mp3", m);
    
98.                 AString as(context2);
    
99.                 z.push_back(as);
    
100.         }
     
101. 
     
102.         for (zi = z.begin(); zi != z.end(); ++zi)
     
103.                 printf("asIte:%s\n", (*zi.node).data.c_str());
     
104. 
     
105.         #if 0
     
106.         while (1)
     
107.         {       
     
108.                 if (!z.eof())
     
109.                         printf("pop:%s\n", (z.pop_back()).c_str());
     
110.                 else {
     
111.                         printf("Is empty\n");
     
112.                         break;
     
113.                 }
     
114.         }
     
115.         #endif
     
116. 
     
117. 
     
118. 
     
119.            exit(0);
     
120. }
     

复制代码

其他都可以，除了char*类型无法正确匹配.

[ 本帖最后由 SybaseLU 于 2007-8-13 17:18 编辑 ]

jigloo

我觉得这个结果是理所当然的。
这句

1. 
   
2. if (*first == value)
   

复制代码

两边都是char*,怎么比啊。
你的测试例子中一边是局部字符串地址，一边字面字符串的地址，不会相等的。
而string之类的对象重载了==,当然就相等了，char*又没办法重载。
还是实现一个remove_if函数吧。

SybaseLU

比较和调试了标准STL和我的tiny STL， 标准的STL测试代码如下：

1. 
   
2. main()
   
3. {
   
4.         char* as = "aaa";
   
5.         char* bs = "bbb";
   
6.         char* cs  = "aaa";
   
7. 
   
8.         list<char*> S;
   
9.         list<char*>::iterator j;
   
10.         S.push_back(as);
    
11.         S.push_back(bs);
    
12.         S.push_back(cs);
    
13. 
    
14.         for(j=S.begin(); j != S.end(); ++j) cout << *j << " ";
    
15.         cout << endl;
    
16. 
    
17.         S.remove("aaa");
    
18.         for(j=S.begin(); j != S.end(); ++j) cout << *j << " ";
    
19.         cout << endl;
    

复制代码

在remove设置断点的GDB部分调试结果：

1. 
   
2. (gdb) print __value
   
3. $3 = (char * const&) @0xbfffe15c: 0x80490e0 "aaa"
   
4. (gdb) print *__first
   
5. $4 = (char *&) @0x804a7c0: 0x80490e0 "aaa"
   
6. 
   
7. (gdb) step
   
8. std::_List_iterator<char*, char*&, char**>::operator*() const (this=0xbfffe120)
   
9.     at stl_list.h:138
   
10. 138           { return ((_Node*) _M_node)->_M_data; }
    
11. 
    
12. (gdb) print ((_Node*) _M_node)->_M_data
    
13. $5 = 0x80490e0 "aaa"
    

复制代码

不明白的地方：
1 0xbfffe15c: 0x80490e0这两个分别是什么地方的地址?我认为前者是data段中的地址， 而后者是栈中地址。
2 标准STL使用list<char*>存放的是什么地址，是data段中的地址吗？


我的tiny STL部分GDB调试：

1. 
   
2. (gdb) print context[2]
   
3. $1 = "aaa\000\000\000\000\000\000"
   
4. (gdb) print &context[2]
   
5. $2 = (char (*)[10]) 0xbffff4f4
   
6. (gdb) print value
   
7. $3 = (char * const&) @0xbffff4d4: 0x804b56d "aaa"
   
8. (gdb) print &value
   
9. $4 = (char * const *) 0xbffff4d4
   
10. ...
    
11. (gdb) print *first
    
12. $10 = (char *&) @0x804e6b8: 0xbffff4f4 "aaa"
    

复制代码

我存放的是data段中的地址，返回的也是data段中的地址【0xbffff4f4】， 而标准的STL返回应该的是局部的栈中的地址。

说错了，标准STL和tiny STL存放的都应该是函数main栈中的地址【只要是在函数体外的变量才是在data段中】

[ 本帖最后由 SybaseLU 于 2007-8-13 18:10 编辑 ]

jigloo

1. 嗯。我也这么认为的。
2. list<char*>中的字符串地址是push_back过来的。push_back("aaaa")和a[]="aaa";S.push_back(a)的char*是不同的。
我觉得楼主在设计这个List的时候，主要目的是要按容器的值语义来使用这个List的。所以用这个List来管理指针型数据时，remove_if是少不了的。也可以在构造list时传入比较函数。

[ 本帖最后由 jigloo 于 2007-8-13 17:44 编辑 ]