cpp列表中的哨兵节点不像预期的那样工作

Question

我正在编写cpp-11，并希望根据收到的数据创建一个列表。数据结构为std::list>。外部列表存储内部列表的列表，当几个连续的内部列表具有相同的标签时，则应将它们分组在一起，否则将创建一个新条目。类似地，内部列表计数具有相同标签并存储总计数的连续数据条目的数目，否则将创建一个新条目。

我使用下面的技巧来避免每次判断容器是否为空。在开始创建列表时，将一个哨兵节点插入到新创建的容器中。哨兵节点获得一个永远不会出现在接收到的数据中的标签。因此，每次新的数据出现时，我都会将数据与最后一个条目的标签进行比较，而不是插入额外的代码来判断这是否是当前列表中的第一个条目。

但它并不像预期的那样起作用。似乎根本没有插入哨兵节点。

这是密码。

#include <list>
#include <tuple>
#include <iostream>

using profileLoc = std::pair<char, size_t>;
using profileGrp = std::pair<char, std::list<profileLoc>>;

std::list<profileGrp> totalInfo;

void dump(bool isFinal=false){
  static int dumpCount = 0;
  if(isFinal) std::cout<<"Final ";
  std::cout<<"dump "<< ++dumpCount<<"\n";
  for(auto grp:totalInfo){
    if(grp.first==-1) continue;
    std::cout<<"grp label: "<<grp.first<<"\n";
    for(auto range: grp.second){
      if(std::get<0>(range)==0) continue;
      std::cout<<"\ttype label: "<<std::get<0>(range)<<" count: "<<std::get<1>(range)<<"\n";
    }
  }
}

int main(){

  profileGrp dummyGrp{-1,{{0,0}}};
  totalInfo.push_back(dummyGrp);
  

  using dataTy = std::tuple<int, char>;
  std::list<dataTy> sampleData{
    {'X', 'a'},
    {'X', 'a'},
    {'X', 'a'},
    {'X', 'b'},
    {'X', 'b'},
    {'X', 'b'},
    //{'Y', 'c'},
    //{'Y', 'c'},
    //{'Y', 'b'},
    //{'Y', 'b'},
    //{'Y', 'b'},
  };
  
  for(auto data:sampleData){
    char grpNo;
    char typeNo;
    std::tie(grpNo, typeNo) = data;
    std::cout<<"receiving data "<<grpNo<<" "<<typeNo<<"\n";
    
    profileGrp& lastGrp = totalInfo.back();
    if(lastGrp.first != grpNo){
      std::list<profileLoc> dummyList{{0, 0}};
      totalInfo.emplace_back(grpNo, dummyList);
      lastGrp = totalInfo.back();
    }
    
    std::list<profileLoc>& locList = lastGrp.second;
    if(std::get<0>(locList.back())!=typeNo){
      locList.emplace_back(typeNo, 1);
    } else {
      size_t lastCount = std::get<1>(locList.back());
      locList.pop_back();
      locList.emplace_back(typeNo, lastCount+1);
    }
    
    //dump();
  }

  dump(true);
  return 0;
}

我得到的结果是：

receiving data X a
receiving data X a
receiving data X a
receiving data X b
receiving data X b
receiving data X b
Final dump 1
grp label: X
    type label: a count: 1
grp label: X
    type label: a count: 2
    type label: b count: 3

如果你知道怎么修改密码，请告诉我。谢谢。

receiving data X a
receiving data X a
receiving data X a
receiving data X b
receiving data X b
receiving data X b
Final dump 1
grp label: X
    type label: a count: 3
    type label: b count: 3

Answer 1

先让它起作用，然后试着让它更好地工作。

下面是一个删除哨兵节点的修订版。尝试将其添加回并与您的代码进行比较。

#include <list>
#include <tuple>
#include <iostream>

using profileLoc = std::pair<char, size_t>;
using profileGrp = std::pair<char, std::list<profileLoc>>;

class MyInfo{
public:
    MyInfo& AddEntry(char groupNo, char typeNo)
    {
        bool g_f = false;
        for(auto & g : totalInfo)
        {
            if(g.first == groupNo){
                bool l_f = false;
                for(auto& loc: g.second)
                {
                    if(loc.first == typeNo){
                        ++loc.second;
                        l_f = true;
                    }
                }
                if( !l_f )
                    g.second.emplace_back(typeNo, 1);
                g_f = true;
            }
        }
        if( !g_f )
            totalInfo.emplace_back(groupNo,std::list<profileLoc>{{typeNo, 1}} );

        return *this;
    }
    
#ifdef _DEBUG
    void Dump(bool isFinal = false)
    {
        static int dumpCount = 0;
        if(isFinal) std::cout<<"Final ";
        std::cout<<"dump "<< ++dumpCount <<"\n";
        for(const auto& grp:totalInfo){ // use reference if you don't want to make a copy
                  // here you don't need. the const modifier is a good practice
                  // to communicate to the compiler you have no 
                  // intention to modify it in the following for-loop scope
                   
        //if(grp.first==-1) continue;
            std::cout<<"grp label: "<<grp.first<<"\n";
            for(const auto& range: grp.second){
                if(std::get<0>(range)==0) continue;
                std::cout<<"\ttype label: "<<std::get<0>(range)<<" count: "<<std::get<1>(range)<<"\n";
            }
        }
    }
#else
    void Dump(bool){}
#endif
private:
    std::list<profileGrp> totalInfo;
};

int main(){
  using dataTy = std::tuple<int, char>;
  std::list<dataTy> sampleData{
    {'X', 'a'},
    {'X', 'a'},
    {'X', 'a'},
    {'X', 'b'},
    {'X', 'b'},
    {'X', 'b'},
    {'Y', 'c'},
    {'Y', 'c'},
    {'Y', 'b'},
    {'Y', 'b'},
    {'Y', 'b'},
  };
  
    MyInfo info;
  
    for(auto& data:sampleData){
        auto& [grp,type] = data;
        info.AddEntry(grp, type);
    }
    
    info.Dump(true);

    return 0;
}

上面的实现不依赖于数据的排序。如果这是给定的，则可以修改AddEntry()以利用这一优势：

    MyInfo& AddEntry(char groupNo, char typeNo)
    {
        if( totalInfo.empty() || totalInfo.back().first != groupNo){
            totalInfo.emplace_back(groupNo, std::list<profileLoc>{{typeNo, 1}});
            return *this;
        }

        auto& _profLoc = totalInfo.back().second; // the std::list<profileLoc> we
                                               // are going to do more processing on
        if(_profLoc.empty() || _profLoc.back().first != typeNo )
            _profLoc.emplace_back(typeNo, 1);
        else
            ++_profLoc.back().second;
        return *this;
    }

添加哨兵来保存if list is empty检查应该是小菜一碟。

Answer 2

关于reference的一些想法，以及它与pointer的关系。希望它能帮助AshZhao更好地理解reference。

int a{5}, b{500};

int& r = a;

r是什么？它是整数的reference。那是什么意思？对象r将占用与int *一样大的空间，在其中存储a的地址。

现在

r = b;

会发生什么呢？b( 500)的值被分配给r的底层pointer所指向的接口，即a。尽管您可能希望这行被解释为将引用r与b重新关联，但编译器不会侦听，因为c++语言不允许这样做。

如果我真的需要在几行代码之后更改它在我的程序中指向的对象呢？那么，把它声明为pointer。

但是这里有一个黑客，您可以使用它来更改底层pointer，以便将它与另一个对象重新关联。在非常罕见的情况下，这是一种有用的技术，但它确实有助于理解reference实际上是什么以及它与pointer的关系。

#include <iostream>

struct IntRef
{
    int& obj;
};


int main(int argc, const char *argv[])
{
    int a{10}, b{100};
    
    IntRef r{a};
    
    std::cout<<"Now `r.obj` is correctly referencing `a`, its value is "
            << r.obj <<std::endl;
            
    // I am going to make `r.obj` referencing `b`
    // you cannot take the actual address of `r.obj`
    // as `&r.obj` will always return the address of the object
    // it points to, not its own address.
    //
    // here we make use of the knownledge that it's the first member
    // variable of struct IntRef
    //
    *reinterpret_cast<int**>(&r) = &b;
    std::cout<<"I believe `r.obj` should be re-associated with `b` now, but let's verify it"<<std::endl;
    std::cout<<"`r`'s value is "<<r.obj<<std::endl;
}