In this article, we will begin with a brief recap of what lists are, followed by an introduction to 2-dimensional lists (2D list), where we shall explore creating and defining 2D lists in C++ STL and sorting them.

Table of content:

1. Lists in C++ STL
2. 2D list in C++ STL
3. Sorting individual list elements of the 2D list
4. Sorting the entire 2-D list by comparing elements from individual lists
5. Sorting the 2-D list according to the value of its elements present at a particular index

Let us begin!

Lists in C++ STL

std::list belongs to the Standard Template Library (STL) provided by C++. In contrast to vectors and arrays which provide contiguous memory allocation, lists are sequence containers with non-contiguous memory allocation i.e. the items in a list are stored all over the memory disk and connected via forward and backward pointers.

Due to this-

• Traversing a list is a slow task.
• Elements cannot be accessed quickly and randomly.
• However, insertion and deletion can be achieved in constant time complexity once the position is found.

The syntax for declaring a list is as follows:

list<int> list1;

The data type of the elements (here int) is declared inside the <> . To make a list of strings, just replace int with string. This can be done for all data-types.

To work with lists, include the header file #include <list> or #include <bits/stdc++.h>.

Quick question:

Which data structure does a list in C++ implement?

Singly linked list

Doubly linked list

Array

Stack

Since lists use both forward and backward pointers, they implement doubly linked lists.

2D list in C++ STL

The concept of 2-D lists is similar to working with two-dimensional arrays or vectors. In two-dimensional lists, we basically make a list of lists, i.e. lists are nested inside one another. They can be declared in code as

list <list <int>> list2;

For initializing it, use the assignment = operator. Ex.

list <list <int>> list2= {{1,2,3},{7,2},{5,3,1}};

We can also initalise a 2-d list using inputs from stdin by using 2 nested for loops and and deciding the size of each list. For traversal and displaying the values in the list, we still use 2 nested for loops. Let us see the code snippets-

int main()
{
    list<list<int>> list1(2); 
    cout<<"enter values:"<<endl;
    for( auto i=0;i<2;i++) 
    //here, 2 is the size of the overall list.
        {
        list<int> list2; int a;
        for(auto j1=0;j1<2;j1++) 
    // here, 2 is the size of each indiviual list. Please note that the individual lists can also be of different sizes.
            {
            cin>>a;
            list2.push_back(a);
            }
          list1.push_back(list2);
          }
    cout<<"your values:"<<endl;
    for(auto i1=list1.begin();i1!=list1.end();i1++)
    {
        list<int>& list2=*i1; 
        for(auto j=list2.begin();j!=list2.end();j++)
          {
            cout<<*j<<" ";
          }
        cout<<endl;
    }
    return 0;
}

Here, we have used the auto keyword, which assigns a data-type to the variable according to the value assigned to it, and thus, saving us the work to explicitly stating it. But, for learning's sake, please note that the data-type of j in the above code is list<int>:: iterator.

Sorting of 2-D Lists

Sorting in two dimensional lists is a tricky task. Before we begin, let use see the working of the std::list::sort() function for one dimensional lists.
Suppose we have to sort a 1-D list list1, then, using this inbuilt sort function will look like this-

list1.sort();

The sort function sorts the elements in ascending order, by default. If you'd like the largest element first, then, we pass the greater<int>() element as a parameter in the sort function. Ex.

list1.sort(greater<int>());

Time Complexity of sort() is O(nlogn).

Now, coming to sorting of 2-D lists, there are multiple scenarios possible, such as

• Sorting individual list elements of the 2-D list.
• Sorting the entire 2-D list by comparing elements from individual lists
• Sorting the 2-D list according to the value of its elements present at a particular index, like the second value in every list. This is analogous to sorting with reference to a particular column in a 2-D array.

Let us explore each of these scenarios one by one.

1. Sorting individual list elements of the 2D list

When each individual list in the 2-D list is to be sorted, we iterate through the list, and call the sort() function for every individual element.This is analogous to row-wise sorting in 2-D vectors.
Code:

//Here, list1 is our 2-D list.
for(auto i1=list1.begin();i1!=list1.end();i1++)
    {
        list<int>& list2=*i1; 
        list2.sort();
        }

So, a list list <list <int>> list2= {{3,2,4},{7,2},{5,3,1}}; will get sorted as

{
    {2,3,4},
    {2,7},
    {1,3,5}
}

2. Sorting the entire 2-D list by comparing elements from individual lists

In this scenario, the elements of the lists are compared one by one, and the lists are arranged in increasing order. This is a straight-forward case which can be achieved by using the sort() function directly on the 2-D array. This can be implemented as-

//Here, list1 is our 2-D list.
list1.sort();

So,a list list <list <int>> list2= {{3,2,4},{7,2},{5,3,1}}; will get sorted as

{
{3,2,4},
{5,3,1},
{7,2}
}

If we can to sort the list in decreasing order, we pass the function greater< list<int>>() as a parameter in the sort() function, just like in case of 1-D arrays.

3. Sorting the 2-D list according to the value of its elements present at a particular index

This is analogous to sorting with reference to a particular column in a 2-D vector. For this, we will need to design a comparison function which returns a boolean value after comparing the values of the elements at a pre-specified index. For this, we shall use std::advance, which advances the iterator by a given distance. It takes two parameters- the input operator and the number of iterations to be done.
Let us now code the comparison function:

bool compareval(const list<int>& l1,const list<int>& l2 ) {
             auto a = l1.begin();
             std::advance(a, 2);
             auto b = l2.begin();
             std::advance(b, 2);
             return *a < *b;
}
//Here, 2 is the number we want the iterator to move ahead by. So, analogously it represents the column number of a 0-indexed vector.

In the main function, we call the sort function.

 list <list <int>> list1= {{3,2,4},{7,2,0},{5,3,1}};
 list1.sort(compareval);

In this case, the output will be:

{
{7,2,0},
{5,3,1},
{3,2,4}
}
//Take a look at how the last values of the 3 lists i.e. 0, 1, 4 are now sorted.

With this article at OpenGenus, you must have the complete idea of 2D lists in C++. Enjoy.