Question 190357 in Visual Studio Code Question posted in
View the official documentation.

Visual Studio Code – using C++ ranges to create hierarchical tree structure from a flattened table

I have a simple struct containing three fields and a spaceship operator <=> as follows:

using MyStruct = struct MyStruct {
    unsigned id;
    std::filesystem::path sourcePath;
    std::string functionName;
    auto operator<=>(const MyStruct&) const = default;
};

The data is initialized as shown below:

std::vector<MyStruct> structs{
    {1, "c:/temp/file3.c", "chimp()"},
    {2, "c:/temp/file3.c", "ape()"},
    {3, "c:/temp/file1.c", "foo()"},
    {4, "c:/temp/file1.c", "bar()"},
    {5, "c:/temp/file1.c", "baz()"},
    {6, "c:/temp/sub/file3.c", "file3Fn2()"},
    {7, "c:/temp/sub/file3.c", "file3Fn1()"},
    {8, "c:/temp/file2.c", "file2Fn2()"},
    {9, "c:/temp/file2.c", "file2Fn3()"},
    {10, "c:/temp/file2.c", "file2Fn1()"},
};

I am trying to create a very simple sorted tree from the following 2 fields (sourcePath and functionName). I do not care about the id field.

In order to create the tree struct, I need to filter out the unique filenames and then add the function names as leaves to these filenames.

I would like to use the new c++20 ranges or ranges-v3 to to achieve this but I am having trouble piping the right ranges/views together. I need to break up the flattened data into 2 loops: an outer one containing filenames, and an inner one with the function names associated with each filename.

The tree I am after is:

├───root
    ├───file1.c
    │   ├───foo()
    │   ├───foo()
    │   └───baz()
    ├───file2.c
    │   ├───file2Fn1()
    │   ├───file2Fn2()
    │   └───file2Fn3()
    ├───file3.c
    │   ├───ape()
    │   └───chimp()
    └───sub
        └───file3.c
            ├───file3Fn1()
            └───file3Fn2()

This is the code (and results) I have so far (Visual Studio 2022 Preview 2)

#include <algorithm>
#include <format>
#include <iostream>
#include <filesystem>

using MyStruct = struct MyStruct {
    unsigned id;
    std::filesystem::path sourcePath;
    std::string functionName;
    auto operator<=>(const MyStruct&) const = default;
};

//! Template partial specialization for use with std::formatter
template<>
struct std::formatter<MyStruct> : std::formatter<std::string_view> {
    // parse inherited from std::formatter<std::string_view>
    template <typename FormatContext>
    auto format(const MyStruct& arg, FormatContext& ctx) {
        return formatter<string_view>::format(std::format(
            "{}t{}t{}"
            , arg.id
            , arg.sourcePath.generic_string()
            , arg.functionName), ctx);
    }
};

void
print(std::string_view intro, const std::vector<MyStruct>& container) {
    std::cout << intro << 'n';
    for (const auto& next : container) {
        std::cout << std::format("{}n", next);
    }
}

std::vector<MyStruct> structs{
    {1, "c:/temp/file3.c", "chimp()"},
    {2, "c:/temp/file3.c", "ape()"},
    {3, "c:/temp/file1.c", "foo()"},
    {4, "c:/temp/file1.c", "bar()"},
    {5, "c:/temp/file1.c", "baz()"},
    {6, "c:/temp/sub/file3.c", "file3Fn2()"},
    {7, "c:/temp/sub/file3.c", "file3Fn1()"},
    {8, "c:/temp/file2.c", "file2Fn2()"},
    {9, "c:/temp/file2.c", "file2Fn3()"},
    {10, "c:/temp/file2.c", "file2Fn1()"},
};

// comparator used for unique
static const auto customComp = [](const auto& lhs, const auto& rhs) {
    return std::tie(lhs.sourcePath, lhs.functionName) <
        std::tie(rhs.sourcePath, rhs.functionName);
    };

int
main() {

    auto copy = structs;
    std::ranges::sort(copy, {}, &MyStruct::sourcePath);
    print("after sorting by sourcePath", copy);
    std::ranges::sort(copy, customComp);
    print("after sorting by customComp", copy);
}

program output is as follows, note the order of the customComp comparator seems to produce the correctly ordered results.

after sorting by sourcePath
3       c:/temp/file1.c foo()
4       c:/temp/file1.c bar()
5       c:/temp/file1.c baz()
8       c:/temp/file2.c file2Fn2()
9       c:/temp/file2.c file2Fn3()
10      c:/temp/file2.c file2Fn1()
1       c:/temp/file3.c chimp()
2       c:/temp/file3.c ape()
6       c:/temp/sub/file3.c     file3Fn2()
7       c:/temp/sub/file3.c     file3Fn1()
after sorting by customComp
4       c:/temp/file1.c bar()
5       c:/temp/file1.c baz()
3       c:/temp/file1.c foo()
10      c:/temp/file2.c file2Fn1()
8       c:/temp/file2.c file2Fn2()
9       c:/temp/file2.c file2Fn3()
2       c:/temp/file3.c ape()
1       c:/temp/file3.c chimp()
7       c:/temp/sub/file3.c     file3Fn1()
6       c:/temp/sub/file3.c     file3Fn2()
Tags:

2

Answers


  1. 0

    Your projection use is wrong, you sort them by path that way. Its purpose is to take an argument and return the basis for comparison, e.g. sorting by function name:

    std::ranges::sort(copy, {},  // same as &MyStruct::functionName
                  [](MyStruct& s) ->decltype(s.functionName)& {
                       return s.functionName;
                  } );

    Obviously, spaceship operator does not effect sort unless you use std::identity as a projection.

    You can use an std::tuple projection.

    std::ranges::sort( copy, {}, [](const MyStruct& s) { 
                        return std::tie(s.sourcePath, s.functionName); 
                   } );

    This would use default operator<=> for std::tuple, not for your class. Obviousy, if you don’t want this hassle with referencecopy issues the example above have and worrying about correct syntax of sort, you have to write a custom operator. In that case you can use a simpler version of sort function.

    For printing as a tree after sorting, the file path should be treated as a range (fs::path can be of use, for it has iterators over its lexical elements, or your own equivalent), which would add depth to the loop in print() function.

    Login or Signup to reply.
  2. 0

    I am trying to create a very simple sorted tree from the following 2 fields (sourcePath and functionName). I do not care about the id field.

    In order to create the tree struct, I need to filter out the unique filenames and then add the function names as leaves to these filenames.

    I would like to use the new c++20 ranges or ranges-v3 to to achieve this but I am having trouble […]

    So then why are you trying to achieve this with ranges? What’s the point? From what I understand you want, a simple std::map would suffice:

    #include <vector>
#include <algorithm>
#include <iostream>
#include <filesystem>
#include <map>

using MyStruct = struct MyStruct {
    unsigned id;
    std::filesystem::path sourcePath;
    std::string functionName;
    auto operator<=>(const MyStruct&) const = default;
};

std::vector<MyStruct> structs{
    {1, "c:/temp/file3.c", "chimp()"},
    {2, "c:/temp/file3.c", "ape()"},
    {3, "c:/temp/file1.c", "foo()"},
    {4, "c:/temp/file1.c", "bar()"},
    {5, "c:/temp/file1.c", "baz()"},
    {6, "c:/temp/sub/file3.c", "file3Fn2()"},
    {7, "c:/temp/sub/file3.c", "file3Fn1()"},
    {8, "c:/temp/file2.c", "file2Fn2()"},
    {9, "c:/temp/file2.c", "file2Fn3()"},
    {10, "c:/temp/file2.c", "file2Fn1()"},
};

using Map = std::map<std::filesystem::path, std::vector<std::string>>;

int
main() {

    auto copy = structs;
    
    // sort by functionName
    std::ranges::sort(copy, std::less{}, [](auto const& s){ return s.functionName; });

    Map map;
    for (auto const& s : copy) {
        map[s.sourcePath].push_back(s.functionName);
    }

    for (auto const& [file, functions] : map) {
        std::cout << file << ":t";
        int n{0};
        for (auto const& fun : functions) {
            std::cout << fun << (++n == functions.size()? "n" : ", ");
        };
    }
}

    Output:

    c:/temp/file1.c:    bar(), baz(), foo()
c:/temp/file2.c:    file2Fn1(), file2Fn2(), file2Fn3()
c:/temp/file3.c:    ape(), chimp()
c:/temp/sub/file3.c:    file3Fn1(), file3Fn2()

    https://godbolt.org/z/6P498sTGM

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search