2D list in C++ STL (Defining and Sorting)

Internship at OpenGenus

Get FREE domain for 1st year and build your brand new site

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.

Quick question:

Which is the data-type of the variable 'i1' in the above code?

list <int>:: iterator
list <list <int>>:: iterator
list <list>:: iterator
list <int, int>:: iterator
The <> signs contain the data-type of the elements in the list. Since list1 is a list of lists, therefore, its iterator type is list <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.

Before we end this discussion, here's a final question:


Will the order of the elements of the 2-D list change if we apply "row-wise" sorting?

Yes
No
No, the order of elements in the nesting list will not change. Only the order of the elements in each individual list will change.

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