Alphabetize text file?

L67GS (46)
I'm trying to make alphabetized lists of the items in given directories. From reading around I gather that when we read the contents of a directory, there's no simple way to read them in order? Is there a simple way to alphabetize the contents of a file after the fact? I'm assuming I need to read the contents into a vector and then order the vector but some of these files can be quite long with towards 1000 lines depicting as many items in the directory so that seems like a lot for a vector...
Please excuse my style, I prefer to write simple functions so it's easier to re-use them in other projects.
Below I'm checking to see if an earlier version of the temp file exists, deleting it if it's there, reading the directory contents and appending the contents to a new file.
I'd prefer to just read the directory in order if there's a trick for that in Linux.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
bool FileExists(string findFile){
	bool var0;
	FILE *file;
	if (file = fopen(findFile.c_str(), "r")) {
		fclose(file);
		var0 = 1;
   } 
return var0;
}
/////
void AppendString(string theFile, string words){
 	MyFile.open (theFile, ios_base::app);
	MyFile << words << endl;
	MyFile.close();
}
/////
void FilesToText(string dir){
	if(FileExists("temp.txt") == 1){
		remove("temp.txt");
	}
	string file;
	for(const auto & entry : filesystem::directory_iterator(dir)){
		file = entry.path();
			AppendString("temp.txt", file);
	}
}
Last edited on
L67GS (46)
This works, but it seems like workingVec could get REALLY BIG, lol. Note this version can be used to peruse recursively or the working directory only by commenting the unwanted part.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
void FilesToOrderedText(string dir){
	vector<string> workingVec;
	if(FileExists("temp.txt") == 1){
		remove("temp.txt");
	}
	string file;
//	for(const auto & entry : filesystem::directory_iterator(dir)){
//		file = entry.path();
//			workingVec.push_back(file);
//	}
	for(const auto & entry : filesystem::recursive_directory_iterator(dir)){
		file = entry.path();
			workingVec.push_back(file);

	}
    sort(workingVec.begin(), workingVec.end()); // Alphabetize

	for(auto i : workingVec){
		cout << i << " " << endl;
		AppendString("temp.txt", i);
	}

}
Peter87 (11266)
I don't think I understand your concern. If you have 1000 paths and each path is 100 characters long then it would only use around 100 KB. If you use directory_iterator to iterate over the files in a single directory (not recursive_directory_iterator) then you only need to store the filenames (not the whole paths) in the vector.
Last edited on
kigar64551 (855)
First and foremost, instead of writing the file names to a text file and then loading them from the text file back into memory (STL container), just to be able to sort them, why not keep them in memory (STL container) right away?

Furthermore, instead of using an std::vector and then having to sort the elements explicitly with sort(), you could simply use a std::set, which keeps its elements sorted implicitly/automatically.

(std::set is usually implemented as a red–black tree, which allows its elements to be kept sorted extremely efficiently.)

________________

I doubt this is necessary in your use case, but...

If you need to sort REALLY HUGE data, i.e., data that is too big to load into memory at once, then it is possible to break the list down into separate chunks (files), so that each chunk is small enough to fit into memory. Next, each chunk can be sorted individually, using a normal in-memory algorithm (e.g. Quicksort). Finally, the sorted chunks (files) can be merged together into a single file using Merge Sort.

That is exactly what the Unix/Linux command-line tool sort does for very large inputs:
https://en.wikipedia.org/wiki/Sort_(Unix)

________________

Another option would be using an SQLite "in memory" database to store and sort your data, instead of using C++ STL containers. In my experience, SQLite is much more memory-efficient when it comes to working with VERY LARGE lists or sets. So, in situations where keeping all data in memory at once is not possible with a C++ STL container, SQLite may very well still be able to do so!

That plus: With SQLite you can always switch to file-backed database, if neccessary.
Last edited on
L67GS (46)
Thank you guys for your responses, I guess it just seemed like a lot of data in a vector but I guess it was an over reaction on my part. I went with this function and it seems to be working well, and as suggested it reads the file names directly into a vector, orders them, and then iterates the vector to append each item to the text file alphabetically.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
void FilesToOrderedText(string dir){
	vector<string> workingVec;
	if(FileExists("temp.txt") == 1){
		remove("temp.txt");
	}
	string file;
//	for(const auto & entry : filesystem::directory_iterator(dir)){
	for(const auto & entry : filesystem::recursive_directory_iterator(dir)){
		file = entry.path();
			workingVec.push_back(file);

	}
    sort(workingVec.begin(), workingVec.end()); // Alphabetize

	for(auto i : workingVec){
		cout << i << " " << endl;
		AppendString("temp.txt", i);
	}

}
seeplus (6655)
Don't put AppendString within a loop. You're opening/closing the output file for every string appended to the file. This is extremely inefficient.

You also don't need to delete an existing temp.txt file. If you open for output then any existing file contents will be removed.

It's been mentioned that a set could be used instead of vector and sort. Whilst this is true, for a large number of entries it's generally quicker to use vector/sort than a set.

Consider:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
#include <iostream>
#include <string>
#include <fstream>
#include <filesystem>
#include <iomanip>
#include <vector>
#include <algorithm>

namespace fs = std::filesystem;

constexpr const char* outnam { "temp.txt" };	// Output file name

int main(int argc, char* argv[]) {
	// Open file for output. Erases existing content if already exists
	std::ofstream ofs(outnam);

	// If output file not opened, report error
	if (!ofs.is_open())
		return (std::cout << "Cannot open output file" << std::quoted(outnam, '\'')), 2;

	std::vector<std::string> fnames;	// Vector of folder names to iterate

	// Make a vector of specified folder names or . for current if none specified
	if (argc > 1)
		 for (auto i { 1 }; i < argc; fnames.emplace_back(argv[i++]));
	else
		fnames.emplace_back(".");

	std::vector<std::string> names;		// Vector of iterated file names

	// Iterate required folder names
	for (const auto& fn : fnames)
		// Iterate folder names
		for (const auto& entry : fs::recursive_directory_iterator(fn))
			// Only process regular files
			if (entry.is_regular_file())
				names.emplace_back(entry.path().string());

	std::sort(names.begin(), names.end());	// Sort file names

	// Display file names and output to file
	for (const auto& snam : names) {
		std::cout << snam << '\n';
		ofs << snam << '\n';
	}

	ofs.close();	// CLose opened file
}

Last edited on
kigar64551 (855)
Insert operation in std::set (Red-Black-Tree) has complexity O(log(n)). So, overall, for n inserts we get O(n × log(n)).

Meanwhile, insert operation in std::vector has complexity O(1), but the required qsort() at the end has complexity O(n × log(n)) in the best case and complexity O(n²) in the worts case. So, overall, for n inserts we get something in between O(n × log(n)) and O(n²).

Hence, in the best case they are equal, but in the wort case std::set clearly wins.

I know that, most of the time, qsort() is closer to O(n × log(n)) than to O(n²), which means, that, in practice, they are essentially equal.


Now tell me that std::vector is better because of cache locality... 🤫
Last edited on
Peter87 (11266)
The sorting function that was used previously in this thread was std::sort which should have a complexity of O(n×log(n)) even in the worst case.

I was also expecting std::vector+sorting to be faster because of cache locality etc. but I did some testing and it seems like inserting into std::set is actually quite a lot faster than inserting everything into a std::vector and then sort. Iterating over the vector is a lot faster but if you only do it once it's not enough to make up for it.

Interestingly, std::list+sort seems be even faster. Now I need to think about why that is...

EDIT: Disregard what I said above. I had turned on compiler optimizations but forgot to turn off the standard library debug mode (-D_GLIBCXX_DEBUG with libstdc++). Now I see that std::vector+sort is indeed the fastest, as expected.
Last edited on
Registered users can post here. Sign in or register to post.